排序算法

Posted on Edited on

排序算法是最基本最常用的算法，是算法与数据结构的基础，也是面试中常见的一类问题。

插入排序 Insertion sort

插入排序方法类似于我们整理手上的扑克牌，在数据量小的时候是一种高效的的排序算法。

插入排序通常只需要用到O(1)的额外空间：

  1. 从第一个元素开始，该元素可以认为已经被排序
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

伪代码

升序

示例代码

1
2
3
4
5
6
7
8
9
10
11
void insertionSort(vector<int> &a) {
    for(int j = 1;j<a.size();j++) {
        int key = a[j];
        int i = j - 1;
        while (i>=0 && a[i]>key) {
            a[i+1] = a[i];
            i-- ;
        }
        a[i+1] = key;
    }
}

归并排序

归并排序是分治法的一个实现：

Divide： 把长度为n的序列分成两个长度为n/2的子序列

Conquer：递归的使用归并排序将子序列排序

Combine：将两个排好序的子序列合并成一个序列

伪代码：

归并操作：

例如上图所示，归并操作将A分成L和R两个数组，然后根据每个元素的大小依次将元素重新填入到A中。

归并排序：

代码

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
//C++
void merage(vector<int> &A,int p, int q, int r) {
    int n1 = q - p +1;
    int n2 = r - q;
    vector<int> L(n1+1), R(n2+1);
    for (int i = 0; i < n1; i++) {
        L[i] = A[p+i-1];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = A[q + j];
    }
    
    L[n1+1] = INT_MAX;
    R[n1+1] = INT_MAX;
    int i = 0;
    int j = 0;
    
    for(int k = p;k<r;k++) {
        if(L[i]<=R[j]) {
            A[k] = L[i];
            i++;
        }
        else {
            A[k] = R[j];
            j++;
        }
        
    }
}

void merage_sort(vector<int> &A,int p, int r) {
    if (p<r) {
        int q = int((p+r-0.5)/2);
        merage_sort(A, p, q);
        merage_sort(A, q+1, r);
        merage(A, p, q, r);
    }
}

冒泡排序

冒泡排序是一种简单的排序方法，通过重复的走访需要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

冒泡排序的运作如下：

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

伪代码

代码

1
2
3
4
5
6
7
8
9
void bubbleSort(vector<int> &a) {
    for (int i = 0; i<a.size(); i++) {
        for(int j = a.size()-1;j>i+1;j--) {
            if (a[i]>a[j]) {
                swap(a[i], a[j]);
            }
        }
    }
}

参考资料：

Introduction to Algorithms Thomas H. Cormen

https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F