数据结构知识点总结：排序_数据排序时,是否类型数据的是大于否

前言
 
  数据结构知识点总结文档：排序算法。该文档总结了9种经典的、或有着广泛使用的排序算法。

 
 

排序算法

 

算法分类

目前最常见的排序算法有十种，这十种算法可进一步分为：

• 比较类排序： 通过比较元素大小来决定相互之间的次序，由于复杂度不能突破 $n\log (n)$，因此也被称为非线性时间排序。

• 非比较类排序： 不通过比较元素大小来决定次序，可突破比较类排序的时间下限，以线性时间运行，因此也被称作线性时间排序

 

算法复杂度

• 稳定和不稳定指的是，如果 $x$ 的位置原本在 $y$ 前面，且 $x=y$, 经过排序后 $x$ 仍然在 $y$ 的前面，那么这种情况就是稳定。反之则是不稳定。

 
 
 

---

比较类排序

 
 
 

1.1 插入排序（Insertion Sort）

 

基本知识点

• 插入排序是一种简单直观的排序算法，它的原理就像我们在打扑克时对手牌进行排序一样，算法从前往后的扫描整个数组，扫描指针前的数组是已排序好的， 指针后的数组是未排序的，指针每访问到一个未排序数组中的元素，就在已排序数组中扫描一次，找到合适的位置后，把元素插入其中。具体的步骤可分为：

  • 1） 从数组的第一个元素开始，该元素可被视为已经排序好。
  • 2） 取出下一个元素，在已经排序好的数组中，从后往前扫描。
  • 3） 如果当前元素（已排序）大于待排序元素，则把该元素向后挪动一个位置。
  • 4） 重复步骤3，直到寻找到待排序元素合适的位置。
  • 5） 将待排序元素插入到当前元素后一个的位置。
  • 6） 重复步骤2~5，直到遍历整个数组。

• 由于插入排序首先要遍历一次整个数组，在访问每一个元素时，又要从后往前遍历一次已排序数组。因此插入排序的平均复杂度为 $O(n^2)$

• 适用场景： 适用于数据量不大，对算法的稳定性有要求，且数据局部或者整体有序的情况。

 

动图演示  

 

代码实现

#include <vector>
using namespace std;

void InsertionSort(vector<double>& data) {
    for (int i = 1; i < data.size(); i++) {
        double key = data[i];
        int j = i-1;

        while(j >= 0 && data[j] > key) {
            data[j+1] = data[j];
            j -= 1;
        }
        data[j+1] = key;
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

 
 

---

 

1.2 希尔排序（Shell Sort）

 

基本知识点

• 插入排序的思路很简单，就是不管数据如何分布，依然要对每个元素都一步一步进行比较，移动，插入。当数据是呈完全倒序分布时，最小的元素要归位到数组的前端就会很费劲，而这也是导致插入排序复杂度高的原因之一。

• 希尔排序在1959年由Shell发明。希尔排序本质上是插入排序经过改进后的高效版本，也被称作最小增量排序，是第一个突破 $O(n^2)$ 复杂度的算法。

• 希尔排序在插入排序的基础上，采用了跳跃式分组的策略。通过预先设定好的增量，把整个数组分割为若干组，再单独对每一个分组进行插入排序，随后逐步缩小增量，使每个分组所包含的元素越来越多，直到增量为1时，此时分组即为数组本身，即对整个数组进行正常的插入排序。

• 站在上帝视角来看，希尔排序通过分组排序，从宏观层面上使整个数组逐步趋向有序，小的元素基本在前，大的元素基本在后，到最后对整个数组进行插入排序时，对其中的大部份元素只需进行微调即可，不会涉及过多的数据移动。因此相对于插入排序有着更好的复杂度。

• 希尔具体步骤为：

  • 首先先确定好增量 $k$ 及增量序列。 确定和证明增量序列是一个数学难题，通常情况下会令初始增量 $k=length/2$，缩小增量继续以 $k=k/2$。
  • 假如数组中共有10个元素，初始增量 $k=5$，因此数组会被分成5个分组，每个分组各自含有2个元素，前后两个元素在数组中相隔 $k-1=4$ 个元素。随后对每个分组分别直接进行插入排序。
  • 增量缩小后为 $k=2$，因此数组会被分成2个分组，每个分组各自含有5个元素，分组内每个元素在数组中相隔 $k-1=1$个元素。随后直接进行插入排序。
  • 最后的增量为1，此时直接对整个数组进行插入排序。

• 适用场景： 如果使用已知最好的步长序列，希尔排序比直接插入排序要快，甚至在小数组中比快速排序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排。

 

动图演示  

 

代码实现

#include <vector>
using namespace std;

void InsertionSortWithIncrement(vector<double>& data, int k, int begin) {
    for (int i = begin+k; i < data.size(); i+=k) {
        double key = data[i];
        int j = i-k;

        while(j >= 0 && data[j] > key) {
            data[j+k] = data[j];
            j -= k;
        }
        data[j+k] = key;
    }
    return;
}

void ShellSort(vector<double>& data) {
    int k = data.size() / 2;

    while(k > 1) {
        for (int begin = 0; begin < k; begin++) {
            InsertionSortWithIncrement(data, k, begin);
        }
        k /= 2;
    }
    InsertionSortWithIncrement(data, 1, 0);
   
    return;
}
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

 
 

---

 

1.3 归并排序（Merge Sort）

 

基本知识点

• 归并排序是利用分治思想（Divide-and-Conquer）实现排序的算法。分治，本质上是把总问题通过递归分成若干个小问题，并对各个小问题求解，最后将求解后的小问题修补成总问题，从而得到总问题的解。

• 归并排序的具体步骤为：

  • 分： 把数组通过递归的方式分解成若干个子数组，一种常用的策略是把数组等分为两个子数组，直到数组中只剩下一个元素，这种策略也被称作 “二路归并排序”。 若采用二路归并，算法需要 $\log (n)$ 次递归才能完成分割。
  • 治： 当分无可分后，递归会开始返回。在这个过程中，我们需要把子数组合并成有序的总数组。
  • 对于待合并的两个子数组，我们需要额外申请两块内存来存放他们，然后用两个指针对两个子数组从前往后扫描（两边的扫描是同步进行的）。任意一边每扫描到新的元素时，就会使其与另一边当前扫描到的元素作比较，较小者会被先存放回总数组中，直到左右子数组的所有元素都以有序状态归位到总数组中。
  • 重复上述步骤直到递归完成返回。

• 适用场景： 适用于数据量较大，并且要求排序稳定的情况，但需要注意内存空间的开销。

 

动图演示  

 

代码实现

#include <vector>
using namespace std;

void Merge(vector<double>& data, int left, int mid, int right) {
    vector<double> LSubsequence(data.begin()+left, data.begin()+mid+2);     // Extract left subsequence to buffer
    vector<double> RSubsequence(data.begin()+mid+1, data.begin()+right+2);  // Extract right subsequence to buffer
    LSubsequence[LSubsequence.size()-1] = INT_MAX;  // In case the iterator out of boundary 
    RSubsequence[RSubsequence.size()-1] = INT_MAX;  // In case the iterator out of boundary

    int i = 0, j = 0;
    for (int k = left; k < right+1; k++) {          // Fill ordered elements back to origin sequence
        if (LSubsequence[i] <= RSubsequence[j]) {
            data[k] = LSubsequence[i];
            i++;
        }
        else {
            data[k] = RSubsequence[j];
            j++;
        }
    }
    return;
}

void MergeSort(vector<double>& data, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        MergeSort(data, left, mid);
        MergeSort(data, mid+1, right);
        Merge(data, left, mid, right);
    }
    return;
}

void MergeSort(vector<double>& data) {
    MergeSort(data, 0, data.size()-1);
    return;
}
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

 
 

---

 

1.4 选择排序（Selection Sort）

 

基本知识点

• 选择排序是一种简单直观的排序算法，算法的思路是通过逐一在数组的未排序区找到其中的最小的元素，将其移动到已排序区中的末尾，一次类推，直至未排序区为空，从而完成排序

• 选择排序的具体步骤为：

  • 初始状态下，未排序区为整个数组，已排序区为空。
  • 从前往后扫描未排序区，找到其中最小的元素，使之与未排序区的首个元素的位置互换。
  • 此时已排序区不为空，使用一个指针记录已排序区的末尾，即未排序区的首个元素。
  • 重复第2~3步骤，直到未排序区为空。

• 适用场景： 由于是循环地选出待排序数据中的最小或最大值，插入到有序队列中，相对于冒泡排序减少了交换的次数。适用于当数据量不大，且对稳定性没有要求的场景。

 

动图演示  

 

代码实现

#include <vector>
using namespace std;

void Swap(vector<double>& data, int indexA, int indexB) {
    double temp = data[indexA];
    data[indexA] = data[indexB];
    data[indexB] = temp;
    return;
} 

int FindMinIndex(vector<double>& data, int begin) {
    double min = data[begin];
    int minIndex = begin;

    while (begin != data.size()) {
        if (data[begin] <= min) {
            minIndex = begin;
            min = data[begin];
        }
        begin ++;
    }
    return minIndex;
}

void SelectionSort(vector<double>& data) {
    for (int i = 0; i < data.size(); i++) {
        int minIndex = FindMinIndex(data, i);
        Swap(data, i, minIndex);
    }
    return;
}
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

 
 

---

 

1.5 堆排序（Heap Sort）

 

基本知识点

• 堆排序是利用了堆（heap）这种数据结构所设计出来的排序算法，因此要理解堆排序，首先就要理解堆。

• 堆本身是二叉树中的一种。堆具有以下性质：堆中任意一个节点的数值都要比其左右子节点大，这种堆被称作大顶堆（Max-Heap）；堆中任意一个节点的数值都要比其左右子节点小，这种堆被称作小顶堆（Min-Heap）。

• 此外，堆可以通过数组的形式来储存。可发现，对于堆中任意一个节点，若其索引值为 $n$，其左右子节点的索引值分别为 $2n+1$ 与 $2n+2$，其父节点的索引值为 $\lfloor (n-1)/2\rfloor$，如下图所示：

Max-Heap         50
               /    \
             45      40     
            /  \    /  \        ------>   array:  50 | 45 | 40 | 20 | 25 | 35 | 30 | 10 | 15
          20   25  35  30                 index:   0    1    2    3    4    5    6    7    8
         /  \
        10  15
1
2
3
4
5
6
7

• 堆排序的具体步骤为：

  • 首先把初始数组看作是一个无规则的二叉树结构
  • 从树的最后一个不为叶节点的节点开始把二叉树调整为大顶堆。
  • 调整完毕后，把堆顶元素与堆底元素的位置互换，同时使堆大小减1，对缩减后剩余的堆执行维护其大顶堆性质的操作。
  • 重复步骤3直到堆的大小为1。

• 适用场景： 堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。适用于数据量大，

 

动图演示  

 

代码实现

#include <vector>
using namespace std;

void Swap(vector<double>& data, int indexA, int indexB) {
    double temp = data[indexA];
    data[indexA] = data[indexB];
    data[indexB] = temp;
    return;
} 

/* Maintain Heap Properties */
void MaxHeapify(vector<double>& data, int node, int heapSize) {
    int lChild = 2*node + 1;
    int rChild = 2*node + 2;

    int MaxChildIndex = node;
    if (lChild <= heapSize && data[lChild] > data[MaxChildIndex])
        MaxChildIndex = lChild;
    if (rChild <= heapSize && data[rChild] > data[MaxChildIndex])
        MaxChildIndex = rChild;

    if (MaxChildIndex != node) {
        Swap(data, node, MaxChildIndex);
        MaxHeapify(data, MaxChildIndex, heapSize);
    } 
    return;
}

void HeapSort(vector<double>& data) {
    int heapSize = data.size()-1;

    for (int i = data.size()/2-1; i >= 0; i--) {    // Build Max-Heap
        MaxHeapify(data, i, heapSize);
    }
    for (int i = data.size()-1; i > 0; i--) {
        Swap(data, 0, i);
        heapSize --;
        MaxHeapify(data, 0, heapSize);
    }
}
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

 
 

---

 

1.6 冒泡排序（Bubble Sort）

 

基本知识点

• 冒泡排序是一种简单的排序算法。它重复地扫描要排序的数组，一次比较两个元素，如果它们的顺序错误就把它们交换过来，直到无需再进行交换，即该数组已经排序完成。由于较小的元素会经由交换慢慢“浮”到数组的前端，因此该算法被称为冒泡排序。

• 冒泡排序的具体步骤为：

  • 比较相邻的元素。如果第一个比第二个大，就交换双方的位置。
  • 从数组的前端开始，对每一组相邻的元素做相同的比较，当比较完数组中所有的相邻对后，最大的元素会位于数组的末尾。该元素同时也出于已排序区中。
  • 重复上述步骤，直到未排序区为空。

• 适用场景： 此排序算法适用于数据量量不大，对稳定性有要求，且数据基本有序的情况下。

 

动图演示  

 

代码实现

#include <vector>
using namespace std;

void Swap(vector<double>& data, int indexA, int indexB) {
    double temp = data[indexA];
    data[indexA] = data[indexB];
    data[indexB] = temp;
    return;
} 

void BubbleSort(vector<double>& data) {
    int length = data.size();
    
    for (int i = 0; i < length; i++) {
        for (int j = 0; j < length-i-1; j++) {
            if (data[j] > data[j+1]) 
                Swap(data, j, j+1);
        }
    }
    return;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

 
 

---

 

1.7 快速排序（Quick Sort）

 

基本知识点

• 冒泡排序的思路是通过逐一交换元素，从而使数组达到有序。然而逐一的交换需要耗费大量的时间，导致冒泡排序的复杂度达到了 $O(n^2)$ 之久。快速排序沿用了冒泡排序交换元素的思想，同时能够极大的优化其复杂度，因此快速排序在计算机领域中有着广泛的运用。

• 快速排序的具体步骤是：

  • 记录当前数组初始位置的元素的数值，把其记为 “标杆（Pivot）”
  • 设置两个指针，左指针位于数组初始端，右指针位于数组末尾端。
  • 先令右指针从右往左扫描，当扫描到比标杆小的元素时停下。
  • 接着令左指针从左往右扫描，当扫描到比标杆大的元素时停下，此时互换左右指针所指向的元素。
  • 重复上述两步，直到左右指针均指向同一个元素。
  • 互换标杆元素以及指针所指向的元素的位置。
  • 递归式地对标杆元素以左，以及标杆元素以右的子数组执行步骤1~6，直到数组无法被继续分割为止。

• 通过与 “标杆” 进行比较的排序方式存在一个隐患，那即是若标杆的数值很极端，比如恰好等于整个数组中的最大值，或最小值。那么指针扫描完整个数组也无法完成进行一次交换，导致算力被浪费。在最坏的情况下为数组以倒序排列，这种情况下快速排序需要重复地扫描整个数组，因此时间复杂度为 $O(n^2)$。

• 针对这种情况的一种优化方式是 “三数取中法（Mid-3）"，即先用数组初始位置的元素，中间位置的元素，以及末尾位置的元素作比较，取三者的中间值者作为标杆，再进行快速排序。

• 适用场景： 此排序算法的效率在序列越乱的时候，效率越高。在数据有序时，会退化成冒泡排序。

• 优化方法： 当待排序序列的长度分割到一定大小后，使用插入排序；或是在一次分割结束后，可以把与pivot相等的元素聚集在一起，下一次分割时，不必再对与pivot相等的元素分割。

• 额外应用： 求数组中第k小的数。将数组中某一个元素m作为划分依据。若m前面的元素个数大于k，则第k小的数一定在m前面的元素中，这时我们只需要继续在m前面的元素中找第k小的数；若m前面的元素小于k，则第k小的数一定在m后面的元素中，这时我们只需要在m后面的元素中找第k小的数；

 

动图演示  

 

代码实现

#include <vector>
using namespace std;

void Swap(vector<double>& data, int indexA, int indexB) {
    double temp = data[indexA];
    data[indexA] = data[indexB];
    data[indexB] = temp;
    return;
} 

void Mid3(vector<double>& data, int begin, int end) {
    int mid = (begin + end) / 2;
    if (data[begin] > data[mid])    // Compare the first and second element
        Swap(data, begin, mid);
    if (data[mid] > data[end])      // Compare the second and third element
        Swap(data, mid, end);
    if (data[begin] <= data[mid])   // Compare the first and third element
        Swap(data, begin, mid);
    return;
}

void QuickSort(vector<double>& data, int begin, int end) {
    if (begin == end)               // Directly return if there are only one element 
        return;
    if (end - begin + 1 >= 3)       // Apply mid-3 strategy if sequence size >= 3
        Mid3(data, begin, end);

    int pivot = data[begin];
    int lpointer = begin;
    int rpointer = end;

    while(lpointer != rpointer) {
        while (rpointer > lpointer && data[rpointer] > pivot)
            rpointer --;
        while (lpointer < rpointer && data[lpointer] <= pivot)
            lpointer ++;
        Swap(data, lpointer, rpointer);
    }
    Swap(data, begin, lpointer);

    if (begin < lpointer)
        QuickSort(data, begin, lpointer-1);
    if (end > lpointer)
        QuickSort(data, lpointer+1, end);
    return;
}

void QuickSort(vector<double>& data) {
    QuickSort(data, 0, data.size()-1);
    return;
}
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

 
 
 

---

非比较类排序

 
 
 

2.1 计数排序（Counting Sort）

 

基本知识点

• 计数排序在1954年由 Harold H. Seward 发明，算法采取了空间换时间的策略，核心思路是通过额外的内存空间记录数组元素的信息，并利用这些信息对数组进行调整，从而使数组达到有序状态。

• 计数排序的具体步骤是：

  • 找到待排序数组中的最大元素，记为 $max$。
  • 新建一个数组 $count$ 用于计数，其大小为 $max+1$，所有元素的初始值均为 $0$。
  • 遍历初始数组，以元素的数值作为 $count$ 数组中的索引值，以元素出现的次数作为 $count$ 数组的元素值。
  • 新建一个空数组 $result$，其大小与待排序数组相同。
  • 遍历 $count$ 数组，若当前元素值为 $0$，则跳过该元素。若大于 $0$，则将其对应的索引值作为 $result$ 数组中的元素值填充到 $result$ 中，每处理一次，$count$ 数组中的元素值减1，直到该元素值为 $0$。
  • $result$ 即为已排序好的数组。

        原始        index:  0  1  2  3  4  5  6  7  8  9
        数组        value:  0  2  5  3  7  9 10  3  7  6
       -------------------------------------------------------------
        计数        index:  0  1  2  3  4  5  6  7  8  9  10 
        数组        value:  0  0  0  0  0  0  0  0  0  0   0
       -------------------------------------------------------------
        完成        index:  0  1  2  3  4  5  6  7  8  9  10
        计数后      value:  1  0  1  2  0  1  1  2  0  1   1
       -------------------------------------------------------------
        结果        index:  0  1  2  3  4  5  6  7  8  9
        数组        value:  0  2  3  3  5  6  7  7  9 10
1
2
3
4
5
6
7
8
9
10
11

• 上述的算法存在一个隐患，若待排序的数组为 $[105,103,102,104,101]$，算法会创建出一个大小为 $106$ 的数组。但实际需要排序的元素只有5个，那么 $[0,100]$ 的内存空间就都浪费了。

• 针对这种情况，一种优化策略是除了找到数组的最大值以外，还要找到数组的最小值。令 $count$ 数组的大小为 $max-min+1$。那么初始数组的元素值与 $count$ 数组中的索引值的对应关系为：$inde{x}_{count}=valu{e}_{data}-min$；$count$ 数组的索引值与 $result$ 数组的元素值的对应关系为 $valu{e}_{result}=inde{x}_{count}+min$

        原始        index:   0   1   2   3   4   5
        数组        value:  107 103 107 105 101 102
       ------------------------------------------------
        完成        index:   0  1  2  3  4  5  6 
        计数后      value:   1  1  1  0  1  0  2
       ------------------------------------------------
        结果        index:   0   1   2   3   4   5
        数组        value:  101 102 103 105 107 107
1
2
3
4
5
6
7
8

 

动图演示  

 

代码实现

#include <vector>
using namespace std;

void CountingSort(vector<double>& data) {
    int max = INT_MIN;
    int min = INT_MAX;
    for (auto value : data) {     // Finding the maximum and minimum value of the sequence
        if (value > max)
            max = value;
        if (value < min)
            min = value;
    }

    vector<double> count(max-min+1, 0);         // Creating counting sequence
    for (auto value : data) {
        count[value-min] += 1;
    }

    int j = 0;
    for (int i = 0; i < count.size(); i++) {
        while (count[i] > 0) {
            data[j] = i + min;
            count[i] -= 1;
            j += 1;
        }
    }
}
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

 
 

---

 

2.2 桶排序（Bucket Sort）

 

基本知识点

• 桶排序是计数排序的扩展版本，算法的思路是利用映射函数，将数据分到有限数量的子数组或链表里（即我们所说的桶），每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。最后，依照顺序把非空桶中的元素逐个放回到原序列中，从而使数组达到有序状态。

• 计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素。因此桶排序需要尽量保证元素经过映射后的分布是均匀的，否则当所有数据集中在同一个桶中时，桶排序就会丧失其复杂度优势。

	array:  78  17  39  26  72  94  21  12  23  68

					  	-----
					0 	| / |
					1	|	| ---> 12 ---> 17
					2 	|	| ---> 21 ---> 23 ---> 26
	bucket: 	    3	|	| ---> 39
					4	| / |
					5	| / |
					6	|	| ---> 68
					7	|	| ---> 72 ---> 78
					8	| / |
					9	|	| ---> 94
						-----
1
2
3
4
5
6
7
8
9
10
11
12
13
14

 

代码实现

#include <vector>
using namespace std;

void BucketSort(vector<double>& data){
    int max = INT_MIN;
    int min = INT_MAX;
    for (auto value : data) {     // Finding the maximum and minimum value of the sequence
        if (value > max)
            max = value;
        if (value < min)
            min = value;
    }
    
    int bucketNum = (max - min) / data.size() + 1;          // Calculating bucket number
    vector<double> bucket;
    vector<vector<double>> bucketMap(bucketNum, bucket);    // Initialize buckets

    for (auto value : data) {
        int index = (value - min) / data.size();
        int j = 0;

        while (j < bucketMap[index].size()) {               // Put elements into buckets and sort the buckets
            if (bucketMap[index][j] > value)
                break;
            j++;
        }
        bucketMap[index].insert(bucketMap[index].begin()+j, value);
    }

    int j = 0;
    for (int m = 0; m < bucketNum; m++) {                   // Extract data from buckets to form ordered sequence
        for (int n = 0; n < bucketMap[m].size(); n++) {
            data[j] = bucketMap[m][n];
            j++;
        }
    } 
}
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

 
 
 

---

参考文献

Thomas, H., Charles, E., Ronald, L., Clifford, S. (2009). Introduction to Algorithms (3rd Edition)
 
一像素. (2017). 十大经典排序算法. Retrieved from https://www.cnblogs.com/onepixel/articles/7674659.html

 
原创博客，不得转载、抄袭