四种简单的排序算法.docx

四种简单的排序算法我觉得如果想成为一名优秀的开发者，不仅要积极学习时下流行的新技术，比如WCF、 Asp.NetMVC、AJAX等，熟练应用一些已经比较成熟的技术，比如Asp.Net、WinForm。还应 该有着牢固的计算机基础知识，比如数据结构、操作系统、编译原理、网络与数据通信等。 有的朋友可能觉得这方面的东西过于艰深和理论化，望而却步，但我觉得假日里花上一个下 午的时间，研究一种算法或者一种数据结构，然后写写心得，难道不是一件乐事么？所以， 我打算将一些常见的数据结构和算法总结一下，不一定要集中一段时间花费很大精力，只是 在比较空闲的时间用一种很放松的心态去完成。我最不愿意的，就是将写博客或者是学习技 术变为一项工作或者负担，应该将它们视为生活中的一种消遣。人们总是说坚持不易，实际 上当你提到“坚持”两个字之时，说明你已经将这件事视为了一种痛苦，你的内心深处并不 愿意做这件事，所以才需要坚持。你从不曾听人说“我坚持玩了十年的电子游戏”，或者“坚 持看了十年动漫、电影”、“坚持和心爱的女友相处了十年”吧？我从来不曾坚持，因为我 将其视为一个爱好和消遣，就像许多人玩网络游戏一样。好了，闲话就说这么多吧，我们回到正题。因为这方面的著作很多，所以这里只给出 简单的描述和实现，供我本人及感兴趣的朋友参考。我会尽量用C#和C+两种语言实现，对 于一些不好用C#表达的结构，仅用C+实现。本文将描述四种最简单的排序方法，插入排序、泡沫排序、选择排序、希尔排序，我 在这里将其称为“简单排序”，是因为它们相对于快速排序、归并排序、堆排序、分配排序、 基数排序从理解和算法上要简单一些。对于后面这几种排序，我将其称为“高级排序”。简单排序开始之前先声明一个约定，对于数组中保存的数据，统一称为记录，以避免和“元素”，“对象”等名称相混淆。对于一个记录，用于排序的码，称为关键码。很显然，关键码的选 择与数组中记录的类型密切相关，如果记录为int值，则关键码就是本身；如果记录是自定 义对象，它很可能包含了多个字段，那么选定这些字段之一为关键码。凡是有关排序和查找 的算法，就会关系到两个记录比较大小，而如何决定两个对象的大小，应该由算法程序的客 户端(客户对象)决定。对于.NET来说，我们可以创建一个实现了 IComparer<T >的类(对 于C+也是类似)。关于IComparer<T>的更多信息，可以参考这篇文章基于业务对象的排 序。最后，为了使程序简单，对于数组为空的情况我并没有做处理。1. 插入排序算法思想插入排序使用了两层嵌套循环，逐个处理待排序的记录。每个记录与前面已经排好序 的记录序列进行比较，并将其插入到合适的位置。假设数组长度为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#)publicclassSortAlgorithm /插入排序publicstaticvoid InsertSort<T, C>(T array, C comparer)where C:IComparer<T>for (int i = 1; i <= array.Length - 1; i+) /Console.Write("0: ", i);int j = i;while (j>=1 && comparer.Compare(arrayj, arrayj - 1) < 0) swap(ref arrayj, ref arrayj-1);j-;/Console.WriteLine();/AlgorithmHelper.PrintArray(array);/交换数组array中第i个元素和第j个元素privatestaticvoid swap<T>(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<T> ()方法则用于交换数组中的两 条记录，也对交换数进行了打印(这里我注释掉了，但在测试时可以取消对它们的注释)。 外层for循环控制变量i表示当前处理第i条记录。publicclassAlgorithmHelper /打印数组内容publicstaticvoid PrintArray<T>(T array) Console.Write(" Array:");foreach (T item in array) Console.Write(" 0”, item);555e。；获得,进行比较publicclassComparerFactory publicstatic IComparer<int> GetIntComparer() returnnew IntComparer();publicclassIntComparer : IComparer<int> publicint Compare(int x, int y) return x.CompareTo(y);上面这段代码我们创建了一个ComparerFactory类，它用于获得一个IntComparer对 象，这个对象实现了 IComparer<T>接口，规定了两个int类型的关键码之间比较大小的规 则。如果你有自定义的类型，比如叫MyType，只需要在ComparerFactory中再添加一个类， 比如叫MyTypeComparer，然后让这个类也实现IComparer<T>接口，最后再添加一个方法返 回 MyTypeComparer 就可以 了。输出演示(C#)接下来我们看一下客户端代码和输出：staticvoid 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：< C:VIflD0TS5y5teB32cBd. exe: 42 20 17 13 281： 20<>42: 2Q 42 17 13 282： 17<>42 17<>26: 17 26 42 13 2814143： 13<>42 13<>20 13<>1? Arra<；: 13 1? 20 42 2S 14 23 15 4： 28<>42 Arrai/: 13 1? 20 28 42 14 23 15 5： 14<>42 14<>28 14<>20 14<>17 drrAV: 13 14 17 26 2S 42 23 15 6： 23<>42 23<>28 Appai/: 13 14 17 20 23 28 42 157： 15<>42 15<>28 15<>23 15< >20 15<>17 : 13 14 15 17 20 23 28 42请按任意键继续-_Tn算法实现(C+)/对int类型进行排序class IntComparerpublic:static bool Smaller(int x, int y) return x<y;Ltic bool ,int y)( return x=y;static bool Larger(int x, int y) return x>y;:/插入排序template <class T, class C>void InsertSort(T a, int length)for(int i=1;i<=length-1;i+)int j = i;while(j>=1 && C:Smaller(aj, aj-1)swap(aj, aj-1);j-;2. 冒泡排序算法思想如果你从没有学习过有关算法方面的知识，而需要设计一个数组排序的算法，那么很 有可能设计出的就是泡沫排序算法了。因为它很好理解，实现起来也很简单。它也含有两层 循环，假设数组长度为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#)/泡沫排序publicstaticvoid BubbleSort<T, C>(T array, C comparer)where C : IComparer<T>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(arrayj, arrayj - 1) < 0) swap(ref arrayj, ref arrayj - 1);/Console.WriteLine();/AlgorithmHelper.PrintArray(array);输出演示(C#)staticvoid Main(string args) int array = 42,20,17,13,28,14,23,15;AlgorithmHelper.PrintArray(array);SortAlgorithm.BubbleSort(array, ComparerFactory.GetIntComparer();算法实现(C+)/冒泡排序template <class T, class C>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(aj, aj-1)swap(aj, aj-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#)publicstaticvoid SelectionSort<T, C>(T array, C comparer)where C : IComparer<T>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(arrayj, arraylowestIndex) < 0)lowestIndex = j;swap(ref arrayi, ref arraylowestIndex);AlgorithmHelper.PrintArray(array);输出演示(C#)staticvoid Main(string args) int array = 42,20,17,13,28,14,23,15;AlgorithmHelper.PrintArray(array);SortAlgorithm.SelectionSort(array, ComparerFactory.GetIntComparer();算法实现(C+)/选择排序template <class T, class C>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(aj, alowestIndex)lowestIndex = j;swap(ai, alowestIndex);4. 希尔排序希尔排序利用了插入排序的一个特点来优化排序算法，插入排序的这个特点就是：当数组基本有序的时候，插入排序的效率比较高。比如对于下面这样一个数组：可以看到，尽管比较的趟数没有减少，但是交换的次数却明显很少。希尔排序的总体想法就是先让数组基本有序，最后再应用插入排序。具体过程如下：假设有数组int a=42,20,17,13,28,14,23,15，不失一般性，我们设其长度为 length。int array = 1, 0, 2, 3, 5, 4, 8, 6, 7, 9 ;插入排序的输出如下:g C:VIflD0TSsy5teB32cBd. exeAffai/ : 0 12 3 47： 6<>85 86 7 9: 012348： 7<>85 6 8 7 95 6 7 8 9AFFai/: 0 12 3 4请按任意键继-: 10231： 0<>1G 7 9：0 1 2 35 4 86 7 9Array J .k:Appal/：0 1 2 3 423548679Arra<；: 0 1 2 3 5 4 85： 4<>56 ? 9Array：0 1 2 3 45 86 ? 9第一趟时，步长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)，所以这两个记录在原数组的下标 分别为 a1=14;a5=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,4213,14,15,20。此时数组就成了 17,13,23,14,28,15,42,20，已经基本有序。第三趟时，步长step=step/2 = 1，此时相当进行一次完整的插入排序，得到最终结 果13,14,15,17,20,23,28,42。算法实现(C#)/希尔排序publicstaticvoid ShellSort<T, C>(T array, C comparer)where C : IComparer<T>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);/用于希尔排序的插入排序privatestaticvoid InsertSort<T, C>(T array, int startindex, int step, C comparer)where C : IComparer<T>for (int i = startindex + step; i <= array.Length - 1; i += step) int j = i;while(j>= step && comparer.Compare(arrayj, arrayj - step) <0 ) swap(ref arrayj, ref arrayj - step);j -= step;注意这里插入排序InsertSort()方法的参数，startindex是分组的起始索引，step 是步长，可以看出，前面的插入排序只是此处step=1,startindex=0的一个特例。输出演示(C#)staticvoid Main(string args) int array = 42,20,17,13,28,14,23,15;AlgorithmHelper.PrintArray(array);SortAlgorithm.ShellSort(array, ComparerFactory.GetIntComparer();应 C:VIflD0TSsy5teB32cBd. exe : 42 20 17 28<>42 14<>20 : 28 14 17 17<>28 23<>42 23<>2B 13<>14 15<>20 Arra<；: 17 13 23 13<>17 14<>23 14<>17 15<>28 15<>23 15<>17 20<>42 20<>28 20<>23 : 13 14 15 请按任意键继续 13 28 14 23 1513 42 20 23 1514 28 15 42 2&17 20 23 28 42算法实现(C+)/希尔排序template<class T, class C>void ShellSort(T a, int length) for(int i = length/2; i >= 1; i = i/2 ) for(int j = 0; j<i; j+) InsertSort<T, C>(&aj, length-1, i); /用于希尔排序的插入排序template<class T, class C>void InsertSort(T a, int length, int step)for(int i = step; i<length; i+= step)int j = i;while（j>=step && C:Smaller（aj, aj-step）swap（aj, aj-step）;j-=step;对于上面三种算法的代价，插入排序、冒泡排序、选择排序，都右（皿），而希尔排序 略好一些，是。（m.5），关于算法分析，大家感兴趣可以参考相关书籍。这里推荐数据 结构与算法分析（C+版）第二版和算法IIV（C+实现）一一基础、数据结构、排序和 搜索，都很不错，我主要也是参考这两本书。