【排序算法】—— 选择排序
目录
- 一、选择排序的原理
- 二、选择排序的代码实现
- 三、选择排序的优化
- 1. 优化思路
- 2. 排序优化后问题
- 3. 优化代码的实现
- 四、选择排序的效率
一、选择排序的原理
选择排序算法是通过遍历数组,选择出数组的最小或最大值,与指定位置交换数据,遍历完整个数组的所有位置就完成排序
- 遍历第一趟数组,找出数组的最小值,与第一个数据交换
- 遍历第二趟数组,继续找出最小值,与第二个数据交换
- 重复上述动作,遍历完数组就得到一个有序数组
二、选择排序的代码实现
//交换两个数据void Swap(int* a, int* b){int temp = *a;*a = *b;*b = temp;}//选择排序void SelectSort(int* arr, int size){int i = 0;for (i = 0; i < size-1; i++){int min = i;int j = 0;for (j = i+1; j < size; j++){if (arr[j] < arr[min]){min = j;}}Swap(&arr[i], &arr[min]);}}
三、选择排序的优化
1. 优化思路
以上算法是每次找出最小的放在指定位置,一共要找n-1
次,如果我们每次不但找到最小的,还找到最大的,将最小的与左端交换,最大的与右端交换,那么就少了一半的遍历次数,从而提高效率
- 变量
begin
和变量end
是数组的两端,min
和max
分别找小和大的下标
- 先交换
min
与begin
位置的数值,再交换max
与end
位置的数值
begin
右移,end
左移,继续找大找小,继续交换
- 重复上述操作,直到遍历完所有数组
2. 排序优化后问题
若是max
的位置与begin
重合,则begin
先与min
的位置交换,此时max
位置的最大值被交换走,导致end
与max
交换的数值是错误的
max
与begin
重合
begin
先与min
的位置交换数据,此时max
位置的已经不是最大值了
max
再与end
位置交换数据,排序就发生了错误
如何解决问题呢?
当max
与begin
重合时,begin
与min
交换后导致max
指向的不再是最大值,所以当我们对begin
交换后,就要对max
进行一个修正,让max
指向最大值,然后完成end
的交换
max
与begin
重合,并且begin
此时完成了交换,此时最大值已经交换到了min
所指向的位置
- 对
max
进行修正并完成与end
的交换
3. 优化代码的实现
//交换两个数据void Swap(int* a, int* b){int temp = *a;*a = *b;*b = temp;}//选择排序void SelectSort(int* arr, int size){int begin = 0;int end = size - 1;while (begin < end){int max = begin;int min = begin;int i = 0;for (i = begin+1; i <= end; i++){if (arr[i] < arr[min]){min = i;}if (arr[i] > arr[max]){max = i;}}Swap(&arr[begin], &arr[min]);if (begin == max)//修正max{max = min;}Swap(&arr[end], &arr[max]);begin++;end--;}}
四、选择排序的效率
- 时间复杂度:O( n 2)O(n^2) O(n2)
- 空间复杂度:O(1)O(1) O(1)
选择排序是不稳定的排序
选择排序是最简单的排序算法之一,最大的优点就是很好理解,但是无论排序数组是否有序,选择排序的执行次数都不发生改变,效率一直保持这比较低的水平,所以在实际应用中几乎不使用