数据结构 10.3 选择排序

362 阅读2分钟

选择排序也是一种很直观的排序方法,它从无序区里 选择 一个元素,与无序区中的第一个元素交换位置。

在我们的日常生活中,其实也经常使用选择排序,下面以摆放俄罗斯套娃为例。

在摆放时,我们将套娃划分为两个区:有序区和无序区。有序区的套娃已经是按顺序排列的,而每次要摆放新的套娃时,我们在无序区中选择一个最小的套娃,与无序区的第一个套娃交换位置。

进行到无序区只有最后两个元素时,排完这一趟即宣告结束。

实现

使用自然语言可以描述如下:

从第一个套娃开始,直到倒数第二个套娃:
    找到最小的套娃;
    与此轮遍历开始的套娃交换位置;

可以用一张简单的图表示选择排序:

使用 C 语言实现如下:

void SELECTSORT(int dolls[], int totalOfDolls) {
  for (int i = 0; i < totalOfDolls - 1; i++) {
    int minDosPos = i;
    
    for (int j = i; j < totalOfDolls; j++) {
      if (dolls[j] < dolls[minDosPos]) {
        minDosPos = j;
      }
    }

    if (minDosPos != i) {
      int temp = dolls[i];
      dolls[i] = dolls[minDosPos];
      dolls[minDosPos] = temp;
    }
  }
}

特性

排序次数

对于 n 个元素的序列,选择排序一共需要 n - 1 趟排序。

空间复杂度

只需要一个辅助空间,即 minDosPos,空间复杂度为 O(1)。

比较次数

可以发现,无论套娃的初始情况如何,选择排序法每一趟始终要进行 n - i 次元素的比较,所以元素的比较总次数为 \frac{n*(n-1)}{2}

这说明 选择排序法所进行的元素之间的比较次数与原始状态无关

时间复杂度

由上可知,时间复杂度为 O(n^2)。

稳定性

选择排序中,相同大小的元素在被选择时,处在前面的元素很可能在选择时被置换到后面去,仔细观察上文套娃的例子,同样大小的套娃在摆放后相对顺序发生了改变,所以选择排序是 不稳定排序算法