归并排序

归并排序的思路就是：

  • 排序好数组 1
  • 排序好数组 2
  • 然后将两个数组合并

时间复杂度：

对n个元素进行排序的时间，T（n) = O(nlogn)

利用递归表达式来推导时间复杂度如下：

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
void Merge(int a[], int s, int m, int e, int tmp[]){
    // O(n)
    // 对区间 [s, m] 和 [m + 1, e]两个区间的数组进行合并,存储到tmp；
    // 然后保证tmp有序，然后再将tmp的内容拷贝会 a[s, e]
	int pb = 0;   // tmp 数组的下标
	int p1 = s;   // p1, p2 为两个区间的开始索引指针
	int p2 = m + 1; 
    while(p1 <= m && p2 <= e){ // 在两个子数组中，比较两个指针指向的两个数，
        if(a[p1] < a[p2]){    // 较小的数存入tmp，同时索引递增
            tmp[pb++] = a[p1++]; //直到有其中一个子数组所有值已经被复制到tmp后停止
        }
        else{
            tmp[pb++] = a[p2++]
        }
    }
    // 这里直接按顺序将未写入到tmp的数写入。因为底层归并时，已经排序好了。
    while( p1 <= m){
        tmp[pb++] = a[p1++];
    }
    while( p2 <= e){
        tmp[pb++] = a[p2++];
    }
    // 复制值回到原始数组
    for(int i = 0; i < pb; i++){
        a[s + i] = tmp[i];
    }
}

void MergeSort(int a[], int s, int e, int tmp[]){
    /*
    a: 待排序的数组
    s：开始排序的下标
    e: 结束排序的下标
    tmp: 临时存放排序的数组
    */
    // 当开始下标和结束下标大小一致时，结束归并
    if (s < e){
        int m = s + (e - s) / 2;
        MergeSort(a, s, m, tmp);
        MergeSort(a, m, e, tmp);
        Merge(a, s, m, e, tmp);
    }
}

快速排序

快速排序也是一个典型的分治算法，其思想相当简洁：

  • 找到其中一个数k，将其挪到适当的位置，使得比 k 小的元素都排在左边，比k大的元素都排在右边
  • 然后对k的左边进行排序
  • 对k的右边进行排序

一般情况为 nlogn，最坏情况是 n^2；

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
void swap(int & a, int & b){
    int tmp = a;
    a = b;
    b = tmp;
}

void QuickSort(int a[], int s, int e){
    // a 为待排序的数组
    // s 为要处理的数组前索引
    // e 为要处理的数组后索引 s，e构成一个子数组
    if(s >= e)  // 当前后边界相等时，开始返回
        return;  
    int k = a[s];  // 选择子数组的第一个数，下一步将要为其挑选一个合适的位置，保证该位置的左边都
    			  // 小于k，右边都大于k
    int i = s;
    int j = e;
    while(i != j){
        while(j > i && a[j] >= k) --j;  // 当尾部的数e，大于k时，需要向前移动一位e--，
        							  // 继续比较直到小于k
        swap(a[i], a[j]); // 找到一个 j 指向的数min小于 k时，需要交换min，k的位置
        while(i < j && a[i] <= k) ++i; // 当前部的数s，小于k时，向后移动一位，
        							// 继续比较，直到大于 k
        swap(a[j], a[i]);  // 找到一个数，大于k，需要交换位置。
    } // 直到两个索引 i，j相等事，k已放置在合适的位置，左边小于k，右边大于k。
    QuickSort(a, s, i - 1); // 对 k 左右两边进行上述操作
    QuickSort(a, i + 1, e); 
}