本文内容借鉴一本我非常喜欢的书——《数据结构与算法图解》。学习之余，我决定把这本书精彩的部分摘录出来与大家分享。 

目录

1.选择排序

2.选择排序实战

3.选择排序的实现

4.选择排序的效率

5.忽略常数

6.大O的作用

7.总结

前言

大 O 是一种能够比较算法效率，并告诉我们在特定环境下应采用何种算法的伟大工具。但我们不能完全依赖于它。

因为有时候即使两种算法的大 O 记法完全一样，但实际上其中一个比另一个要快得多。

本章我们就来学习如何分辨那些效率貌似一样的算法，从而选出较快的那个。

正文

1.选择排序

上一章分析了冒泡排序算法，其效率是 O(N^2 )。现在我们再来探索另一种排序算法，选择排序，并将它跟冒泡排序对比一下。

选择排序的步骤如下。

(1) 从左至右检查数组的每个格子，找出值最小的那个。在此过程中，我们会用一个变量来记住检查过的数字的最小值（事实上记住的是索引，但为了看起来方便，下图就直接写出数值）。如果一个格子中的数字比记录的最小值还要小，就把变量改成该格子的索引，如图所示。

(2) 知道哪个格子的值最小之后，将该格与本次检查的起点交换。第 1 次检查的起点是索引 0，

第 2 次是索引 1，以此类推。下图展示的是第一次检查后的交换动作。

(3) 重复第(1) (2)步，直至数组排好序。

2.选择排序实战

以数组 [4,2,7,1,3] 为例，步骤如下。

开始第 1轮检查。

首先读取索引 0。根据此算法的定义，它是目前遇到的最小值（因为现在只检查了一个格子），于是记下其索引。

第 1步：将索引 1的值 2与目前的最小值 4进行比较。

2比 4还要小，于是将目前的最小值改为 2。

第 2步：再与下一个值做比较。因为 7大于 2，所以最小值还是 2。

第 3步：将 1和目前的最小值做比较。

1比 2还要小，于是目前的最小值更新为 1。

第 4步：比较 3和目前的最小值 1。因为现在已经走到数组尽头了，所以可以断定 1是整个

数组的最小值。

第 5步：本次检查的起点是索引 0，不管那里的值是什么，我们都应该将最小值 1换到那里。

现在 1就排到正确的位置上了。

可以开始第 2轮检查了。

准备工作：因为索引 0的值已符合其排位，所以这一轮从下一个格子开始，即索引 1，其值为 2，也是目前本轮所遇到的最小值。

第 6步：将 7跟目前的最小值 2进行比较。因为 2小于 7，所以最小值仍为 2。

第 7步：将 4跟目前的最小值 2进行比较。因为 2小于 4，所以最小值仍为 2。

第 8步：将 3跟目前的最小值 2进行比较。因为 2小于 3，所以最小值仍为 2。

又走到数组尽头了。本轮不需要做任何交换，2已在其正确位置上。于是第 2轮检查结束，现在数组如下图所示。 、

开始第 3轮检查。

准备工作：从索引 2起，其值为 7。于是本轮目前最小值为 7。

第 9 步：比较 4 与 7。

将 4 记为目前的最小值。

第 10 步：遇到 3，它比 4 还小。

于是 3 成了目前的最小值。

第 11 步：到数组尽头了，将 3 跟本轮起点 7 进行交换。

于是 3 排到正确位置上了。

虽然我们可以看到现在整个数组都有序了，但计算机是看不到的，它只会继续第 4轮检查。

准备工作：此轮检查从索引 3开始，其值 4是目前的最小值。

第 12步：比较 4和 7。

4仍为最小值，而且它也处于本轮起点，因此无须任何交换。

因为最后一个格子左侧的那些值都已在各自的正确位置上，所以最后一格也必然正确，于是排序结束。

3.选择排序的实现

下面是用C语言实现的选择排序：

void SelectSort(int arr[], int n)//升序
{
  for (int i = 0; i < n-1; i++) //n个数，只需排好n-1个，剩下的一个自然在正确的位置上
  {
    int min = i;      //用min来记录最小值的索引（下标）         
        for (int j = i+1; j < n; j++)  //从i索引的后一个开始比较
    {
      if (arr[j] < arr[min])
      {
        min = j;            //找到比自己小的数的索引，并成为它
      }
    }
    if (min != i)               //如果min的值改变，则与i处的值交换
    {
      int tmp = arr[i];
      arr[i] = arr[min];
      arr[min] = tmp;
    }
  }
}

下面来进行分析：

for (int i = 0; i < n-1; i++)

这个外层的循环代表每一轮检查。在一轮检查之初，我们会先记住目前的最小值的索引。

int min = i;

因此每轮开始时 min 都会是该轮的起点索引 i 。

注意我们实际上记录的是最小值的索引，而非最小值本身。于是，第 1 轮开始时最小值的索引是 0，到第 2 轮则是 1，以此类推。

for (int j = i+1; j < n; j++)

这个内层循环控制的是找出最小值的索引的过程。

1. if (arr[j] < arr[min])
2. {
3.  min = j;            
4. }

循环内逐个检查数组未排序的格子，若遇到比之前记录的本轮最小值还小的格子值，就将min更新为该格子的索引。

内层循环结束时，会得到未排序数值中最小值的索引。

if (min != i)
{
  int tmp = arr[i];
  arr[i] = arr[min];
  arr[min] = tmp;
}

然后再看看这个最小值是否已在正确位置，即该索引是否等于 i 。如果不是，就将 i 所指的值与最小值交换。

4.选择排序的效率

选择排序的步骤可分为两类：比较和交换。

若有 N个元素，就会有 (N - 1) + (N - 2) + (N - 3) + … + 1次比较。

但每轮的交换最多只有 1 次。如果该轮的最小值已在正确位置，就无须交换，否则要做 1 次交换。相比之下，冒泡排序在最坏情况（完全逆序）时，每次比较过后都要进行 1 次交换。

下表为冒泡排序和选择排序的并列对比。

5.忽略常数

但有趣的是，选择排序的大 O记法跟冒泡排序是一样的。

还记得我们说过，大 O记法用来表示步数与数据量的关系。所以你可能会以为步数约为 N^2的一半的选择排序，其大 O会写成 O(N ^2/ 2)，以表示 N个元素需要 N ^2 / 2步。如下表所示。

6.大O的作用

尽管不能比较冒泡排序和选择排序，大 O 还是很重要的，因为它能够区分不同算法的长期增长率。当数据量达到一定程度时，O(N)的算法就会永远快过 O(N^2 )，无论这个 O(N)实际上是O(2N)还是 O(100N)。

下图为 O(N)和 O(N^2 )的对比。

这就是大 O 记法忽略常数的原因。大 O 记法只表明，对于不同分类，存在一临界点，在这一点之后，一类算法会快于另一类，并永远保持下去。至于这个点在哪里，大 O并不关心。

因此，不需要写成 O(100N)，归类到 O(N)就好了。

7.总结

现在我们已经掌握了一些非常强大的算法分析手法。我们能够使用大 O去判断各种算法的效率，即便两种算法的大 O记法一样，也知道如何对比它们。不过在对比算法时，还需要考虑一个重要因素。至今我们关注的都是最坏情况下算法会跑得多慢，但其实最坏情况并不总会发生。没错，我们遇到的大都是平均情况。下一章，我们会学习怎样顾及所有情况。