快速排序

 1 #include <iostream>
 2 #include <cstdlib>
 3 
 4 #define ARR_SIZE 10
 5 
 6 using namespace std;
 7 
 8 
 9 void quicksort(int a[], int lo, int hi);
10 int partition(int a[], int lo, int hi);
11 void CreateRandArr(int a[]);
12 
13 int main()
14 {
15     int a[ARR_SIZE];
16     int i;
17     CreateRandArr(a);
18     quicksort(a, 0, ARR_SIZE-1);
19     cout << "after sort: " << endl;
20     for(i=0;i<ARR_SIZE;i++)
21     {
22         cout << a[i] << ' ' ;
23     }
24     
25     return 0;
26 }
27 
28 void quicksort(int a[], int lo, int hi)
29 {
30     if(lo >= hi) return;
31     int j = partition(a, lo, hi);
32     quicksort(a, lo, j-1);
33     quicksort(a, j+1, hi);
34 
35 }
36 
37 /* 算法解析：分治思想：把索引为lo的元素放中间作为分界，使左边的元素都小于它，右边的元素都大于他，返回它的索引 */
38 int partition(int a[], int lo, int hi)
39 {
40     int i=lo,j = hi+1, temp;
41     while(true)
42     {
43         while(a[lo] >a[++i])if(i==hi)break;  /* 这两个while中的if语句都是冗余的，想想看why？ */
44         while(a[lo]<a[--j])if(j==lo)break;
45         if(i>=j)break;
46         temp = a[i];
47         a[i] = a[j];
48         a[j] = temp;
49     }
50     temp = a[lo];   /* 注意这个地方，把分界元素（a[lo]）与a[j]进行交换(而不是a[i]),返回j（这里只能死记硬背了） */
51     a[lo] = a[j];
52     a[j] = temp;
53 
54     return j;
55 
56 }
57 
58 void CreateRandArr(int a[])
59 {
60     int i;
61     for(i=0;i<ARR_SIZE;i++)
62     {
63         a[i] = rand() % 100;
64         cout <<a[i] << ' ' ; 
65     }
66     cout << endl;
67 }