四种简单的排序算法

算法思想

插入排序使用了两层嵌套循环，逐个处理待排序的记录。每个记录与前面已经排好序的记录序列进行比较，并将其插入到合适的位置。假设数组长度为n，外层循环控制变量i由1至n-1依次递进，用于选择当前处理哪条记录；里层循环控制变量j，初始值为i，并由i至1递减，与上一记录进行对比，决定将该元素插入到哪一个位置。这里的关键思想是，当处理第i条记录时，前面i-1条记录已经是有序的了。需要注意的是，因为是将当前记录与相邻的上一记录相比较，所以循环控制变量的起始值为1（数组下标），如果为0的话，上一记录为-1，则数组越界。

现在我们考察一下第i条记录的处理情况：假设外层循环递进到第i条记录，设其关键码的值为X，那么此时有可能有两种情况：

1. 如果上一记录比X大，那么就交换

它们，直到上一记录的关键码比X小或者相等为止。

2. 如果上一记录比X小或者相等，那

么之前的所有记录一定是有序的，且都比X小，此时退出里层循环。外层循环向前递进，处理下一条记录。

算法实现(C#)

public class SortAlgorithm { // 插入排序

public static void InsertSort(T[] array, C comparer)

where C:IComparer {

for (int i = 1; i <= array.Length - 1; i++) {

//Console.Write(\"{0}: \", i); int j = i; while (j>=1 &&

comparer.Compare(array[j], array[j - 1]) < 0) {

swap(ref array[j], ref array[j-1]);

j--; }

//Console.WriteLine();

//AlgorithmHelper.PrintArray(array); } }

// 交换数组array中第i个元素和第j个元素 private static void swap(ref T x,ref T y) {

// Console.Write(\"{0}<-->{1} \", x, y); T temp = x; x = y; y = temp; } }

上面Console.WriteLine()方法和AlgorithmHelper.PrintArray()方法仅仅是出于测试方便，PrintArray()方法依次打印了数组的内容。swap()方法则用于交换数组中的两

条记录，也对交换数进行了打印（这里我注释掉了，但在测试时可以取消对它们的注释）。外层for循环控制变量i表示当前处理第i条记录。

public class AlgorithmHelper { // 打印数组内容

public static void PrintArray(T[] array) {

Console.Write(\" Array:\"); foreach (T item in array) { Console.Write(\" {0}\", item); }

Console.WriteLine(); } }

// 获得Comparer，进行比较 public class ComparerFactory { public static IComparer GetIntComparer() {

return new IntComparer(); }

public class IntComparer : IComparer {

public int Compare(int x, int y) { return x.CompareTo(y); } } }

上面这段代码我们创建了一个ComparerFactory类，它用于获得一个IntComparer对象，这个对象实现了IComparer接口，规定了两个int类型的关键码之间比较大小的规则。如果你有自定义的类型，比如叫MyType，只需要在ComparerFactory中再添加一个类，比如叫MyTypeComparer，然后让这个类也实现IComparer接口，最后再添加一个方法返回MyTypeComparer就可以了。

输出演示(C#)

接下来我们看一下客户端代码和输出：

static void Main(string[] args) {

int[] array = {42,20,17,13,28,14,23,15}; //int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };

AlgorithmHelper.PrintArray(array);

SortAlgorithm.InsertSort (array,

ComparerFactory.GetIntComparer()); }

算法实现(C++)

// 对int类型进行排序 class IntComparer{ public:

2.冒泡排序

static bool Smaller(int x, int y){ return xstatic bool Equal(int x, int y){ return x==y; }

static bool Larger(int x, int y){ return x>y; } };

// 插入排序

template

void InsertSort(T a[], int length){ for(int i=1;i<=length-1;i++){ int j = i;

while(j>=1 && C::Smaller(a[j], a[j-1])){

swap(a[j], a[j-1]); j--; } } }

算法思想

如果你从没有学习过有关算法方面的知识，而需要设计一个数组排序的算法，那么很有可能设计出的就是泡沫排序算法了。因为它很好理解，实现起来也很简单。它也含有两层循环，假设数组长度为n，外层循环控制变量i由0到n-2递增，这个外层循环并不是处理某个记录，只是控制比较的趟数，由0到n-2，一共比较n-1趟。为什么n个记录只需要比较n-1趟？我们可以先看下最简单的两个数排序：比如4和3，我们只要比较一趟，就可以得出3、4。对于更多的记录可以类推。

数组记录的交换由里层循环来完成，控制变量j初始值为n-1（数组下标），一直递减到1。数组记录从数组的末尾开始与相邻的上一个记录相比，如果上一记录比当前记录的关键码大，则进行交换，直到当前记录的下标为1为止（此时上一记录的下标为0）。整个过程就好像一个气泡从底部向上升，于是这个排序算法也就被命名为了冒泡排序。

我们来对它进行一个考察，按照这种排序方式，在进行完第一趟循环之后，最小的一定位于数组最顶部（下标为0）；第二趟循环之后，次小的记录位于数组第二（下标为1）的位置；依次类推，第n-1趟循环之后，第n-1小的记录位于数组第n-1（下标为n-2）的位置。此时无需再进行第n趟循环，因为最后一个已经位于数组末尾（下标为n-1）位置了。

算法实现(C#)

// 泡沫排序

public static void BubbleSort(T[] array, C comparer)

where C : IComparer {

int length = array.Length;

for (int i = 0; i <= length - 2; i++) { //Console.Write(\"{0}: \", i + 1); for (int j = length - 1; j >= 1; j--) {

if (comparer.Compare(array[j], array[j - 1]) < 0) {

swap(ref array[j], ref array[j - 1]); 输出演示(C#)

} }

//Console.WriteLine();

//AlgorithmHelper.PrintArray(array); } }

static void Main(string[] args) {

int[] array = {42,20,17,13,28,14,23,15}; AlgorithmHelper.PrintArray(array);

SortAlgorithm.BubbleSort (array,

ComparerFactory.GetIntComparer()); }

算法实现(C++)

// 冒泡排序

template

void BubbleSort(T a[], int length){ for(int i=0;i<=length-2;i++){ for(int j=length-1; j>=1; j--){ if(C::Smaller(a[j], a[j-1])) swap(a[j], a[j-1]); } } }

3.选择排序

算法思想

选择排序是对冒泡排序的一个改进，从上面冒泡排序的输出可以看出，在第一趟时，为了将最小的值13由数组末尾冒泡的数组下标为0的第一个位置，进行了多次交换。对于后续的每一趟，都会进行类似的交换。

选择排序的思路是：对于第一趟，搜索整个数组，寻找出最小的，然后放置在数组的0号位置；对于第二趟，搜索数组的n-1个记录，寻找出最小的（对于整个数组来说则是次小的），然后放置到数组的第1号位置。在第i趟时，搜索数组的n-i+1个记录，寻找最小的记录（对于整个数组来说则是第i小的），然后放在数组i-1的位置（注意数组以0起始）。可以看出，选择排序显著的减少了交换的次数。

需要注意的地方是：在第i趟时，内层循环并不需要递减到1的位置，只要循环到与i相同就可以了，因为之前的位置一定都比它小（也就是第i小）。另外里层循环是j>i，而不是j>=i，这是因为i在进入循环之后就被立即保存到了lowestIndex中。

算法实现(C#)

public static void SelectionSort(T[] array, C comparer)

where C : IComparer {

int length = array.Length;

for (int i = 0; i <= length - 2; i++) { Console.Write(\"{0}: \", i+1); int lowestIndex = i; // 最小记录的数组索引

for (int j = length - 1; j > i; j--) { if (comparer.Compare(array[j], array[lowestIndex]) < 0)

lowestIndex = j; }

swap(ref array[i], ref array[lowestIndex]);

AlgorithmHelper.PrintArray(array); } }

输出演示(C#)

static void Main(string[] args) {

int[] array = {42,20,17,13,28,14,23,15}; AlgorithmHelper.PrintArray(array);

SortAlgorithm.SelectionSort (array,

ComparerFactory.GetIntComparer()); }

算法实现(C++)

// 选择排序

template

void SelectionSort(T a[], int length) { for(int i = 0; i <= length-2; i++){ int lowestIndex = i;

for(int j = length-1; j>i; j--){ if(C::Smaller(a[j], a[lowestIndex]))

lowestIndex = j; }

swap(a[i], a[lowestIndex]);

} }

4.希尔排序

希尔排序利用了插入排序的一个特点来优化排序算法，插入排序的这个特点就是：当数组基本有序的时候，插入排序的效率比较高。比如对于下面这样一个数组：

int[] array = { 1, 0, 2, 3, 5, 4, 8, 6, 7, 9 };

插入排序的输出如下：

可以看到，尽管比较的趟数没有减少，但是交换的次数却明显很少。希尔排序的总体想法就是先让数组基本有序，最后再应用插入排序。具体过程如下：假设有数组int a[] = {42,20,17,13,28,14,23,15}，不失一般性，我们设其长度为length。

第一趟时，步长step = length/2 = 4，将数组分为4组，每组2个记录，则下标分别为(0,4)(1,5)(2,6)(3,7)；转换为数值，则为{42,28}, {20,14}, {17,23}, {13,15}。然后对每个分组进行插入排序，之后分组数值为{28,42}, {14,20}, {17,23}, {13,15}，而实际

的原数组的值就变成了{28,14,17,13,42,20,23,15}。这里要注意的是分组中记录在原数组中的位置，以第2个分组{14,20}来说，它的下标是(1,5)，所以这两个记录在原数组的下标分别为a[1]=14;a[5]=20。

第二趟时，步长 step = step/2 = 2，将数组分为2组，每组4个记录，则下标分别为(0,2,4,6)(1,3,5,7)；转换为数值，则为{28,17,42,23}, {14,13,20,15}，然后对每个分组进行插入排序，得到{17,23,28,42}{13,14,15,20}。此时数组就成了{17,13,23,14,28,15,42,20}，已经基本有序。

第三趟时，步长 step=step/2 = 1，此时相当进行一次完整的插入排序，得到最终结果{13,14,15,17,20,23,28,42}。

算法实现(C#)

// 希尔排序

public static void ShellSort(T[] array, C comparer)

where C : IComparer {

for (int i = array.Length / 2; i >= 1; i = i / 2) {

Console.Write(\"{0}: \", i); for (int j = 0; j < i; j++) {

InsertSort(array, j, i, comparer); }

Console.WriteLine();

AlgorithmHelper.PrintArray(array); } }

// 用于希尔排序的插入排序

private static void InsertSort

(T[] array, int startIndex, int step, C comparer)

where C : IComparer {

for (int i = startIndex + step; i <= array.Length - 1; i += step) { int j = i; while(j>= step &&

comparer.Compare(array[j], array[j - step]) <0 ){

swap(ref array[j], ref array[j - step]);

j -= step; } } }

注意这里插入排序InsertSort()方法的参数，startIndex是分组的起始索引，step是步长，可以看出，前面的插入排序只是此处step=1,startindex=0的一个特例。

输出演示(C#)

static void Main(string[] args) {

int[] array = {42,20,17,13,28,14,23,15}; AlgorithmHelper.PrintArray(array);

SortAlgorithm.ShellSort (array,

ComparerFactory.GetIntComparer()); }

算法实现(C++)

// 希尔排序

template

void ShellSort(T a[], int length){

for(int i = length/2; i >= 1; i = i/2 ){ for(int j = 0; jInsertSort(&a[j], length-1, i); } } }

// 用于希尔排序的插入排序 template

void InsertSort(T a[], int length, int step){

for(int i = step; iwhile(j>=step && C::Smaller(a[j], a[j-step])){

swap(a[j], a[j-step]); j-=step; } } }

2

对于上面三种算法的代价，插入排序、冒泡排序、选择排序，都是Θ(n)，而希尔排序略好一些，是Θ（n），关于算法分析，大家感兴趣可以参考相关书籍。这里推荐《数据结构与算法分析(C++版)第二版》和《算法I~IV（C++实现）——基础、数据结构、排序和搜索》，都很不错，我主要也是参考这两本书。

1.5