快速排序

  1 #include <stdio.h>
  2 
  3 /**
  4     @param 两个需要交换的int值 的地址 
  5 */ 
  6 void Swap(int *a, int *b)
  7 {
  8     static int temp = 0;
  9     temp = *a;
 10     *a = *b;
 11     *b = temp;
 12 }
 13 
 14 /**
 15     目标：a[center] < a[low] < a[high]  目标：中间值 放在 a[low]上 
 16     欲要确定此三数的中间值；
 17         我们假定 存在一个中间值 a[low]，先对 a[center]，a[high] 进行比较。
 18             可排列成(通过交换两个数的值) a[center] < a[high], 两者分别与 a[low] 进行比较： 
 19         当a[low] > a[center]，a[low] < a[high] 均无法确定中间值
 20         
 21         故，我们先对 a[low] > a[center]，a[low] < a[high]的关系进行处理
 22             if (a[low] > a[center])     if (a[low] < a[high])  均交换它们的值
 23             于是，
 24             a[low] < a[center]              a[low] > a[high]
 25             发现，
 26                 a[high] < a[low] < a[center]
 27              
 28              故只需交换 a[high] 和 a[center]的值 即可达到目标 
 29 */
 30 /**
 31     寻找 核心元素 
 32     @param a 数组的地址 low, high 数组的范围(闭合区间) 
 33     @return 中间值
 34 */ 
 35 int SearchPivot(int a[], int low, int high)
 36 {
 37     int center = low + ((high - low) >> 1); // 计算中间位置 
 38     
 39     if (a[low] > a[center]) 
 40         Swap(&a[low], &a[center]); 
 41     if (a[low] < a[high])
 42         Swap(&a[low], &a[high]);
 43         
 44     Swap(&a[high], &a[center]);
 45     
 46     return a[low];
 47 }
 48 
 49 
 50 /**
 51     选出 核心元素，并依据 核心元素 划分 两半， 一半比核心元素 小，另一半比核心元素大 
 52     @param a 数组的地址 low, high 数组的范围(闭合区间) 
 53     @return 核心元素 
 54 */
 55 int AdjustOrder(int a[], int low, int high)
 56 {
 57     int pivot = SearchPivot(a, low, high); // 选出核心元素 
 58     
 59     while (low < high)
 60     {
 61         while (low < high && a[high] >= pivot) // 从右往左比较 
 62             --high;
 63         
 64         if (low < high) //有一个是小于 center
 65             a[low++] = a[high]; 
 66                     
 67         
 68         while (low < high && a[low] <= pivot) // 从左往右比较 
 69             ++low;
 70         if (low < high) // 有一个元素是大于 center 
 71             a[high--] = a[low];
 72     }
 73     
 74     a[low] = pivot; // low == high
 75     return low; 
 76 }
 77 
 78 /**
 79     快速排序 
 80     @param a 数组的地址， low, high 需要排序的范围(闭合区间) 
 81 */ 
 82 void QuickSort(int a[], int low, int high)
 83 {
 84     if (low < high)
 85     {
 86         int center = AdjustOrder(a, low, high); // 找出核心元素的位置 
 87         QuickSort(a, low, center - 1); // 划分两半，递归去处理它们 
 88         QuickSort(a, center + 1, high);
 89     }
 90 }
 91 
 92  
 93 int main()
 94 {
 95     int a[] = {99, -1, 0, 6, 88, 0, 7, 78, 1, 0};
 96     QuickSort(a, 0, 9);
 97     
 98     for (int i = 0; i != 10; i++)
 99         printf("%d ", a[i]);
100     
101     return 0;
102 }