知识点总结之排序算法

长沙7喜 2018-04-16

展开全文

定期推送信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，融科教育信息学培训等诸多优质内容的微信平台，欢迎分享文章给你的朋友或者朋友圈！

排序(Sorting) 是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录）的任意序列，重新排列成一个关键字有序的序列。

1、选择排序

　　选择排序是一种直观简单的排序算法，它每次从待排序的数据元素中选出最小(或者最大)元素存放到序列的起始位置，直到全部待排序的数据元素排完。注意，选择排序并不是稳定的排序。

1 /*
2 * @brief select sort
3 * @param [in] arr: the array be sorted
4 * [in] length: the array size
5 * @return void
6 */
7 void SelectSort(int arr[], int length)
8 {
9 for (int i = 0; i < length;="">) {
10 int min = i;
11 for (int j = i + 1; j < length;="">) {
12 if (arr[min] arr[j]) {
13 min = j;
14 }
15 }
16 if (min != i) {
17 swap(arr[min], arr[i]);
18 }
19 }
20 }

2、冒泡排序

　　冒泡排序也是一种直观简单的排序算法，它重复地走访要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。冒泡排序是一种稳定的排序。

1 /*
2 * @brief bubble sort
3 * @param [in] arr: the array be sorted
4 * [in] length: the array size
5 * @return void
6 */
7 void BubbleSort(int arr[], int length)
8 {
9 for (int i = 0; i < length;="">) {

10 for (int j = 0; j < length="" -="" i="" -="">1; j++) {

11 if (arr[j] > arr[j + 1]) {

12 swap(arr[j], arr[j + 1]);

13 }

14 }

15 }

16 }

3、插入排序

　　插入排序基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的元素序列中适当位置上，直到全部插入完为止。插入排序是稳定的排序算法。

1 /*
2 * @brief insert sort
3 * @param [in] arr: the array be sorted
4 * [in] length: the array size
5 * @return void
6 */
7 void InsertSort(int arr[], int length)
8 {
9 for (int i = 0; i < length;="">) {

10 for (int j = i; j > 0 && arr[j - 1] > arr[j]; j--) {

11 swap(arr[j], arr[j - 1]);

12 }

13 }

14 }

15 /* 这是插入排序的第二种写法 */

16 void InsertSort2(int arr[], int length)

17 {

18 for (int i = 0; i < length;="">)

19 {

20 int x = arr[i], j;

21 for (j = i; j > 0 && arr[j - 1] > x; j--)

22 arr[j] = arr[j - 1];

23 arr[j] = x;

24 }

25 }

4、希尔排序

　　希尔排序(Shell Sort)是插入排序的一种，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。

1 /*
2 * @brief shell sort
3 * @param [in] arr: the array be sorted
4 * [in] length: the array size
5 * @return void
6 */
7 void ShellSort(int arr[], int length)
8 {
9 for (int inc = length / 2; inc > 0; inc /= 2) {

10 for (int i = inc; i < length;="">) {

11 for (int j = i; j >= inc && arr[j - inc] > arr[j]; j -= inc) {

12 swap(arr[j], arr[j - inc]);

13 }

14 }

15 }

16 }

5、快速排序

　　快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1 /*
2 * 快速排序
3 * 快速排序是一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立地排序。
4 * 快速排序和归并排序是互补的：归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；
5 * 而快速排序的方式是当两个子数组有序时整个数组也就自然有序了。归并排序中，递归发生在处理整个数组之前，
6 * 一个数组被分为两半；快速排序中，递归调用发生在处理整个数组之后，切分的位置取决于数组的内容。
7 */
8 int Partion(int arr[], int left, int right)
9 {
10 int x = arr[right];

11 int i, j;

12
13 for (i = j = left; i < right;="">) {

14 if (arr[i] <> x) {

15 swap(arr[i], arr[j++]);

16 }

17 }

18 swap(arr[j], arr[right]);

19
20 return j;

21 }

22 void QuickSort(int arr[], int left, int right)

23 {

24 if (left right) {

25 int mid = Partion(arr, left, right);

26 QuickSort(arr, left, mid - 1);

27 QuickSort(arr, mid + 1, right);

28 }

29 }

30 void QuickSort(int arr[], int length)

31 {

32 QuickSort(arr, 0, length - 1);

33 }

6、归并排序

　　归并排序是将两个有序的数组归并成一个更大的有序数组。要将一个数组排序，可以先（递归的）将他分成两半分别排序，让后将结果归并起来。它能够保证将任意长度为N的数组排序所需时间和NlogN成正比；它的主要缺点就是所需的额外空间和N成正比。归并排序是稳定的排序算法。

1 /*
2 * 归并排序
3 * 归并排序将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序
4 */
5 void Merge(int arr[], int aux[], int left, int mid, int right) 6 {
7 int i = left;
8 int j = mid + 1;
9 int k = left;

10
11 while (i <= mid="" &&="" j=""><> right) {

12 if (arr[i] > arr[j]) {

13 aux[k++] = arr[j++];

14 }

15 else {

16 aux[k++] = arr[i++];

17 }

18 }

19 while (i <> mid) {

20 aux[k++] = arr[i++];

21 }

22 while (j <> right) {

23 aux[k++] = arr[j++];

24 }

25 for (int i = left; i <= right;="">) {

26 arr[i] = aux[i];

27 }

28 }

29 void MergeSort(int arr[], int aux[], int left, int right)

30 {

31 if (left right) {

32 int mid = left + (right - left) / 2;

33 MergeSort(arr, aux, left, mid);

34 MergeSort(arr, aux, mid + 1, right);

35 Merge(arr, aux, left, mid, right);

36 }

37 }

38 void MergeSort(int arr[], int length)

39 {

40 int *aux = new int[length];

41 MergeSort(arr, aux, 0, length - 1);

42 delete []aux;

43 }

7、堆排序

　　堆排序可以分为两个阶段。在堆的构造阶段，我们将元使数组重新组织安排进一个堆中；然后在下沉阶段，我们从堆中按递减顺序取出所有元素并得到排序结果。堆排序主要工作都是在堆的下沉阶段完成的，这里我们将堆中最大的元素删除，然后放入堆缩小后数组中空出的位置。

1 /*
2 * 堆排序
3 * 堆排序是用堆来实现的一种排序算法，堆排序分为两个阶段，在堆的构造阶段中，我们将原始数据重新组织安排
4 * 进一个堆中；然后在下沉排序阶段，我们从堆中按照递减顺序取出所有元素并得到排序算法
5 */
6 void Sink(int arr[], int i, int length)
7 {
8 while (2 * i <> length) {

9 int child = 2 * i;

10 if (child < length="" &&="" arr[child]="">< arr[child="" +="">1]) {

11 child++;

12 }

13 if (arr[i] >= arr[child]) {

14 break;

15 }

16
17 swap(arr[i], arr[child]);

18 i = child;

19 }

20 }

21 void HeapSort(int arr[], int length)

22 {

23 length--; /* 此时length代表数组最后一个元素下标 */

24 for (int i = length / 2; i >= 0; i--) { /* 这里一定要 i>=0，否则建堆不完全 */

25 Sink(arr, i, length);

26 }

27
28 while(length >= 0) {

29 swap(arr[0], arr[length--]);

30 Sink(arr, 0, length);

31 }

32 }

8、各种排序算法的稳定性和时间复杂度分析

什么是排序的稳定性呢？如果一个排序算法能够保留数组中重复元素的相对位置则可以称为是稳定的。以下是各个排序算法稳定性总结：

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法，
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

各个排序时间复杂度总结：

冒泡法：这是最原始，也是众所周知的最慢的算法了。他的名字的由来因为它的工作看来象是冒泡：复杂度为O(n*n)。当数据为正序，将不会有交换。复杂度为O(n^2)。
直接插入排序：O(n^2)
选择排序：O(n^2)
快速排序：平均时间复杂度log2(n)*n，所有内部排序方法中最高好的，大多数情况下总是最好的。
归并排序：log2(n)*n
堆排序：log2(n)*n
希尔排序：算法的复杂度为log2(n)*n

下面是一个总的表格，大致总结了我们常见的所有的排序算法的特点。

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n²)	O(n²)	稳定	O(1)	n小时较好
交换	O(n²)	O(n²)	不稳定	O(1)	n小时较好
选择	O(n²)	O(n²)	不稳定	O(1)	n小时较好
插入	O(n²)	O(n²)	稳定	O(1)	大部分已排序时较好
基数	O(log_RB)	O(log_RB)	稳定	O(n)	B是真数(0-9)， R是基数(个十百)
Shell	O(nlogn)	O(n^s) 1<><>	不稳定	O(1)	s是所选分组
快速	O(nlogn)	O(n²)	不稳定	O(nlogn)	n大时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好