基础算法学习——排序算法概述

kon3155

本主题内容多来自维基百科，更多更全更权威请见英文版 http://en.wikipedia.org/wiki/Sorting_algorithm 排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。 插入排序 O(n²) 冒泡排序 O(n²) 选择排序 O(n²) 快速排序 O(n log n) 堆排序 O(n log n) 归并排序 O(n log n) 基数排序 O(n) 希尔排序 O(n^1.25)?

kon3155

【算法描述】 一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下： 从第一个元素开始，该元素可以认为已经被排序 取出下一个元素，在已经排序的元素序列中从后向前扫描 如果该元素（已排序）大于新元素，将该元素移到下一位置 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置中 重复步骤2 如果比较操作的代价比交换操作大的话，可以采用二分查找法来减少比较操作的数目。该算法可以认为是插入排序的一个变种，称为二分查找排序。 【示例代码】 示例代码为C语言，输入参数中，需要排序的数组为array[],起始索引为first，终止索引为last。示例代码的函数采用in-place排序，调用完成后，array[]中从first到last处于升序排列。

1. void insertion_sort(char array[], unsigned int first, unsigned int last)
2. {
3. int i,j;
4. int temp;
5. for (i = first+1; i<=last;i++)
6. {
7. temp = array[i];
8. j=i-1;
10. //与已排序的数逐一比较，大于temp时，该数移后
11. while((j>=first) && (array[j] > temp))
12. {
13. array[j+1] = array[j];
14. j--;
15. }
17. array[j+1] = temp;
18. }
19. }

复制代码

这个更好:

1. void InsertSort(char array[],unsigned int n)
2. {
3. int i,j;
4. int temp;
5. for(i=1;i<n;i++)
6. {
7. temp = array[i];//store the original sorted array in temp
8. for(j=i ; j>0 && temp < array[j-1] ; j--)//compare the new array with temp
9. {
10. array[j]=array[j-1];//all larger elements are moved one pot to the right
11. }
12. array[j]=temp;
13. }
14. }

复制代码

这个是c++语言版本的插入排序。为了支持list使用了std::advance()。

1. #include <iterator>
3. template<typename biIter>
4. void insertion_sort(biIter begin, biIter end)
5. {
6. typedef typename std::iterator_traits<biIter>::value_type value_type;
7. biIter bond = begin;
8. std::advance(bond, 1);
9. for(; bond!=end; std::advance(bond, 1)) {
10. value_type key = *bond;
11. biIter ins = bond;
12. biIter pre = ins;
13. std::advance(pre, -1);
14. while(ins!=begin && *pre>key) {
15. *ins = *pre;
16. std::advance(ins, -1);
17. std::advance(pre, -1);
18. }
19. *ins = key;
20. }
21. }

复制代码

【算法复杂度】 如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小，例如，量级小于千，那么插入排序还是一个不错的选择。

kon3155

冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个项目，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 冒泡排序对n个项目需要O(n2)的比较次数，且可以原地排序。尽管这个算法是最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。 冒泡排序是与插入排序拥有相等的执行时间，但是两种法在需要的交换次数却很大地不同。在最坏的情况，冒泡排序需要O(n2)次交换，而插入排序只要最多O(n)交换。天真的冒泡排序实作（类似下面）通常会对已经排序好的数列拙劣地执行（O(n2)），而插入排序在这个例子只需要O(n)个运算。因此很多现代的算法教科书避免使用冒泡排序，而用插入排序取代之。冒泡排序如果能在内部回圈第一次执行时，使用一个旗标来表示有无需要交换的可能，也有可能把最好的复杂度降低到O(n)。在这个情况，在已经排序号的数列就无交换的需要。若在每次走访数列时，把走访顺序和比较大小反过来，也可以些微地改进效率。有时候称为往返排序（en:shuttle sort），因为算法会从数列的一端到另一端之间穿梭往返。 冒泡排序算法的运作如下： 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。 由于它的简洁，冒泡排序通常被用来对于程式设计入门的学生介绍算法的概念。 【伪码】

1. function bubblesort (A : list[1..n]) {
2. var int i, j;
3. for i from n downto 1 {
4. for j from 1 to i-1 {
5. if (A[j] > A[j+1])
6. swap(A[j], A[j+1])
7. }
8. }
9. }

复制代码

【Pascal码】 使用标志的冒泡排序 输入：（在程式同目录下的文本文件：input.txt） 　一行：等待排序的数（用空格隔开）； 　实例：194 638 124 482 469 245 852 294 484 243 623 输出：（在程式同目录下的文本文件：output.txt） 　一行：已经排好的数（从小到大）； 　实例：124 194 243 245 294 469 482 484 623 638 852 Free PASCAL 2.1.4 下通过编译；

1. Program Bubble_sort;
3. const
4. infile='input.txt';
5. outfile='output.txt';
6. maxn=100; //這是數字的最大個數，可以更改
8. var
9. n:longint;
10. a:array[1..maxn] of longint;
12. procedure init; //讀入部分
13. begin
14. assign(input,infile);
15. reset(input);
16. n:=0;
17. while not(eoln) do begin
18. inc(n);
19. read(a[n]);
20. end;
21. readln;
22. close(input);
23. end;
25. procedure print; //輸出部分
26. var
27. i:longint;
28. begin
29. assign(output,outfile);
30. rewrite(output);
31. for i:=1 to n do write(a[i],' ');
32. writeln;
33. close(output);
34. end;
36. procedure swap(j:longint); //交換過程
37. begin
38. a[j]:=a[j] xor a[j+1];
39. a[j+1]:=a[j] xor a[j+1];
40. a[j]:=a[j] xor a[j+1];
41. end;
43. procedure bubble_sort; //排序過程
44. var
45. i,j:longint;
46. flag:boolean; //flag標志：若一次排序未發現數據交換，則說明數據已經有序，可以結束排序過程
47. begin
48. for i:=n-1 downto 1 do begin
49. flag:=true;
50. for j:=1 to i do begin
51. if a[j]>a[j+1] then begin
52. swap(j);
53. flag:=false;
54. end;
55. end;
56. if flag then exit;
57. end;
58. end;
60. {======MAIN======}
62. begin
63. init;
64. bubble_sort;
65. print;
66. end.

复制代码

【 PHP 源码】

1. function bubble_sort($array){
2. $count = count($array);
3. if ($count <= 0) return false;
4. for($i=0; $i<$count; $i++){
5. for($j=$count-1; $j>$i; $j–){
6. if ($array[$j] < $array[$j-1]){
7. $tmp = $array[$j];
8. $array[$j] = $array[$j-1];
9. $array[$j-1] = $tmp;
10. }
11. }
12. }
13. return $array;
14. }

复制代码

[ 本帖最后由 kon3155 于 2009-2-26 17:22 编辑 ]

kon3155

选择排序（Selection Sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。

1. // selection sort function module in C
2. void selectionSort(int data[], int count)
3. {
4. int i, j, min, temp;
5. for (i = 0; i < count - 1; i++) {
6. /* find the minimum */
7. min = i;
8. for (j = i+1; j < count; j++) {
9. if (data[j] < data[min]) {
10. min = j;
11. }
12. }
13. /* swap data[i] and data[mi] */
14. temp = data[i];
15. data[i] = data[min];
16. data[min] = temp;
17. }
18. }

复制代码

【复杂度分析】 选择排序的交换操作介于0和(n-1)次之间。 选择排序的比较操作为n(n-1)/2次之间。 选择排序的赋值操作介于0和3(n-1)次之间。 平均复杂度:Ο(n²)

kon3155

快速排序（Quicksort）是一种众所周知的排序算法，由C. A. R. Hoare所发展的，以平均效能来说，排序 n 个项目要Θ(n log n)次比较。然而，在最坏的效能下，它需要Θ(n2)次比较。一般来说，快速排序实际上明显地比其他Θ(n log n) 算法更快，因为它的内部回圈（inner loop）可以在大部分的架构上很有效率地被实作出来，且在大部分真实世界的资料，可以决定设计的选择，减少所需时间的二次方项之可能性。 【算法】 快速排序是一种“分而治之、各个击破”的观念。快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。 步骤为： 从数列中挑出一个元素，称为 "基准"（pivot）， 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。 在简单的虚拟码中，算法可以被表示为：

1. function quicksort(q)
2. var list less, pivotList, greater
3. if length(q) ≤ 1 {
4. return q
5. } else {
6. select a pivot value pivot from q
7. for each x in q except the pivot element
8. if x < pivot then add x to less
9. if x ≥ pivot then add x to greater
10. add pivot to pivotList
11. return concatenate(quicksort(less), pivotList, quicksort(greater))
12. }

复制代码

原地(in-place)分割的版本 上面简单版本的缺点是，它需要Ω(n)的额外储存空间，也就跟归并排序一样不好。额外需要的内存空间配置，在实际上的实作，也会极度影响速度和快取的效能。有一个比较复杂使用原地（in-place）分割算法的版本，且在好的基准选择上，平均可以达到O(log n)空间的使用复杂度。

1. function partition(a, left, right, pivotIndex)
2. pivotValue := a[pivotIndex]
3. swap(a[pivotIndex], a[right]) // 把 pivot 移到結尾
4. storeIndex := left
5. for i from left to right-1
6. if a[i] <= pivotValue
7. swap(a[storeIndex], a[i])
8. storeIndex := storeIndex + 1
9. swap(a[right], a[storeIndex]) // 把 pivot 移到它最後的地方
10. return storeIndex

复制代码

这是原地分割算法，它分割了标示为 "左边（left）" 和 "右边（right）" 的序列部份，借由移动小于a[pivotIndex]的所有元素到子序列的开头，留下所有大于或等于的元素接在他们后面。在这个过程它也为基准元素找寻最后摆放的位置，也就是它回传的值。它暂时地把基准元素移到子序列的结尾，而不会被前述方式影响到。由于算法只使用交换，因此最后的数列与原先的数列拥有一样的元素。要注意的是，一个元素在到达它的最后位置前，可能会被交换很多次。 一旦我们有了这个分割算法，要写快速排列本身就很容易：

1. function quicksort(a, left, right)
2. if right > left
3. select a pivot value a[pivotIndex]
4. pivotNewIndex := partition(a, left, right, pivotIndex)
5. quicksort(a, left, pivotNewIndex-1)
6. quicksort(a, pivotNewIndex+1, right)

复制代码

这个版本经常会被使用在命令式语言中，像是C语言。 【竞争的排序算法】 快速排序是二叉查找树（二叉查找树）的一个空间最佳化版本。不以循序地把项目插入到一个明确的树中，而是由快速排序组织这些项目到一个由递回呼叫所意含的树中。这两个算法完全地产生相同的比较次数，但是顺序不同。 快速排序的最直接竞争者是堆排序（Heapsort）。堆排序通常比快速排序稍微慢，但是最坏情况的执行时间总是O(n log n)。快速排序是经常比较快，除了introsort变化版本外，仍然有最坏情况效能的机会。如果事先知道堆排序将会是需要使用的，那么直接地使用堆排序比等待 introsort 再切换到它还要快。堆排序也拥有重要的特点，仅使用固定额外的空间（堆排序是原地排序），而即使是最佳的快速排序变化版本也需要Θ(log n)的空间。然而，堆排序需要有效率的随机存取才能变成可行。 快速排序也与归并排序（Mergesort）竞争，这是另外一种递回排序算法，但有坏情况O(n log n)执行时间的优势。不像快速排序或堆排序，归并排序是一个稳定排序，且可以轻易地被采用在链串行（linked list）和储存在慢速存取媒体上像是磁盘储存或网络连接储存的非常巨大数列。尽管快速排序可以被重新改写使用在链串行上，但是它通常会因为无法随机存取而导致差的基准选择。归并排序的主要缺点，是在最佳情况下需要Ω(n)额外的空间。 【正规的分析】 从一开始快速排序平均需要花费O(n log n)时间的描述并不明显。但是不难观察到的是分割运算，阵列的元素都会在每次循环中走访过一次，使用Θ(n)的时间。在使用结合（concatenation）的版本中，这项运算也是Θ(n)。 在最好的情况，每次我们执行一次分割，我们会把一个数列分为两个几近相等的片段。这个意思就是每次递回呼叫处理一半大小的数列。因此，在到达大小为一的数列前，我们只要作 log n 次巢状的呼叫。这个意思就是呼叫树的深度是O(log n)。但是在同一阶层的两个程序呼叫中，不会处理到原来数列的相同部份；因此，程序呼叫的每一阶层总共全部仅需要O(n)的时间（每个呼叫有某些共同的额外耗费，但是因为在每一阶层仅仅只有O(n)个呼叫，这些被归纳在O(n)系数中）。结果是这个算法仅需使用O(n log n)时间。 另外一个方法是为T(n)设立一个递回关系式，也就是需要排序大小为n的数列所需要的时间。在最好的情况下，因为一个单独的快速排序呼叫牵涉了O(n)的工作，加上对n/2大小之数列的两个递回呼叫，这个关系式可以是： T(n) = O(n) + 2T(n/2) 解决这种关系式型态的标准数学归纳法技巧告诉我们T(n) = Θ(n log n)。 事实上，并不需要把数列如此精确地分割；即使如果每个基准值将元素分开为 99% 在一边和 1% 在另一边，呼叫的深度仍然限制在 100log n，所以全部执行时间依然是O(n log n)。 然而，在最坏的情况是，两子数列拥有大各为 1 和 n-1，且呼叫树（call tree）变成为一个 n 个巢状（nested）呼叫的线性连串（chain）。第 i 次呼叫作了O(n-i)的工作量，且递回关系式为： T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1) 这与插入排序和选择排序有相同的关系式，以及它被解为T(n) = Θ(n2)。 【乱数快速排序的期望复杂度】 不管输入怎样下，乱数快速排序拥有得当的特性，也就是它只需要O(n log n)期望的时间。是什么让随机的基准变成一个好的选择？ 假设我们排序一个数列，然后把它分为四个部份。在中央的两个部份将会包含最好的基准值；他们的每一个至少都会比25%的元素大，且至少比25%的元素小。如果我们可以一致地从这两个中央的部份选出一个元素，在到达大小为1的数列前，我们可能最多仅需要把数列分割2log2 n次，产生一个 O(nlogn)算法。 不幸地，乱数选择只有一半的时间会从中间的部份选择。出人意外的事实是这样就已经足够好了。想像你正在翻转一枚硬币，一直翻转一直到有 k 次人头那面出现。尽管这需要很长的时间，平均来说只需要 2k 次翻动。且在 100k 次翻动中得到 k 次人头那面的机会，是像天文数字一样的非常小。借由同样的论证，快速排序的递回平均只要2(2log2 n)的呼叫深度就会终止。但是如果它的平均呼叫深度是O(log n)且每一阶的呼叫树状过程最多有 n 个元素，则全部完成的工作量平均上是乘积，也就是 O(n log n)。 【平均复杂度】 即使如果我们无法随机地选择基准数值，对于它的输入之所有可能排列，快速排序仍然只需要O(n log n)时间。因为这个平均是简单地将输入之所有可能排列的时间加总起来，除以n这个因子，相当于从输入之中选择一个随机的排列。当我们这样作，基准值本质上就是随机的，导致这个算法与乱数快速排序有一样的执行时间。 更精确地说，对于输入顺序之所有排列情形的平均比较次数，可以借由解出这个递回关系式可以精确地算出来。 在这里，n-1 是分割所使用的比较次数。因为基准值是相当均匀地落在排列好的数列次序之任何地方，总和就是所有可能分割的平均。 这个意思是，平均上快速排序比理想的比较次数，也就是最好情况下，只大约比较糟39%。这意味着，它比最坏情况较接近最好情况。这个快速的平均执行时间，是快速排序比其他排序算法有实际的优势之另一个原因。 【空间复杂度】 被快速排序所使用的空间，依照使用的版本而定。使用原地（in-place）分割的快速排序版本，在任何递回呼叫前，仅会使用固定的額外空間。然而，如果需要产生O(log n)巢状递回呼叫，它需要在他们每一个储存一个固定数量的资讯。因为最好的情况最多需要O(log n)次的巢状递回呼叫，所以它需要O(log n)的空间。最坏情况下需要O(n)次巢状递回呼叫，因此需要O(n)的空间。 然而我们在这里省略一些小的细节。如果我们考虑排序任意很长的数列，我们必须要记住我们的变量像是left和right，不再被认为是占据固定的空间；也需要O(log n)对原来一个n项的数列作索引。因为我们在每一个堆栈框架中都有像这些的变量，实际上快速排序在最好跟平均的情况下，需要O(log2 n)空间的位元数，以及最坏情况下O(n log n)的空间。然而，这并不会太可怕，因为如果一个数列大部份都是不同的元素，那么数列本身也会占据O(n log n)的空间字节。 非原地版本的快速排序，在它的任何递回呼叫前需要使用O(n)空间。在最好的情况下，它的空间仍然限制在O(n)，因为递回的每一阶中，使用与上一次所使用最多空间的一半，且 它的最坏情况是很恐怖的，需要 空间，远比数列本身还多。如果这些数列元素本身自己不是固定的大小，这个问题会变得更大；举例来说，如果数列元素的大部份都是不同的，每一个将会需要大约O(log n)为原来储存，导致最好情况是O(n log n)和最坏情况是O(n2 log n)的空间需求。 【选择的关连性】 选择算法（selection algorithm）可以选取一个数列的第k个最小值；一般而言这是比排序还简单的问题。一个简单但是有效率的选择算法与快速排序的作法相当类似，除了对两个子数列都作递回呼叫外，它仅仅针对包含想要的元素之子数列作单一的结尾递回（tail recursive）呼叫。这个小改变降低了平均复杂度到线性或是Θ(n)时间，且让它成为一个原地算法。这个算法的一种变化版本，可已让最坏情况下降为O(n)（参考选择算法来得到更多资讯）。 相反地，一旦我们知道一个最坏情况的O(n)选择算法是可以利用的，我们在快速排序的每一步可以用它来找到理想的基准（中位数），得到一种最化情况下O(n log n)执行时间的变化版本。在实际的实作，然而这种版本一般而言相当的慢。 【代码模板】见楼下

kon3155

【快速排序代码模板】 【C】 排序一个整数的阵列

1. void swap(int *a, int *b)
2. {
3. int t=*a; *a=*b; *b=t;
4. }
6. void quicksort(int arr[],int beg,int end)
7. {
8. if (end >= beg + 1)
9. {
10. int piv = arr[beg], k = beg + 1, r = end;
12. while (k < r)
13. {
14. if (arr[k] < piv)
15. k++;
16. else
17. swap(&arr[k], &arr[r--]);
18. }
19. if (arr[k] < piv){
21. swap(&arr[k],&arr[beg]);
23. quicksort(arr, beg, k);
24. quicksort(arr, r, end);
25. }else {
26. if (end - beg == 1)
27. return;
29. swap(&arr[--k],&arr[beg]);
30. quicksort(arr, beg, k);
31. quicksort(arr, r, end);
32. }
33. }
35. }

复制代码

【C++】 这是一个使用标准模版库（STL）的泛型式快速排序版本。

2. #include <functional>
3. #include <algorithm>
4. #include <iterator>
6. template< typename BidirectionalIterator, typename Compare >
7. void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare cmp ) {
8. if( first != last ) {
9. BidirectionalIterator left = first;
10. BidirectionalIterator right = last;
11. BidirectionalIterator pivot = left++;
13. while( left != right ) {
14. if( cmp( *left, *pivot ) ) {
15. ++left;
16. } else {
17. while( (left != right) && cmp( *pivot, *right ) )
18. right--;
19. std::iter_swap( left, right );
20. }
21. }
23. if cmp( *pivot, *left )
24. --left;
25. std::iter_swap( first, left );
27. quick_sort( first, left, cmp );
28. quick_sort( right, last, cmp );
29. }
30. }
32. template< typename BidirectionalIterator >
33. inline void quick_sort( BidirectionalIterator first, BidirectionalIterator last ) {
34. quick_sort( first, last,
35. std::less_equal< typename std::iterator_traits< BidirectionalIterator >::value_type >()
36. );
37. }

复制代码

【Java】

1. import java.util.Comparator;
2. import java.util.Random;
4. public class Quicksort {
5. public static final Random RND = new Random();
7. private void swap(Object[] array, int i, int j) {
8. Object tmp = array[i];
9. array[i] = array[j];
10. array[j] = tmp;
11. }
13. private int partition(Object[] array, int begin, int end, Comparator cmp) {
14. int index = begin + RND.nextInt(end - begin + 1);
15. Object pivot = array[index];
16. swap(array, index, end);
17. for (int i = index = begin; i < end; ++ i) {
18. if (cmp.compare(array[i], pivot) <= 0) {
19. swap(array, index++, i);
20. }
21. }
22. swap(array, index, end);
23. return (index);
24. }
26. private void qsort(Object[] array, int begin, int end, Comparator cmp) {
27. if (end > begin) {
28. int index = partition(array, begin, end, cmp);
29. qsort(array, begin, index - 1, cmp);
30. qsort(array, index + 1, end, cmp);
31. }
32. }
34. public void sort(Object[] array, Comparator cmp) {
35. qsort(array, 0, array.length - 1, cmp);
36. }
37. }

复制代码

【C#】

1. public static void Sort(int[] numbers)
2. {
3. Sort(numbers, 0, numbers.Length - 1);
4. }
6. private static void Sort(int[] numbers, int left, int right)
7. {
8. if (left < right)
9. {
10. int middle = numbers[(left + right) / 2];
11. int i = left - 1;
12. int j = right + 1;
13. while (true)
14. {
15. while (numbers[++i] < middle) ;
17. while (numbers[--j] > middle) ;
19. if (i >= j)
20. break;
22. Swap(numbers, i, j);
23. }
25. Sort(numbers, left, i - 1);
26. Sort(numbers, j + 1, right);
27. }
28. }
30. private static void Swap(int[] numbers, int i, int j)
31. {
32. int number = numbers[i];
33. numbers[i] = numbers[j];
34. numbers[j] = number;
35. }

复制代码

kon3155

积排序（Heap Sort）是指利用堆积树（堆, heaps tree）这种数据结构所设计的一种排序算法。堆积树是一个近似完整二叉树的结构，并同时满足堆积属性：即子结点的键值或索引总是小于（或者大于）它的父结点。 【堆积树节点的访问】 通常堆积树(heap)是通过一维阵列来实现的。 在起始阵列为0的情形中: 堆积树的根节点（即堆积树的最大值）存放在阵列位置0的地方 节点i的左子节点在位置（2*i+1） 节点i的右子节点在位置（2*i+2） 节点i的父节点在位置floor((i-1)/2) 【堆积树的操作】 在堆积树的数据结构中，堆积树中的最大值总是位于根节点。堆积树中定义以下几种操作操作： 最大堆积调整（Max_Heapify）：将堆积树的末端子结点作调整,使的子结点永远小于父结点 建立最大堆积（Build_Max_Heap）：将堆积树所有数据重新排序 堆积排序（HeapSort）：移除位在第一个数据的根结点,并做最大堆积调整的递归运算 【阵列堆积排序】

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<math.h>
4. #define HEAP_SIZE 13 //堆積樹大小
5. int parent(int i);
6. int left(int i);
7. int right(int i);
8. void Max_Heapify(int A[],int i,int heap_size);
9. void Build_Max_Heap(int A[]);
10. void print(int A[]);
11. void HeapSort(int A[],int heap_size);
12. /*父結點*/
13. int parent(int i)
14. {
15. return (int)floor(i/2);
16. }
17. /*左子結點*/
18. int left(int i)
19. {
20. return 2*i;
21. }
22. /*右子結點*/
23. int right(int i)
24. {
25. return 2*i+1;
26. }
27. /*單一子結點最大堆積樹調整*/
28. void Max_Heapify(int A[],int i,int heap_size)
29. {
30. int l=left(i);
31. int r=right(i);
32. int largest;
33. int temp;
34. if(l<heap_size&&A[l]>A[i])
35. {
36. largest=l;
37. }
38. else
39. {
40. largest=i;
41. }
42. if(r<heap_size&&A[r]>A[largest])
43. {
44. largest=r;
45. }
46. if(largest!=i)
47. {
48. temp=A[i];
49. A[i]=A[largest];
50. A[largest]=temp;
51. Max_Heapify(A,largest,heap_size);
52. }
53. }
54. /*建立最大堆積樹*/
55. void Build_Max_Heap(int A[])
56. {
57. for(int i=HEAP_SIZE;i>=1;i--)
58. {
59. Max_Heapify(A,i,HEAP_SIZE);
60. }
61. }
62. /*印出樹狀結構*/
63. void print(int A[])
64. {
65. for(int i=0;i<HEAP_SIZE;i++)
66. {
67. printf("%d ",A[i]);
68. }
69. printf("\n");
70. }
71. /*堆積排序程式碼*/
72. void HeapSort(int A[],int heap_size)
73. {
74. Build_Max_Heap(A);
76. int temp;
77. for(int i=heap_size-1;i>=2;i--)
78. {
79. temp=A[1];
80. A[1]=A[i];
81. A[i]=temp;
82. heap_size=heap_size-1;
83. Max_Heapify(A,1,heap_size);
84. }
85. print(A);
86. }
87. /*輸入資料並做堆積排序*/
88. int main()
89. {
90. int A[HEAP_SIZE]={0,1,10,14,16,4,7,9,3,2,8,5,11};
91. HeapSort(A,HEAP_SIZE);
94. system("pause");
95. }

复制代码

【其他程式码】 示例代码为C语言，堆的结构采用阵列实现，起始索引为0。

1. #define MAX_HEAP_LEN 100
2. static int heap[MAX_HEAP_LEN];
3. static int heap_size = 0; // the number of elements in heaps
5. static void swap(int* a, int* b)
6. {
7. int temp = 0;
8. temp = *b;
9. *b = *a;
10. *a = temp;
11. }
13. static void sift_up(int i)
14. {
15. int done = 0;
16. if( i == 0) return; //node is the root already
17. while((i!=0)&&(!done))
18. {
19. if(heap[i] > heap[(i-1)/2])
20. {//if the current is larger than the parent, then swap
21. swap(&heap[i],&heap[(i-1)/2]);
22. }
23. else
24. {// the job is already done.
25. done =1;
26. }
27. i = (i-1)/2;
28. }
29. }
31. static void sift_down(int i)
32. {
33. int done = 0;
34. if (2*i + 1> heap_size) return; // node i is a leaf
36. while((2*i+1 < heap_size)&&(!done))
37. {
38. i =2*i+1; // jump to left child
39. if ((i+1< heap_size) && (heap[i+1] > heap[i]))
40. {// find the bigger one of the two children
41. i++;
42. }
43. if (heap[(i-1)/2] < heap[i])
44. {
45. swap(&heap[(i-1)/2], &heap[i]);
46. }
47. else
48. {
49. done = 1;
50. }
51. }
52. }
54. static void delete(int i)
55. {
56. int current = heap[i]; // the one to be deleted
57. int last = heap[heap_size - 1]; // get the last one;
58. heap_size--; // shrink the heap
59. if (i == heap_size) return;
60. heap[i] = last; // use the last item to overwrite the current
61. if(last >= current)
62. sift_up(i);
63. else
64. sift_down(i);
65. }
67. int delete_max()
68. {
69. int ret = heap[0];
70. delete(0);
71. return ret;
72. }
74. void insert(int new_data)
75. {
76. if(heap_size >= MAX_HEAP_LEN) return;
77. heap_size++;
78. heap[heap_size - 1] = new_data;
79. sift_up(heap_size - 1);
80. }

复制代码

【in-place堆排序】 基于以上堆相关的操作，我们可以很容易的定义堆排序。例如，假设我们已经读入一系列数据并创建了一个堆，一个最直观的算法就是反复的调用del_max()函数，因为该函数总是能够返回堆中最大的值，然后把它从堆中删除，从而对这一系列返回值的输出就得到了该序列的降序排列。真正的in-place的堆排序使用了另外一个小技巧。对排序的过程是： 建立一个堆H[0..n-1] 把堆首（最大值）和堆尾互换 把堆的尺寸缩小1，并调用sift_down(0),目的是把新的数组顶端数据调整到相应位置 重复2号步骤，直到堆的尺寸为1 【平均复杂度】 堆排序的平均时间复杂度为O(n log n)，空间复杂度为Θ (1)。

kon3155

归并排序（Merge Sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。 【归并操作】 归并操作(merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。 【算法描述】 归并操作的工作原理如下： 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 设定两个指针，最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针达到序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 【示例代码】 以下示例代码实现了归并操作。array[]是元素序列，其中从索引p开始到q位置，按照升序排列，同时，从(q+1)到r也已经按照升序排列，merge()函数将把这两个已经排序好的子序列合并成一个排序序列。结果放到array中。

1. /**
2. * 0 <= p <= q < r, subarray array[p..q] and array[q+1..r] are already sorted.
3. * the merge() function merges the two sub-arrays into one sorted array.
4. */
6. static void merge(int array[], int p, int q, int r)
7. {
8. int i,k;
9. int begin1,end1,begin2,end2;
10. int* temp = (int*)malloc((r-p+1)*sizeof(int));
11. begin1= p; end1 = q;
12. begin2 = q+1; end2 = r;
14. k = 0;
15. while((begin1 <= end1)&&( begin2 <= end2))
16. {
17. if(array[begin1]<array[begin2])
18. {
19. temp[k] = array[begin1]; begin1++;
20. }
21. else
22. {
23. temp[k] = array[begin2]; begin2++;
24. }
25. k++;
26. }
28. while(begin1<=end1)
29. {
30. temp[k++] = array[begin1++];
31. }
32. while(begin2<=end2)
33. {
34. temp[k++] = array[begin2++];
35. }
36. for (i = 0; i < (r - p +1); i++)
37. array[p+i] = temp[i];
38. free(temp);
39. }

复制代码

【Java 语言】

1. public int[] Two_Way_Merge_Sort(int[] A, int[] B) {
2. int[] C = new int[A.length + B.length];
3. int k = 0;
4. int i = 0;
5. int j = 0;
6. while(i < A.length && j < B.length) {
7. if (A[i] < B[j])
8. C[k++] = A[i++];
9. else
10. C[k++] = B[j++];
11. }
12. while (i < A.length)
13. C[k++] = A[i++];
14. while (j < B.length)
15. C[k++] = B[j++];
16. return C;
17. }
18. }

复制代码

【算法复杂度】 比较操作的次数介于(nlogn) / 2和nlogn − n + 1。 赋值操作的次数是(2nlogn)。 归并算法的空间复杂度为：Θ (n)

kon3155

基数排序（Radix Sort）是一种排序算法，它是这样实现的： 假设需排序数列的取值范围从1...k,我们于是建一个K+1元的数组 a[]，并赋初值为0，然后便开始排序工作： 按输入顺序读入数列，如果所读的元素为i(1<=i<=k),我们就将a[i]的值加一，这样直到读完所有的元素。 读出元素并排序：我们遍历整个数组，如果a[i]=j(j>=0),我们就输出j次i(表示元素i在原先数列中出现了j次),这样输出的序列就是已排序的。 由于一般排序算法涉及到元素之间的比较，如果化成比较树可以知道，这样的排序算法复杂度的下限是O(N*lnN),而计数排序没有比较元素，所以所需排序时间就少了，我们可以看到计数排序的复杂度为O(n+k)，其中k（k的定义同上）为合并排列所需的时间，是个常数。 此算法适合所需排列的元素取值范围不大的情况下，否则会造成空间的消耗，比如，一共100个元素，其取值范围从1-100000，显然这个时候用基数排序是不合适的。

kon3155

希尔排序(Shell Sort)也称为递减增量排序算法，是插入排序的一种高速而安定的改良版。因希尔(Donald L. Shell)于1959年提出而得名。各种实现在如何进行递减上有所不同。 希尔排序是基于插入排序的以下两点性质而提出改进方法的： 插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率 但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位 对有n个元素的可比较资料，先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2

1. template<typename RandomIter, typename Compare>
2. void shell_sort(RandomIter begin, RandomIter end, Compare cmp)
3. {
4. typedef typename std::iterator_traits<RandomIter>::value_type value_type;
5. typedef typename std::iterator_traits<RandomIter>::difference_type diff_t;
7. diff_t size = std::distance(begin, end);
8. diff_t step = size / 2;
9. while(step >= 1) {
10. for(diff_t i=step; i<size; ++i) {
11. value_type key = *(begin+i);
12. diff_t ins = i;
13. while(ins>=step && cmp(key, *(begin+ins-step)) ) {
14. *(begin+ins) = *(begin+ins-step);
15. ins -= step;
16. }
17. *(begin+ins) = key;
18. }
19. if(step == 2)
20. step = 1;
21. else
22. step = static_cast<diff_t>(step / 2.2);
23. }
24. }
26. template<typename RandomIter>
27. void shell_sort(RandomIter begin, RandomIter end) {
28. typedef typename std::iterator_traits<RandomIter>::value_type value_type;
29. shell_sort(begin, end, std::less<value_type>() );
30. }

复制代码【Code Sample in C】

1. int main()
2. {
3. const int n = 5;
4. int i, j, gap, temp;
5. int a[] = {5, 4, 3, 2, 1};
6. gap = n / 2;
7. while (gap > 0)
8. {
9. for ( i = gap; i < n; i++ )
10. {
11. j = i - gap;
12. temp = a[i];
13. while (( j >= 0 ) && ( a[j] > temp ))
14. {
15. a[j + gap] = a[j];
16. j = j - gap;
17. }
18. a[j + gap] = temp;
19. }
20. gap = gap / 2;
21. }
22. }

复制代码

【 Code Sample in Java】

1. void shellsort (int[] a, int n)
2. {
3. int i, j, k, temp, gap;
4. int[] gaps = { 1,5,13,43,113,297,815,1989,4711,11969,27901,84801,
5. 213331,543749,1355339,3501671,8810089,21521774,
6. 58548857,157840433,410151271,1131376761,2147483647 };
7. for (k=0; gaps[k]<n; k++) ;
8. while (--k >= 0)
9. {
10. gap = gaps[k];
11. for (i=gap; i<n; i++)
12. {
13. temp = a[i];
14. j = i;
15. while (j>=gap && a[j-gap]>temp)
16. {
17. a[j] = a[j-gap];
18. j = j-gap;
19. }
20. a[j] = temp;
21. }
22. }
23. }

复制代码