新闻资讯

选择排序

思想：

双重for循环遍历数组，在每一轮比较中，找出最小元素的下标，将最小元素换到“首位”。

publicstaticvoidselectionSort(int[] arr){int minIndex;for(int i=0; i< arr.length-1; i++){         minIndex= i;for(int j= i+1; j< arr.length; j++){if(arr[minIndex]> arr[j]){// 记录最小值的下标                 minIndex= j;}}// 将最小元素交换至首位int temp= arr[i];         arr[i]= arr[minIndex];         arr[minIndex]= temp;}}

复杂度：

时间复杂度：双重for循环，时间复杂度为O(n^2)
空间复杂度：使用有限个变量，空间复杂度为O(1)

二元选择排序：

二元选择排序时选择排序的优化，选择排序时，我们每次都找出来当前最小值，那么我们当然也可以找到最大值！这就是二元选择排序的思想。

publicstaticvoidselectionSort2(int[] arr){int minIndex, maxIndex;// i 只需要遍历一半for(int i=0; i< arr.length/2; i++){         minIndex= i;         maxIndex= i;for(int j= i+1; j< arr.length- i; j++){if(arr[minIndex]> arr[j]){// 记录最小值的下标                 minIndex= j;}if(arr[maxIndex]< arr[j]){// 记录最大值的下标                 maxIndex= j;}}// 如果 minIndex 和 maxIndex 都相等，那么他们必定都等于 i，且后面的所有数字都与 arr[i] 相等，此时已经排序完成if(minIndex== maxIndex)break;// 将最小元素交换至首位int temp= arr[i];         arr[i]= arr[minIndex];         arr[minIndex]= temp;// 如果最大值的下标刚好是 i，由于 arr[i] 和 arr[minIndex] 已经交换了，所以这里要更新 maxIndex 的值。if(maxIndex== i) maxIndex= minIndex;// 将最大元素交换至末尾int lastIndex= arr.length-1- i;         temp= arr[lastIndex];         arr[lastIndex]= arr[maxIndex];         arr[maxIndex]= temp;}}

我们使用 minIndex 记录最小值的下标，maxIndex 记录最大值的下标。每次遍历后，将最小值交换到首位，最大值交换到末尾，就完成了排序。

由于每一轮遍历可以排好两个数字，所以最外层的遍历只需遍历一半即可。

复杂度：

虽然二元选择排序只需要遍历一半，但是治标不治本。依旧使用双重for循环。
时间复杂度：双重for循环，时间复杂度为O(n^2)
空间复杂度：使用有限个变量，空间复杂度为O(1)