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

vlambda
2020-07-27

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

选择排序

- Select Sort -

排序算法是算法领域十分经典的一类算法，它的名字通俗易懂：给数字排序，让一组无序的数据通过排序算法后，能增序或者降序地输出。

排序算法有很多种，本文来详细讲讲

"选择排序法"。

（本文均是增序排序，降序排序同理即略）

No.1

算法理解

先看看上图给 "6 5 4 3 2 1" 6个数字增序排序的流程。

大体过程：

我们把一串待排序的数字分为已排序、和待排序的两类（当然，初始状态全都是待排序的）。然后每一趟将待排序中的最小值和待排序中第1个元素交换，此时待排序中第1个元素就能归到已排序中。将这个流程进行 6 趟就完成了排序。

No.2

算法剖析

我们将待排序的 n 个数字均存在数组中，数组从下标 0 开始到 n - 1 结束。

选择排序的基本思想：

🔺 排序 n 个数字需要 n 趟

第 i 趟的过程：

（此时数组内 0 ~ i-1 是已排序部分、i ~ n-1是未排序部分）

🌂在 i ~ n-1 中找到最小值对应的下标

🌂将 i ~ n-1 中的最小值与 i 中值交换

下面看一个具体的例子来理解算法

将 "4 5 6 3 2 1" 增序排序，图中红色部分为已排序部分、黄色部分为未排序部分。

下面这个gif可以让大家动态地了解选择排序

No.3

算法实现

由于算法中包含两个数字交换的过程，先看看交换函数：

/* 交换函数 * 传入：待交换两元素的地址 */void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp;}

下面是选择排序函数，亲测无误：

/* 增序的选择排序 * 传入：待排序数组a、数组元素个数n */void selectSort(int a[], int n) { /* 进行n趟操作 */ for(int i = 0; i < n; i++) {  int min_index = i; //记录待排序部分中最小值的下标  /* 扫描待排序部分，知道到最小值的下标 */ for(int j = i; j < n; j ++) { if(a[j] < a[min_index]) min_index = j; //时刻更新最小值下标 } swap(a + i,a + min_index); //交换 当前位 和 待排序部分中最小值 }}

奉上完整代码：

#include <cstdio> /* 交换函数 * 传入：待交换两元素的地址 */void swap(int *x, int *y) { int temp = *x; *x = *y; *y = temp;} /* 增序的选择排序 * 传入：待排序数组a、数组元素个数n */void selectSort(int a[], int n) { /* 进行n趟操作 */ for(int i = 0; i < n; i++) {  int min_index = i; //记录待排序部分中最小值的下标  /* 扫描待排序部分，知道到最小值的下标 */ for(int j = i; j < n; j ++) { if(a[j] < a[min_index]) min_index = j; //时刻更新最小值下标 } swap(a + i,a + min_index); //交换 当前位 和 待排序部分中最小值 }} int main() { int a[] = {5,2,3,4,15,16,100,23,88}; selectSort(a, 9);  for(int i = 0; i < 9; i++) printf("%d ", a[i]); //输出结果：2 3 4 5 15 16 23 88 100}

No.4

简单算法分析

这里主要考虑和冒泡排序👇👇👇 做一下对比。

（点击图片，可查看冒泡排序详解）

🔺时间消耗分析

选择排序的时间复杂度是

虽然和冒泡排序一样，但其实仔细想想可以发现，选择排序是进化了的冒泡排序。两者都是每趟操作将未排序序列中最小的元素移至当前正在排序的位置。只是选择排序是一个个比较，在这个过程中记录下最小元素的下标，扫描完直接交换依次即可；而冒泡排序也是一个个比较，而比较一次后就需要考虑是否要交换一次，最终将最小的元素一步步移动到了指定位置。

🔺稳定性分析

排序算法的稳定性

排序前 2个相等的数其在序列中的前后位置和排序后的前后位置顺序相同，则说明是稳定的排序算法。

那么选择排序的稳定性怎么样呢？看看下面这个例子：

将 5、8、5、2、9选择排序第一次会选择出一个最小的5，即下标为0的5和2进行了交换。通过排序，下标为0的5，跑到下标为2的5后面。