首页 > 代码库 > 排序2

排序2

本博客的代码的思想和图片参考:好大学慕课浙江大学陈越老师、何钦铭老师的《数据结构》

 

<style>h2.western { font-family: "Liberation Sans", sans-serif; font-size: 16pt } h2.cjk { font-size: 16pt } h2.ctl { font-size: 16pt } h1 { margin-bottom: 0.21cm } h1.western { font-family: "Liberation Sans", sans-serif; font-size: 18pt } h1.cjk { font-family: "Noto Sans CJK SC Regular"; font-size: 18pt } h1.ctl { font-family: "Noto Sans CJK SC Regular"; font-size: 18pt } p { margin-bottom: 0.25cm; line-height: 120% }</style>

 

排序2

 

1 快速排序

 

1.1 算法思想

 

快速排序的主要思想就是分而治之。选择一个主元,然后把原来的集合分为比主元小和比主元大两个子集合,然后递归的解决左边,递归的解决右边。我们使用一幅图片来进行说明

 

技术分享

 

 

 

 

 

 

 

 

 

 

 

 

下面是快速排序的伪代码描述

 

void Quicksort( ElementType A[], int N )

 

{

 

if ( N < 2 ) return;

 

pivot = A[]中选一个主元;

 

S = { A[] \ pivot } 分成2个独立子集:

 

A1={ a?S | a ? pivot }

 

A2={ a?S | a ? pivot };

 

A[] =

 

Quicksort(A1,N1)U

 

pivot}U

 

Quicksort(A2,N2);

 

}

 

1.2 快速排序的性能分析

 

因为快速排序是递归进行的,递归算法的好处体现在每次可以递归的解决规模差不多的子问题。如果主元选的不好,让子集大小很悬殊,那么快速排序就快不起来了。下面是使用一幅图片来说明如果主元选取的不好,那么就会很囧。

 

技术分享

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

可以看出,如果主元选的不好,那么快速排序的时间复杂度为O(N^2),很糟糕

 

1.3 常见的选择主元的方法

 

1.随机取 pivot?rand()函数不便宜啊!

 

2.取头、中、尾的中位数

 

例如 8123的中位数就是8

 

下面给出中位数法的伪代码描述

 

ElementType Median3( ElementType A[], int Left, int Right )

 

{

 

int Center = ( Left + Right ) / 2;

 

if ( A[ Left ] > A[ Center ] )

 

Swap( &A[ Left ], &A[ Center ] );

 

if ( A[ Left ] > A[ Right ] )

 

Swap( &A[ Left ], &A[ Right ] );

 

if ( A[ Center ] > A[ Right ] )

 

Swap( &A[ Center ], &A[ Right ] );

 

/* A[ Left ] <= A[ Center ] <= A[ Right ] */

 

Swap( &A[ Center ], &A[ Right-1 ] ); /* pivot藏到右边 */

 

/* 只需要考虑 A[ Left+1 ] ... A[ Right–2 ] */

 

return A[ Right-1 ]; /* 返回 pivot */

 

}

 

1.4 子集划分算法

 

使用一幅图片来说明

 

技术分享

 

 

 

 

 

 

 

 

 

如果有元素正好等于pivot怎么办?

 

1.停下来交换?

 

1.不理它,继续移动指针?

 

举一个极端的例子,如果,如果一个数组全是和主元相等,如果使用停下来交换,就会做无用的交换,如果 不理它,继续移动指针,那么i会一直移动到大于j,此时我们的主元就会在端点,那么所造成的影响就是时间复杂度为O(N^2)

 

所以我们选择 停下来交换

 



 

1.5快速排序的问题

 

1.用递归......

 

对小规模的数据(例如N不到100)可能还不如插入排序快

 



 

2.解决方案

 

当递归的数据规模充分小,则停止递归,直接调用简单排序(例如插入排序)

 

在程序中定义一个Cutoff的阈值 —— 课后去实践一下,比较不同的Cutoff对效率的影响

 



 

1.6快速排序的测试结果

 

 

 



 



 

 技术分享

 

 

 

阀值都取100的情况下

 

技术分享

 

 

 

 

1.7 结果分析

 

对于不同的阀值,发现效率差距并不是很大。但是选择不同pivot,差距很大。从测试结果看

 

中位数效果最好,随机数次之,使用第一个元素作为pivot效果最差。所以今后尽量使用中位数方法。

1.8 快速排序代码

 

技术分享
  1 /*
  2  * quickSort.c
  3  *
  4  *  Created on: 2017年5月20日
  5  *      Author: ygh
  6  */
  7 
  8 #include <stdio.h>
  9 #include <stdlib.h>
 10 #define  MAX_LENGTH 100000
 11 typedef int elementType;
 12 
 13 /*
 14  * Swap two integer number value
 15  */
 16 void swap(elementType *a, elementType *b) {
 17     int temp = *b;
 18     *b = *a;
 19     *a = temp;
 20 }
 21 
 22 /*
 23  * Print the array to console
 24  * @param a A integer array need to sort
 25  * @param n The length of the array
 26  */
 27 void printArray(int a[], int n) {
 28     int i;
 29     for (i = 0; i < n; i++) {
 30         if (i == n - 1) {
 31             printf("%d", a[i]);
 32         } else {
 33             printf("%d ", a[i]);
 34         }
 35     }
 36     printf("\n");
 37 }
 38 
 39 /*
 40  * Get input data from command
 41  */
 42 void getInputData(elementType *a, int n) {
 43     int i;
 44     elementType x;
 45     for (i = 0; i < n; i++) {
 46         scanf("%d", &x);
 47         a[i] = x;
 48     }
 49 }
 50 
 51 /*
 52  * Implement insertion sort.
 53  *@param a A <code>elementType</code> array need to sort
 54  *@param n The length of the array
 55  */
 56 void insertion_sort(elementType a[], int n) {
 57     int i, j;
 58     elementType temp;
 59     for (i = 1; i < n; i++) {
 60         temp = a[i];
 61         for (j = i; j > 0 && a[j - 1] > temp; j--) {
 62             a[j] = a[j - 1];
 63         }
 64         a[j] = temp;
 65     }
 66 
 67 }
 68 
 69 /*
 70  *Get the pivot by get the median amount three number
 71  */
 72 elementType getPivotByMedian3(elementType a[], int left, int right) {
 73     int center = (left + right) / 2;
 74     /*
 75      * Let a[left]<= a[center] <= a[right]
 76      */
 77     if (a[left] > a[center]) {
 78         swap(&a[left], &a[center]);
 79     }
 80 
 81     if (a[left] > a[right]) {
 82         swap(&a[left], &a[right]);
 83     }
 84 
 85     if (a[center] > a[right]) {
 86         swap(&a[center], &a[right]);
 87     }
 88 
 89     /*
 90      * We has known the a[right] greater than a[center]
 91      * so we swap the a[center] and a[right-1],so we just
 92      * consider from a[left+1] to a[right-2] when we divide sub-set
 93      */
 94     swap(&a[center], &a[right - 1]);
 95     return a[right - 1];
 96 
 97 }
 98 
 99 elementType getPivotByRandom(elementType a[], int left, int right) {
100     int index = rand() % (right - left + 1) + left;
101     return index;
102 }
103 
104 /*
105  * Implement quick sort,we get the pivot by the middle of three numbers
106  * @param a A <code>elementType</code> array need to sort
107  * @param left The starting index of sub-set
108  * @param right The finishing index of sub-set
109  * @param A cutoff to determine how many numbers rest we will
110  * use the insertion sort.
111  */
112 void qSort(elementType a[], int left, int right, int cutoff) {
113     int low, high;
114     elementType pivot;
115     if (cutoff <= right - left) {
116         pivot = getPivotByMedian3(a, left, right);
117         low = left;
118         high = right - 1;
119         while (1) {
120             while (a[++low] < pivot)
121                 ;
122             while (a[--high] > pivot)
123                 ;
124             if (low < high) {
125                 swap(&a[low], &a[high]);
126             } else {
127                 break;
128             }
129         }
130         swap(&a[low], &a[right - 1]);
131         qSort(a, left, low - 1, cutoff);
132         qSort(a, low + 1, right, cutoff);
133 
134     } else {
135         insertion_sort(a + left, right - left + 1);
136     }
137 }
138 
139 /*
140  * Implement quick sort,we get the pivot by the middle of three numbers
141  * @param a A <code>elementType</code> array need to sort
142  * @param left The starting index of sub-set
143  * @param right The finishing index of sub-set
144  * @param A cutoff to determine how many numbers rest we will
145  * use the insertion sort.
146  */
147 void qSortByRandom(elementType a[], int left, int right, int cutoff) {
148     int low, high, index;
149     elementType pivot;
150     if (cutoff <= right - left) {
151         index = getPivotByRandom(a, left, right);
152         swap(&a[left], &a[index]);
153         pivot = a[left];
154         low = left;
155         high = right;
156         while (low < high) {
157             while (low < high && a[high] >= pivot) {
158                 high--;
159             }
160             a[low] = a[high];
161             while (low < high && a[low] <= pivot) {
162                 low++;
163             }
164             a[high] = a[low];
165         }
166         a[low] = pivot;
167         qSortByRandom(a, left, low - 1, cutoff);
168         qSortByRandom(a, low + 1, right, cutoff);
169     } else {
170         insertion_sort(a + left, right - left + 1);
171     }
172 }
173 
174 /*
175  * Implement quick sort,we get the pivot by the middle of three numbers
176  * @param a A <code>elementType</code> array need to sort
177  * @param left The starting index of sub-set
178  * @param right The finishing index of sub-set
179  * @param A cutoff to determine how many numbers rest we will
180  * use the insertion sort.
181  */
182 void qSortByFirstNum(elementType a[], int left, int right, int cutoff) {
183     int low, high;
184     elementType pivot;
185     if (cutoff <= right - left) {
186         pivot = a[left];
187         low = left;
188         high = right;
189         while (low < high) {
190             while (low < high && a[high] >= pivot) {
191                 high--;
192             }
193             a[low] = a[high];
194             while (low < high && a[low] <= pivot) {
195                 low++;
196             }
197             a[high] = a[low];
198         }
199         a[low] = pivot;
200         qSortByFirstNum(a, left, low - 1, cutoff);
201         qSortByFirstNum(a, low + 1, right, cutoff);
202     } else {
203         insertion_sort(a + left, right - left + 1);
204     }
205 }
206 
207 /*
208  * Implement sort unitized interface
209  * @param a A <code>elementType</code> array need to sort
210  * @param n The length of the array
211  */
212 void quickSort(elementType a[], int n) {
213 //    qSort(a, 0, n - 1, 100);
214 //    qSortByRandom(a, 0, n - 1, 100);
215     qSortByFirstNum(a, 0, n - 1, 2);
216 }
217 
218 
219 
220 int main() {
221     int a[MAX_LENGTH];
222     int n;
223     scanf("%d", &n);
224     getInputData(a, n);
225     quickSort(a, n);
226     printArray(a, n);
227     return 0;
228 }
quickSort

 

排序2