选择排序

 

思路

  • 确定第1位:从0~length-1中找出最小的数,与第1位的元素交换位置。
  • 确定第2位:从1~length-1中找出最小的数,与第2位的元素交换位置。
  • ……
  • 确定第n-1位:……

从?~?中找出最小的数的思路是:声明int min记录最小值;遍历数组,当元素比min小时,把元素赋值给min;遍历结束时,min即为最小值。

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

实现

void select_sort(const int* a, int length){
    for(int i = 0; i < length-1; i++){
        int minIndex = i;
        for(int j = i+1; j < length; j++){
            if(a[j] < a[minIndex]){
                minIndex = j;
            }
        }
        if(minIndex != i){
            swap(a[i], a[minIndex]);
        }
    }
}

关键点注释

  • 1层遍历。
  • 遍历从0到length - 1,即:“思路”中确定第1位~确定n - 1位。
  • 遍历体分为两部分。
  • 第1部分找出子数组中最小值。
  • 第2部分把最小值与目标索引的值交换。