3.2 选择排序

选择排序

• 选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。
  
• 排序思路:

• 假设按照升序排序
• 1.用第0个元素和后面所有元素依次比较
• 2.判断第0个元素是否大于当前被比较元素, 一旦小于就交换位置
• 3.第0个元素和后续所有元素比较完成后, 第0个元素就是最小值
• 4.排除第0个元素, 用第1个元素重复1~3操作, 比较完成后第1个元素就是倒数第二小的值
• 以此类推, 直到当前元素没有可比较的元素, 排序完成

• 代码实现:

// 选择排序
void selectSort(int numbers[], int length) {
    
    // 外循环为什么要-1?
    // 最后一位不用比较, 也没有下一位和它比较, 否则会出现错误访问
    for (int i = 0; i < length; i++) {
        for (int j = i; j < length - 1; j++) {
            // 1.用当前元素和后续所有元素比较
            if (numbers[i] < numbers[j + 1]) {
                //  2.一旦发现小于就交换位置
                swapEle(numbers, i, j + 1);
            }
        }
    }
}
// 交换两个元素的值, i/j需要交换的索引
void swapEle(int array[], int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}