“《算法导论》之‘排序’”：初级排序算法（选择、冒泡、插入、希尔）

　  《算法》第4版作者是Robert Sedgewick 和 Kevin Wayne。

　1. 选择排序

　　选择排序可以说是最简单的排序方法。首先，找到数组中最小的那个元素；其次，将它与数组的第一个元素交换位置（如果第一个元素就是最小元素，那么它就和自己交换）；再次，在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。如此往复，直到将整个数组排序。

　　该书中提出一个命题：对于长度为N的数组，选择排序需要大约N²/2次比较和N次交换。

　　一个例子如下：以数组 arr = [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 为例。

　　第一次从数组 [8, 5, 2, 6, 9, 3, 1, 4, 0, 7] 中找到最小的数 0，放到数组的最前面（与第一个元素进行交换）：

　　

　　交换后：

　　

　　在剩余的序列中 [5, 2, 6, 9, 3, 1, 4, 8, 7] 中找到最小的数 1，与该序列的第一个个元素进行位置交换：

　　

　　交换后：

　　

　　在剩余的序列中 [2, 6, 9, 3, 5, 4, 8, 7] 中找到最小的数 2，与该序列的第一个个元素进行位置交换（实际上不需要交换）：

　　

　　重复上述过程，直到最后一个元素就完成了排序。

　　

 　  程序如下：

void SelectionSort::sort()
{
    // 将a[i]和a[i+1..len]中最小的元素交换
    for (int i = 0; i < len; i++)
    {
        int min = i;
        for (int j = i + 1; j < len; j++)
        {
            if (less(arr[j], arr[min]))
            {
                min = j;
            }
        }
        exchange(i, min);
    }
}

　2. 冒泡排序

　　从第一个元素开始，将相邻的元素两两进行比较，按照从小到大或者从大到小的顺序进行交换，这样一趟过去后，最大或最小的数字被交换到了最后一位；然后，再从头开始进行两两比较交换，直到倒数第二位时结束；以此类推，一直到所有元素都有序为止。一个例子如下：

　　原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |

　　第一趟排序（外循环）

　　第一次两两比较6 > 2交换（内循环）

　　交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |

　　交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |

　　第二次两两比较，6 > 4交换

　　交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |

　　交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |

　　第三次两两比较，6 > 1交换

　　交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |

　　交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |

　　第四次两两比较，6 > 5交换

　　交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |

　　交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

　　第五次两两比较，6 < 9不交换

　　交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |

　　交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

　　第二趟排序（外循环）

　　第一次两两比较2 < 4不交换

　　交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |

　　交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

　　第二次两两比较，4 > 1交换

　　交换前状态| 2 | 4 | 1 | 5 | 6 | 9 | 
　　交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

　　第三次两两比较，4 < 5不交换

　　交换前状态| 2 | 1 | 4 | 5 | 6 | 9 | 
　　交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

　　第四次两两比较，5 < 6不交换

　　交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |

　　交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

　　第三趟排序（外循环）

　　第一次两两比较2 > 1交换

　　交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

　　交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

　　第二次两两比较，2 < 4不交换

　　交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 
　　交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

　　第三次两两比较，4 < 5不交换

　　交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 
　　交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

　　第四趟排序（外循环）无交换

　　第五趟排序（外循环）无交换

 

　　排序完毕，输出最终结果1 2 4 5 6 9

void BubbleSort::sort()
{
    // 一一比较a[j]和a[j+1]并当a[j]>a[j+1]时进行元素交换
    for (int i = len - 1; i > -1; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (!less(arr[j], arr[j+1]))
            {
                exchange(j, j + 1);
            }
        }
    }
}

　3. 插入排序

　　插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。 插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序。

　　《算法》中提出一个命题：对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要大约N²/4次比较及大约N²/4次交换。最坏情况下需要大约N²/2次比较和大约N²/2次交换，最好情况下需要N-1次比较和0次交换。 

　　一个例子如下图：
　　现有一组数组 arr = [5, 6, 3, 1, 8, 7, 2, 4]，共有八个记录，排序过程如下：

　　

　　其中有一点比较有意思的是，在每次比较操作发现新元素小于等于已排序的元素时，可以将已排序的元素移到下一位置，然后再将新元素插入该位置，接着再与前面的已排序的元素进行比较，这样做交换操作代价比较大。还有一个做法是，将新元素取出，从左到右依次与已排序的元素比较，如果已排序的元素大于新元素，那么将该元素移动到下一个位置，接着再与前面的已排序的元素比较，直到找到已排序的元素小于等于新元素的位置，这时再将新元素插入进去，就像下面这样：

　　

 　　代码如下：

void InsertionSort::sort()
{
    for (int i = 1; i < len; i++)
    {
        // 将a[i]插入到a[i-1]、a[i-2]、a[i-3]...之中
        for (int j = i; j > 0 && less(arr[j], arr[j - 1]);j--)
        {
            exchange(j, j - 1);
        }
    }
}

　4. 希尔排序

 　　下边描述摘自一博文：

　　希尔排序算法（又称缩小增量排序算法）是按其设计者希尔（Donald Shell）的名字命名，该算法由1959年公布，是插入排序的一种更高效的改进版本。它的作法不是每次一个元素挨一个元素的比较。而是初期选用大跨步（增量较大）间隔比较，使记录跳跃式接近它的排序位置；然后增量缩小；最后增量为 1 ，这样记录移动次数大大减少，提高了排序效率。希尔排序对增量序列的选择没有严格规定。

　　希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
• 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位

　　算法思路：

　　1）先取一个正整数 d₁(d₁ < n)，把全部记录分成 d₁ 个组，所有距离为 d₁ 的倍数的记录看成一组，然后在各组内进行插入排序

　　2）然后取 d₂(d₂ < d₁)

　　3）重复上述分组和排序操作；直到取 d_i = 1(i >= 1) 位置，即所有记录成为一个组，最后对这个组进行插入排序。一般选 d₁ 约为 n/2，d₂ 为 d₁ /2， d₃ 为 d₂/2 ，…， d_i = 1。

　　假设有数组 array = [80, 93, 60, 12, 42, 30, 68, 85, 10]，首先取 d₁ = 4，将数组分为 4 组，如下图中相同颜色代表一组：

　　

　　然后分别对 4 个小组进行插入排序，排序后的结果为：

　　

　　然后，取 d₂ = 2，将原数组分为 2 小组，如下图：

　　

　　然后分别对 2 个小组进行插入排序，排序后的结果为：

　　

　　最后，取 d₃ = 1，进行插入排序后得到最终结果：

　　

 　　代码如下：

void ShellSort::sort()
{
    for (int step = len / 2; step > 0; step /= 2)
    {
        for (int i = step; i < len; i++)
        {
            // 将a[i]插入到a[i-step]、a[i-2*step]、a[i-3*step]...之中
            for (int k = i; k >= step && less(arr[k], arr[k - step]); k -= step)
            {
                exchange(k, k - step);
            }
        }
    }
}

　　完整代码请参考Github.