数据结构学习笔记（九）－各大排序算法_数据结构 几大排序算法

一、简单排序

1. 冒泡排序

其思想是每次比较相邻的两个元素，如果后一个比它小则交换两个元素的顺序，直到将最大的数冒出来（假设是从小到大排）。那么我们需要进行N-1趟排序，每次最坏的情况交换N-1次，则时间复杂度为二次。

2. 插入排序

对于喜欢打扑克的人都知道，抓牌后我们需要将其插入到合适的位置，就需要将其与当前手中的牌一一 比较，直到找到那个比它小的数（假如是从小到大排）。那么对于一个数组int A[N]，我们就需要进行N-1趟排序，从P=0到P=N-1。没插入一次P,我们就需要将其与它前面P+1个数进行比较，假设它现在是最后一位，那么就和它相邻的前一位比较。

这里要提出一个“反序对”的概念，可以发现插入排序每交换一次元素，反序对数量就减少一次。则可以推出：

定理：通过交换相邻元素进行排序的任何算法平均需要Ω（N^2）的时间复杂度。

二、希尔排序

为了提高算法效率，我们应该每次多交换几个元素，于是就有了希尔排序。其思想就是每次隔着几个元素进行排序，每趟排序逐渐缩小增量，直到最后间隔为1，即变为插入排序。

但是希尔排序的时间依赖于增量的选择。

三、堆排序

如果我们可以借助最小堆的结构，每次都删除根结点，最小的结点先离开，再将它们存入一个数组中，但这种方法需要耗费额外的存储。
避免使用第二个数组的做法就是没次DeleteMin操作之后，堆缩小了1，所以位于堆最后的单元可以用来存放刚刚删去的元素。

四、归并排序

利用了分而治之的思想，先分治，再归并。整体可以用递归解决，这和之前的利用链表进行两个多项式相加很相似。首先将原来的数组一分为二后，我们还要再申请一个临时数组，设置三个计数器，然后再分别比较，将较小的一个插入临时数组。最后再将临时数组复制回原数组就行了。

五、代码实现

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <time.h>
using namespace std;
typedef int ElementType;

void InsertionSort(ElementType A[], int N) { /* 插入排序 */
  int P, i;
  ElementType Tmp;

  for (P = 1; P < N; P++) {
    Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
    for (i = P; i > 0 && A[i - 1] > Tmp; i--)
      A[i] = A[i - 1]; /*依次与已排序序列中元素比较并右移*/
    A[i] = Tmp;        /* 放进合适的位置 */
  }
}

void ShellSort0(ElementType A[], int N) {
  int i, P, D, temp;
  for (D = N / 2; D > 0; D /= 2) {
    for (P = D; P < N; P++) {
      temp = A[P];
      for (i = P; i >= D && A[i - D] > temp; i -= D)
        A[i] = A[i - D];
      A[i] = temp;
    }
  }
}

void ShellSort1(ElementType A[], int N) { /* 希尔排序 - 用Sedgewick增量序列 */
  int Si, D, P, i;
  ElementType Tmp;
  /* 这里只列出一小部分增量 */
  int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};

  for (Si = 0; Sedgewick[Si] >= N; Si++)
    ; /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */

  for (D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si])
    for (P = D; P < N; P++) { /* 插入排序*/
      Tmp = A[P];
      for (i = P; i >= D && A[i - D] > Tmp; i -= D)
        A[i] = A[i - D];
      A[i] = Tmp;
    }
}

void Swap(ElementType *a, ElementType *b) {
  ElementType t = *a;
  *a = *b;
  *b = t;
}

void PercDown(ElementType A[], int p,
              int N) { /* 改编代码4.24的PercDown( MaxHeap H, int p )    */
  /* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
  int Parent, Child;
  ElementType X;

  X = A[p]; /* 取出根结点存放的值 */
  for (Parent = p; (Parent * 2 + 1) < N; Parent = Child) {
    Child = Parent * 2 + 1;
    if ((Child != N - 1) && (A[Child] < A[Child + 1]))
      Child++; /* Child指向左右子结点的较大者 */
    if (X >= A[Child])
      break; /* 找到了合适位置 */
    else     /* 下滤X */
      A[Parent] = A[Child];
  }
  A[Parent] = X;
}

void HeapSort(ElementType A[], int N) { /* 堆排序 */
  int i;

  for (i = N / 2 - 1; i >= 0; i--) /* 建立最大堆 */
    PercDown(A, i, N);

  for (i = N - 1; i > 0; i--) {
    /* 删除最大堆顶 */
    Swap(&A[0], &A[i]); /* 见代码7.1 */
    PercDown(A, 0, i);
  }
}

/* 归并排序 - 递归实现 */

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge(
    ElementType A[], ElementType TmpA[], int L, int R,
    int RightEnd) { /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列
                       */
  int LeftEnd, NumElements, Tmp;
  int i;

  LeftEnd = R - 1; /* 左边终点位置 */
  Tmp = L;         /* 有序序列的起始位置 */
  NumElements = RightEnd - L + 1;

  while (L <= LeftEnd && R <= RightEnd) {
    if (A[L] <= A[R])
      TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
    else
      TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
  }

  while (L <= LeftEnd)
    TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
  while (R <= RightEnd)
    TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */

  for (i = 0; i < NumElements; i++, RightEnd--)
    A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}

void Msort(ElementType A[], ElementType TmpA[], int L,
           int RightEnd) { /* 核心递归排序函数 */
  int Center;

  if (L < RightEnd) {
    Center = (L + RightEnd) / 2;
    Msort(A, TmpA, L, Center);               /* 递归解决左边 */
    Msort(A, TmpA, Center + 1, RightEnd);    /* 递归解决右边 */
    Merge(A, TmpA, L, Center + 1, RightEnd); /* 合并两段有序序列 */
  }
}

void MergeSort(ElementType A[], int N) { /* 归并排序 */
  ElementType *TmpA;
  TmpA = (ElementType *)malloc(N * sizeof(ElementType));

  if (TmpA != NULL) {
    Msort(A, TmpA, 0, N - 1);
    free(TmpA);
  } else
    printf("空间不足");
}

int main() {
  ElementType A[100001], N;
  clock_t start, finish;
  cin >> N;
  for (int i = 0; i < N; i++)
    cin >> A[i];
  start = clock();
  InsertionSort(A, N);
  finish = clock();
  double duration = (finish - start) / CLOCKS_PER_SEC;
  // cout << "cost time: " << duration << "s" << endl;
  cout << A[0];
  for (int i = 1; i < N; i++)
    cout << " " << A[i];
  // cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

六、测试

各测试点数据如下，比较各种算法的性能：

数据1：只有1个元素；
数据2：11个不相同的整数，测试基本正确性；
数据3：103个随机整数；
数据4：104个随机整数；
数据5：105个随机整数；
数据6：105个顺序整数；
数据7：105个逆序整数；
数据8：105个基本有序的整数；
数据9：105个随机正整数，每个数字不超过1000。

插入排序：

希尔排序：（增量为N/2)

希尔排序：（增量为Sedgewick增量序列）：

堆排序：

归并排序：

可以看出堆排序的效果最好。