vlambda博客
学习文章列表

Java八大排序之选择排序

点击蓝字

Java八大排序之选择排序


思想

每次从数组中选出最大的或者最小的,存放在数组的最右边或者最左边,直到全部有序 


具体实现


我们这里进行了优化,一次排序中,直接同时选出最大的数(a[maxi])和最小的数(a[mini])放在最右边和最左边,这样排序效率是原来的2倍


①单趟排序


找到最小的数字(a[mini])和最大的数字(a[maxi]),将他们放在最左边和最右边


ps:其中的begin,end保存记录左右的下标,mini,maxi记录保存最小值和最大值得下标

Java八大排序之选择排序


②整个数组排序


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


更多福利资源干货
点击下方 “阅读原文”查收