首页 > 代码库 > 排序2

排序2

2024-09-23 19:14:08 217人阅读

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

排序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.取头、中、尾的中位数

例如 8、12、3的中位数就是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

声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉：投诉/举报工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。

联系
我们

首页 > 代码库 > 排序2

排序2

1 快速排序

1.1 算法思想

1.2 快速排序的性能分析

1.3 常见的选择主元的方法

1.4 子集划分算法

1.5快速排序的问题

1.6快速排序的测试结果

1.7 结果分析

1.8 快速排序代码

看完仍有疑问？有类似问题直接问程序猿