//为在玉树地震中逝去的人们表示沉痛的哀悼。。。。。1 #include "stdafx.h"
2
3 /*
4 ================================================
5 功能：快速排序
6 输入：数组名称（也就是数组首地址）、数组中起止元素的下标
7 ================================================
8 */
9 /*
10 ====================================================
11 算法思想简单描述：
12 快速排序是对冒泡排序的一种本质改进。它的基本思想是通过一趟
13 扫描后，使得排序序列的长度能大幅度地减少。在冒泡排序中，一次
14 扫描只能确保最大数值的数移到正确位置，而待排序序列的长度可能只
15 减少1。快速排序通过一趟扫描，就能确保某个数（以它为基准点吧）
16 的左边各数都比它小，右边各数都比它大。然后又用同样的方法处理
17 它左右两边的数，直到基准点的左右只有一个元素为止。它是由
18 C.A.R.Hoare于1962年提出的。
19
20 显然快速排序可以用递归实现，当然也可以用栈化解递归实现。下面的
21 函数是用递归实现的，有兴趣的朋友可以改成非递归的。
22 快速排序是不稳定的。最理想情况算法时间复杂度O(nlog2n)，最坏O(n2)
23 =====================================================
24 */
25 void quick_sort(int *x, int low, int high)
26 {
27 int i, j, t;
28 if (low < high) /*要排序的元素起止下标，保证小的放在左边，大的放在右边。这里以下标为low的元素为基准点*/
29 {
30 i = low;
31 j = high;
32 t = *(x+low); /*暂存基准点的数*/
33 while (i<j) /*循环扫描*/
34 {
35 while (i<j && *(x+j)>t) /*在右边的只要比基准点大仍放在右边*/
36 {
37 j--; /*前移一个位置*/
38 }
39 if (i<j)
40 {
41 *(x+i) = *(x+j); /*上面的循环退出：即出现比基准点小的数，替换基准点的数*/
42 i++; /*后移一个位置，并以此为基准点*/
43 }
44 while (i<j && *(x+i)<=t) /*在左边的只要小于等于基准点仍放在左边*/
45 {
46 i++; /*后移一个位置*/
47 }
48 if (i<j)
49 {
50 *(x+j) = *(x+i); /*上面的循环退出：即出现比基准点大的数，放到右边*/
51 j--; /*前移一个位置*/
52 }
53 }
54 *(x+i) = t; /*一遍扫描完后，放到适当位置*/
55 quick_sort(x,low,i-1); /*对基准点左边的数再执行快速排序*/
56 quick_sort(x,i+1,high); /*对基准点右边的数再执行快速排序*/
57 }
58 }
59
60 /*====================================================
61 算法思想简单描述：
62
63 堆排序是一种树形选择排序，是对直接选择排序的有效改进。
64 堆的定义如下：具有n个元素的序列（h1,h2,...,hn),当且仅当
65 满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)
66 时称之为堆。在这里只讨论满足前者条件的堆。
67
68 由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。完全二叉树可以
69 很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。
70 初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储顺序，
71 使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点
72 交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点
73 的堆，并对它们作交换，最后得到有n个节点的有序序列。
74
75 从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素
76 交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数
77 实现排序的函数。
78 堆排序是不稳定的。算法时间复杂度O(nlog2n)。
79 */
80 /*
81 功能：渗透建堆
82 输入：数组名称（也就是数组首地址）、参与建堆元素的个数、从第几个元素开始
83 */
84 void sift(int *x, int n, int s)
85 {
86 int t, k, j;
87 t = *(x+s); /*暂存开始元素*/
88 k = s; /*开始元素下标*/
89 j = 2*k + 1; /*右子树元素下标*/
90 while (j<n)
91 {
92 if (j<n-1 && *(x+j) < *(x+j+1))/*判断是否满足堆的条件：满足就继续下一轮比较，否则调整。*/
93 {
94 j++;
95 }
96 if (t<*(x+j)) /*调整*/
97 {
98 *(x+k) = *(x+j);
99 k = j; /*调整后，开始元素也随之调整*/
100 j = 2*k + 1;
101 }
102 else /*没有需要调整了，已经是个堆了，退出循环。*/
103 {
104 break;
105 }
106 }
107 *(x+k) = t; /*开始元素放到它正确位置*/
108 }
109
110 /*
111 功能：堆排序
112 输入：数组名称（也就是数组首地址）、数组中元素个数
113 */
114 void heap_sort(int *x, int n)
115 {
116 int i, k, t;
117 int *p;
118 for (i=n/2-1; i>=0; i--)
119 {
120 sift(x,n,i); /*初始建堆*/
121 }
122 for (k=n-1; k>=1; k--)
123 {
124 t = *(x+0); /*堆顶放到最后*/
125 *(x+0) = *(x+k);
126 *(x+k) = t;
127 sift(x,k,0); /*剩下的数再建堆*/
128 }
129 }
130
131 int a[10] = {9,7,4,1,11,33,62,8,5,3};
132 int main(int argc, char* argv[])
133 {
134 int* p = a;
135 heap_sort(p, 10);
136 printf("\n应用程序运行结束！\n");
137 return 0;
138 }
139
1 快速排序（QuickSort）
快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。
（1） 如果不多于1个数据，直接返回。（2） 一般选择序列最左边的值作为支点数据。（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。（4） 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2 归并排序（MergeSort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。
3 堆排序（HeapSort）
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
4 Shell排序（ShellSort）
Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。
Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
5 插入排序（InsertSort）
插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。
6 冒泡排序（BubbleSort）
冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是O(n^2)的算法。
7 交换排序（ExchangeSort）和选择排序（SelectSort）
这两种排序方法都是交换方法的排序算法，效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。
8 基数排序（RadixSort）
基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。
快速排序是一个就地排序，分而治之，大规模递归的算法。从本质上来说，它是归并排序的就地版本。快速排序可以由下面四步组成。
（1） 如果不多于1个数据，直接返回。（2） 一般选择序列最左边的值作为支点数据。（3） 将序列分成2部分，一部分都大于支点数据，另外一部分都小于支点数据。（4） 对两边利用递归排序数列。
快速排序比大部分排序算法都要快。尽管我们可以在某些特殊的情况下写出比快速排序快的算法，但是就通常情况而言，没有比它更快的了。快速排序是递归的，对于内存非常有限的机器来说，它不是一个好的选择。
2 归并排序（MergeSort）
归并排序先分解要排序的序列，从1分成2，2分成4，依次分解，当分解到只有1个一组的时候，就可以排序这些分组，然后依次合并回原来的序列中，这样就可以排序所有数据。合并排序比堆排序稍微快一点，但是需要比堆排序多一倍的内存空间，因为它需要一个额外的数组。
3 堆排序（HeapSort）
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
4 Shell排序（ShellSort）
Shell排序通过将数据分成不同的组，先对每一组进行排序，然后再对所有的元素进行一次插入排序，以减少数据交换和移动的次数。平均效率是O(nlogn)。其中分组的合理性会对算法产生重要的影响。现在多用D.E.Knuth的分组方法。
Shell排序比冒泡排序快5倍，比插入排序大致快2倍。Shell排序比起QuickSort，MergeSort，HeapSort慢很多。但是它相对比较简单，它适合于数据量在5000以下并且速度并不是特别重要的场合。它对于数据量较小的数列重复排序是非常好的。
5 插入排序（InsertSort）
插入排序通过把序列中的值插入一个已经排序好的序列中，直到该序列的结束。插入排序是对冒泡排序的改进。它比冒泡排序快2倍。一般不用在数据大于1000的场合下使用插入排序，或者重复排序超过200数据项的序列。
6 冒泡排序（BubbleSort）
冒泡排序是最慢的排序算法。在实际运用中它是效率最低的算法。它通过一趟又一趟地比较数组中的每一个元素，使较大的数据下沉，较小的数据上升。它是O(n^2)的算法。
7 交换排序（ExchangeSort）和选择排序（SelectSort）
这两种排序方法都是交换方法的排序算法，效率都是 O(n2)。在实际应用中处于和冒泡排序基本相同的地位。它们只是排序算法发展的初级阶段，在实际中使用较少。
8 基数排序（RadixSort）
基数排序和通常的排序算法并不走同样的路线。它是一种比较新颖的算法，但是它只能用于整数的排序，如果我们要把同样的办法运用到浮点数上，我们必须了解浮点数的存储格式，并通过特殊的方式将浮点数映射到整数上，然后再映射回去，这是非常麻烦的事情，因此，它的使用同样也不多。而且，最重要的是，这样算法也需要较多的存储空间。