快速排序算法（二）

1. 快速排序算法

　　在常用的快速排序算法中，每一步均将第一个数放到合适的位置。

　　下面介绍一种将任意数放到合适位置的快速排序算法。

 1 int Partition(int data[], int length, int start, int end)
 2 {
 3     if(data == NULL || length <= 0 || start <= 0 || end >=length)
 4         throw new std::exception("Invalid parameters");
 5     
 6     int index = RandomInRange(start, end);
 7     Swap(&data[index], &data[end]);
 8     
 9     int small = start - 1;
10     for(index = start; index < end; index++)
11     {
12         if(data[index] < data[end])
13         {
14             small++;
15             if(small != index)
16                 Swap(&data[index], &data[small]);
17         }
18     }
19     
20     small++;
21     Swap(&data[small], &data[end]);
22     
23     return small;
24 }
25 
26 int RandomInRange(start, end)
27 {
28     int length = end - start + 1;
29     int ret = rand() % length; //0 ~ length-1
30 }
31 
32 void Swap(int* a, int* b)
33 {
34     *b = *b + *a;
35     *a = *b - *a;
36     *b = *b - *a;
37 }

 1 void QuickSort(int data[], int length, int start, int end)
 2 {
 3     if(start == end)
 4         return;
 5     
 6     int index = Partition(data, length, start, end);
 7     if(index > start)
 8         QuickSort(data, length, start, index - 1);
 9     if(index < end)
10         QuickSort(data, length, index + a, end);
11 }

2. 数组中第k大数字

 1 int FindKthNumber(int data[], int length)
 2 {
 3     int middle = length >> 1;
 4     int start = 0;
 5     int end = length - 1;
 6     int index = Partition(data, length, start, end);
 7     while(index != middle)
 8     {
 9         if(index > middle)
10         {
11             end = index - 1;
12             index = Partition(data, length, start, end);
13         }
14         else
15         {
16             start = index + 1 ;
17             index = Partition(data, length, start, end);
18         }
19     }
20     
21     return data[middle];
22 }