二.直接选择排序
1.算法剖析
基本思想： 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置,直到全部待排序的数据元素排完.
代码实现
void SelectSort(int* a, int n) { int i = 0; for (i = 0; i < n; i++)//i:排好序的元素的最大下标 { int j = 0; int min = i;//从i下标位置开始选出最小值 for (j = i; j < n; j++) { if (a[min] > a[j])//更新最小值 { min = j; } } Swap(&a[min], &a[i]);//把最小值放在i下标位置处 } }
可见,时间复杂度是O(N^2),
而且,需要注意的是直接选择排序的双层for循环中并没有出现break
也就是说无论待排序的序列是有序还是无序还是部分有序
直接选择排序并不考虑这些,它是找最大值(或者最小值)依次放到数组的起始位置
2.优化版本算法剖析
上面代码不难理解,下面我们来给大家看一个优化版本的直接选择排序,这个优化版本比上一个版本快一倍,不过时间复杂度也是O(N^2)
void Swap(int* n1, int* n2) { int tmp = *n1; *n1 = *n2; *n2 = tmp; } void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end) { int min_i = begin; int max_i = begin; for (int i = begin; i <= end; i++) { if (a[i] < a[min_i]) { min_i = i; } if (a[i] > a[max_i]) { max_i = i; } } Swap(&a[begin], &a[min_i]); //如果begin跟max_i重叠,需要修正一下max_i的位置 if (begin == max_i) { max_i = min_i; } Swap(&a[max_i], &a[end]); begin++; end--; } }
这个优化版本的思想是:
1.通过begin和end逐步缩小待排序的范围,当begin>=end时,排序完成
2.通过min_i和max_i选择出[begin,end]内的最大值和最小值,并把最小值与begin位置处的数据交换,把最大值与end位置处的数据交换.
下面是不修正max_i的代码
void Swap(int* n1, int* n2) { int tmp = *n1; *n1 = *n2; *n2 = tmp; } void SelectSortUpper(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end) { int min_i = begin; int max_i = begin; int i = 0; for (i = begin; i <= end; i++) { if (a[min_i] > a[i]) { min_i = i; } if (a[max_i] < a[i]) { max_i = i; } } Swap(&a[min_i], &a[begin]); Swap(&a[max_i], &a[end]); begin++; end--; } }
下面给大家画图解释一下为什么要修正max_i的位置
3.时间复杂度和稳定性
1.时间复杂度
直接选择排序的时间复杂度是O(N^2)
都是等差数列
未优化版本:
N+(N-1)+(N-2)+… -> O(N^2)
优化版本
N+(N-2)+(N-4)+… -> O(N^2)
2.对直接选择排序的评价
在这里我们可以看出:插入排序为1698ms,直接选择排序为4533ms,同样时间复杂度都是O(N^2),但是却相差这么大,
所以也就是说直接选择排序效率非常差,是效率最差的排序算法,
后面讲到冒泡排序(时间复杂度也是O(N^2))的时候我们还要再对比一下这三者的时间复杂度.
3.稳定性
直接选择排序不具有稳定性,下面给大家举一个例子
以上就是堆排序和直接选择排序的讲解,希望能给大家带来帮助
