快速排序算法实现

快速排序算法是比较常用的一种排序算法，在所有同数量级（O(nlogn)）的排序算法中，其平均性能最好。但是，若初始记录序列按关键字有序或基本有序时，快速排序将蜕化为气泡排序，其时间复杂度为O(n^2)，可以通过改良该算法来完善这一问题。

快速排序算法的一般实现：

 1 #include <stdio.h>
 2 
 3 #define LEN 7
 4 
 5 int array[LEN] = {49, 38, 65, 97, 76, 13, 27};
 6 
 7 void printarray()
 8 {
 9     int i;
10 
11     for (i = 0; i < LEN; i++)
12     {
13         printf("%d ", array[i]);
14     }
15     printf("
");
16 
17     return;
18 }
19 
20 int partition(int start, int end)
21 {
22     int pivotkey = array[start];
23 
24     while (start < end)
25     {
26         while (start < end && array[end] >= pivotkey)
27             end--;
28         array[start] = array[end];
29         while (start < end && array[start] <= pivotkey)
30             start++;
31         array[end] = array[start];
32     }
33     array[start] = pivotkey;
34 
35     return start;
36 }
37 
38 void quicksort(int start, int end)
39 {
40     int mid;
41 
42     if (start < end)
43     {
44         mid = partition(start, end);
45         printarray();
46         quicksort(start, mid - 1);
47         quicksort(mid + 1, end);
48     }
49 
50     return;
51 }
52 
53 
54 int main(void)
55 {
56     printarray();
57     quicksort(0, LEN - 1);
58 
59     return 0;
60 }