Java八大排序之选择排序
点击蓝字
思想
每次从数组中选出最大的或者最小的，存放在数组的最右边或者最左边，直到全部有序
具体实现
我们这里进行了优化，一次排序中，直接同时选出最大的数（a[maxi]）和最小的数（a[mini]）放在最右边和最左边，这样排序效率是原来的2倍
①单趟排序
找到最小的数字（a[mini]）和最大的数字（a[maxi]），将他们放在最左边和最右边
ps：其中的begin，end保存记录左右的下标，mini，maxi记录保存最小值和最大值得下标
②整个数组排序
begin++和end--这样下次就可以排剩下的n-2个数字，再次进行单趟，如此可构成循环，直到begin小于end
代码
void SelectSort(int* a, int n){int begin = 0,end = n - 1;while (begin<end){int mini = begin, maxi = begin;for (int i = begin; i <= end; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[maxi]){maxi = i;}}Swap(&a[mini], &a[begin]);//当begin==maxi时，最大值会被换走，修正一下if (begin==maxi){maxi=mini;}Swap(&a[maxi], &a[end]);begin++;end--;}}
直接选择排序总结：
①直接选择排序很好理解，但实际效率不高，很少使用
②时间复杂度：O(N^2)
③空间复杂度：O(1)
程序员 | Mr.Fire
点击下方 “阅读原文”查收