排序算法之----快速排序

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 
  4 void print(int a[], int num);
  5 int Partion3(int k[], int low, int hight);
  6 int Partion(int k[], int low, int hight);
  7 void Qsort(int k[], int low, int hight);
  8 
  9 void swap(int k[], int a, int b)
 10 {
 11     int tmp = k[a];
 12     k[a] = k[b];
 13     k[b] = tmp;
 14 }
 15 
 16 //快速排序
 17 //基本思想：找基准点二分法递归
 18 void QuickSort(int k[], int n)
 19 {
 20     Qsort(k, 0, n - 1);
 21 }
 22 
 23 void Qsort(int k[], int low, int hight)
 24 {
 25     int point;
 26     if (low < hight)
 27     {
 28         point = Partion3(k, low, hight);
 29         Qsort(k, low, point - 1);
 30         Qsort(k, point + 1, hight);
 31     }
 32 }
 33 
 34 int Partion(int k[], int low, int hight)
 35 {
 36     int point;
 37     point = k[low];
 38     while (low < hight)
 39     {
 40         //右边的全部大于point
 41         while ((low < hight) && k[hight] >= point)
 42         {
 43             hight--;
 44         }
 45         //交换的目的是将小与point的放入low
 46         swap(k, low, hight);
 47         //左边的全部小于point
 48         while ((low < hight) && k[low] <= point)
 49         {
 50             low++;
 51         }
 52         //交换的目的是将大于point的放入hight
 53         swap(k, low, hight);
 54     }
 55     return low;
 56 }
 57 
 58 //快速排序的优化
 59 //1.优化基准点：3数取中法
 60 int Partion2(int k[], int low, int hight)
 61 {
 62     int point;
 63     point = k[low];
 64     int m = low + (hight - low) / 2;
 65     if (k[low] > k[hight])
 66     {
 67         swap(k, low, hight);
 68     }
 69     if (k[m] > k[hight])
 70     {
 71         swap(k, m, hight);
 72     }
 73     //使得low为中间值
 74     if (k[m] > k[low])
 75     {
 76         swap(k, m, hight);
 77     }
 78 
 79     while (low < hight)
 80     {
 81         //右边的全部大于point
 82         while ((low < hight) && k[hight] >= point)
 83         {
 84             hight--;
 85         }
 86         //交换的目的是将小与point的放入low
 87         swap(k, low, hight);
 88         //左边的全部小于point
 89         while ((low < hight) && k[low] <= point)
 90         {
 91             low++;
 92         }
 93         //交换的目的是将大于point的放入hight
 94         swap(k, low, hight);
 95     }
 96     return low;
 97 }
 98 
 99 //2. 优化交换
100 int Partion3(int k[], int low, int hight)
101 {
102     int point;
103     point = k[low];
104     while (low < hight)
105     {
106         //右边的全部大于point
107         while ((low < hight) && k[hight] >= point)
108         {
109             hight--;
110         }
111         //交换的目的是将小与point的放入low
112         k[low] = k[hight];
113         //左边的全部小于point
114         while ((low < hight) && k[low] <= point)
115         {
116             low++;
117         }
118         //交换的目的是将大于point的放入hight
119         k[hight] = k[low];
120     }
121     k[low] = point;
122     return low;
123 }
124 
125 //3. 数目小于7使用插入排序
126 //4. 优化递归操作：尾递归会被编译器优化，不会开辟栈
127 
128 void print(int a[], int num)
129 {
130     int i = 0;
131     for (i = 0; i < num; i++)
132     {
133         printf("%d ", a[i]);
134     }
135     printf("
");
136 }
137 
138 int main()
139 {
140     int a[10] = { 2, 3, 56, 1, 4, 7, 8, 94, 3, 10 };
141     print(a, 10);
142 
143     QuickSort(a, 10);
144     printf("快速排序
");
145     print(a, 10);
146 
147     return system("pause");
148 }