快速排序

参考：

　　《linux c编程一站式学习》的习题11.4.1

　　http://c.biancheng.net/cpp/html/2741.html

思想：

　　采用分而治之的排序算法，从a[start,...,end]中选取一个pivot元素（比如a[start]为pivot）；在一个循环中移动a[start,...,end]的数据，将a[start,...,end]分成两半，使a[start, ...,mid-1]比pivot元素小，a[mid+1,...,end]比pivot元素大，而a[mid]就是pivot元素；

code:

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <stdlib.h>
 4 
 5 #define LEN 8
 6 
 7 
 8 int testData[LEN] = {5, 2, 4, 6, 1, 3, 2, 7};
 9 
10 /*
11 功能：从a[start,...,end]中选取一个pivot元素（比如a[start]为pivot）；在一个循环中移动a[start,...,end]的数据，将a[start,...,end]分成两半，
12         使a[start, ...,mid-1]比pivot元素小，a[mid+1,...,end]比pivot元素大，而a[mid]就是pivot元素
13 注意：每一步骤的赋值之前，需判断high>low条件是否成立
14 */
15 int partition(int start, int end)
16 {//
17     int low=start, high=end;
18     int pivot = testData[start];
19     while(high > low){
20         while(high>low && pivot<testData[high]){
21             high--;
22         }
23         if(high > low){
24             testData[low++] = testData[high];
25         }
26         while(high>low && pivot > testData[low]){
27             low++;
28         }
29         if(high > low){
30             testData[high--] = testData[low];
31         }
32     }
33     testData[low] = pivot;
34     return low;
35 }
36 
37 void quickSort(int start, int end)
38 {
39     int mid;
40     if(end > start){
41         mid = partition(start, end);
42         printf("sort(%d-%d, %d, %d-%d): %d, %d, %d, %d, %d, %d, %d, %d
",
43             start, mid-1, mid, mid+1, end, testData[0], testData[1],testData[2],
44             testData[3], testData[4], testData[5],testData[6], testData[7]);
45         quickSort(start, mid-1);
46         quickSort(mid+1, end);
47     }
48 }
49 
50 int main(int argc, char *argv[])
51 {
52     printf("sort: %d, %d, %d, %d, %d, %d, %d, %d
",
53              testData[0], testData[1],testData[2], testData[3], 
54              testData[4], testData[5],testData[6], testData[7]);
55     quickSort(0, LEN-1);
56     return 0;
57 }

快速排序

参考：

思想：

code:

运行结果截图：

第一次划分流程参考：