浅析选择排序算法

选择排序（Selection Sort）

一、算法描述

1. 在一个长度为 N 的无序数组中，第一次遍历 n 个数找到最大的和最后一个数交换。
2. 第二次从倒数第二个数开始遍历 n-1 个数，找到最大的数和倒数第二个数交换。
3. 重复以上操作直到第 n 次遍历最大的数和第 1 个数交换，排序完成。

例如：我们有 [4 9 3 1 7 2] 这样一组数字。

第一趟：我们找出最大值9和最后一个数字2进行交换。就变成了 [4 2 3 1 7 9]，这样我们就把最大值放在最后了。

第二趟：对前5个数字进行排序，同样找出最大值放在倒数第二个位置，因为7已经是这5个数字里面的最大值，所以不需要做交换。还是 [4 2 3 1 7 9]

第三趟：对前4个数字进行排序，找出最大的值放在倒数第三个位置，我们找出4和1进行交换，这样把4放在倒数第三的位置，变成[1 2 3 4 7 9]

第四趟：对前3个数字进行排序，找出最大的值放在倒数第三个位置，因为3是最大值所以不需要进行交换，还是[1 2 3 4 7 9]

第五趟：对前2个数字进行排序，找出最大的值放在倒数第三个位置，因为3是最大值所以不需要进行交换，还是[1 2 3 4 7 9]

第六趟：最后只剩一位数字我们就不用进行排序了，这样我们就对整个数组按照从小到大的顺序进行排序了。最后排序为 [1 2 3 4 7 9]

二、算法实现

#include <stdio.h>

int findMaxPos(int arr[], int n){
  int max = arr[0]; 
  int pos = 0;
  for (int i=0; i<n; i++){
    if(arr[i]>max){
      max = arr[i];
      pos = i;
    }
  }
  return pos;
}

void selectionSort(int arr[], int n){
  while (n > 1){
    int pos = findMaxPos(arr,n);
    int temp = arr[pos];
    arr[pos] = arr[n-1];
    arr[n-1] = temp;
    n--;
  }
}

int main(){
  int arr[] = {4,9,3,1,7,2};
  selectionSort(arr,6);
  for(int i=0; i<6; i++){
    printf("%d\n",arr[i]);
  }
}

输出

三、算法分析

平均时间复杂度：O(n2)

空间复杂度：O(1)

稳定性：不稳定（例如序列9 8 5 2 5，我们知道第一遍选择第1个元素9会和5交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法）

四、适用场景

选择排序适用于数据量很小的排序场景，因为选择的实现方式较为简单。

关注下方公众号，分享硬核知识