【排序算法】—— 选择排序

目录

  • 一、选择排序的原理
  • 二、选择排序的代码实现
  • 三、选择排序的优化
    • 1. 优化思路
    • 2. 排序优化后问题
    • 3. 优化代码的实现
  • 四、选择排序的效率

一、选择排序的原理

​ 选择排序算法是通过遍历数组,选择出数组的最小或最大值,与指定位置交换数据,遍历完整个数组的所有位置就完成排序

  1. 遍历第一趟数组,找出数组的最小值,与第一个数据交换

  1. 遍历第二趟数组,继续找出最小值,与第二个数据交换

  1. 重复上述动作,遍历完数组就得到一个有序数组

二、选择排序的代码实现

//交换两个数据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次,如果我们每次不但找到最小的,还找到最大的,将最小的与左端交换,最大的与右端交换,那么就少了一半的遍历次数,从而提高效率

  1. 变量begin和变量end是数组的两端,minmax分别找小和大的下标

  1. 先交换minbegin位置的数值,再交换maxend位置的数值

  1. begin右移,end左移,继续找大找小,继续交换

  1. 重复上述操作,直到遍历完所有数组

2. 排序优化后问题

​ 若是max的位置与begin重合,则begin先与min的位置交换,此时max位置的最大值被交换走,导致endmax交换的数值是错误的

  1. maxbegin重合

  1. begin先与min的位置交换数据,此时max位置的已经不是最大值了

  1. max再与end位置交换数据,排序就发生了错误

如何解决问题呢?

​ 当maxbegin重合时,beginmin交换后导致max指向的不再是最大值,所以当我们对begin交换后,就要对max进行一个修正,让max指向最大值,然后完成end的交换

  1. maxbegin重合,并且begin此时完成了交换,此时最大值已经交换到了min所指向的位置

  1. 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)

​ 选择排序是不稳定的排序

​ 选择排序是最简单的排序算法之一,最大的优点就是很好理解,但是无论排序数组是否有序,选择排序的执行次数都不发生改变,效率一直保持这比较低的水平,所以在实际应用中几乎不使用