梅庄

算法回顾---nlogn排序算法

发表于 | 分类于
归并排序&快速排序

nlogn排序

自顶向下的递归Merge Sort

分成一半，再逐渐归并
二分法达到不同的层级，每个层级用O(N)的算法来做事情
8 6 2 3 | 1 5 7 4
2 3 6 8 | 1 4 5 7
1 2 3 4 5 6 7 8
需要开辟同样大小的临时空间，来辅助完成归并过程
(即需要O(N)的额外空间来完成排序)
3个索引位置
i,j指向的是当前正在考虑的元素
k 指向的是比较之后，最终应该放到的数组的位置(指下一个需要放的位置)

基础版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// 将arr[l……mid]和arr[mid+1……r]两部分进行归并 
template<typename T>
void __merge(T arr[], int l, int mid, int r)
{
    int i = l, j = mid+1; //i指向A[L1],j指向A[L2]
    int temp[maxn], index = 0;  //temp临时存放合并后的数组，index为其下标
    while (i <= mid && j <= r)
    {
        if (arr[i] <= arr[j])
        {
            temp[index++] = arr[i++];
        }
        else
        {
            temp[index++] = arr[j++];
        }
    }
    while (i <= mid)  temp[index++] = arr[i++];
    while (j <= r)  temp[index++] = arr[j++];
    for (int k = 0; k<index; k++)
    {
        arr[l + k] = temp[k];    //将合并后的序列赋值回数组A
    }
}

Random情况下
n = 10 0000

排序算法 所用时间
Merge Sort 0.077s
Insertion Sort 37.266s

但是在数值近乎有序的情况下，Insertion Sort效果要好于Merger Sort
近乎有序情况下（10 0000中有100个数据调换位置）
n = 10 0000

排序算法 所用时间
Merge Sort 0.051s
Insertion Sort 0.027s

改进版本1

只在arr[mid] > arr[mid+1]的情况下才merge

1
2
3
4
5
6
7
8
9
10
11
// 递归使用归并排序，对arr[l……r]的范围内进行排序
template<typename T>
void __mergeSort(T arr[], int l, int r) 
{
    if(l >= r)    return;
    int mid = l + (r - l)/2;
    __mergeSort(arr, l, mid);//[l……mid]是有序的
    __mergeSort(arr, mid+1, r);//[mid+1……r]是有序的
    **if(arr[mid] > arr[mid+1])**
    __merge(arr, l, mid, r);
}

近乎有序情况下（10 0000中有100个数据调换位置）
n = 10 0000

排序算法 所用时间
Merge Sort 0.014s
Insertion Sort 0.027s

改进版本2

当元素数量比较少的时候，用插入排序

  1. 因为当元素数量比较少的时候，元素近乎有序的可能性比较大
  2. 数量级前面的系数，插入排序比归并排序要小
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    // 递归使用归并排序，对arr[l……r]的范围内进行排序
    template<typename T>
    void __mergeSort(T arr[], int l, int r) 
    {
    //    if(l >= r)    return;
    **    if(r - l <= 15) 
        {
            insertionSort(arr, l, r);
            return;
        }**
        int mid = l + (r - l)/2;
        __mergeSort(arr, l, mid);
        __mergeSort(arr, mid+1, r);
        if(arr[mid] > arr[mid+1])     
        __merge(arr, l, mid, r);
    }

自底向上的迭代Merge Sort

1
2
3
4
5
6
7
8
9
10
11
12
template<typename T>
void mergeSortBU(T arr[], int n) 
{
    for(int sz = 1; sz <= n; sz += sz)
    {
        for(int i = 0; i + sz < n; i += sz + sz)
        {
            //对arr[i ……i+sz-1]和arr[i+sz……i+2*sz-1]进行归并 
            __merge(arr, i, i+sz-1, min(i+sz+sz-1, n-1));
        }
    }
}

近乎有序情况下（10 0000中有100个数据调换位置）
n = 10 0000

排序算法 所用时间
Merge Sort 0.03s
Insertion Sort 0.065s

注意两部分越界：

  1. 第二部分起始超过n
  2. 第二部分结束部分超过n

统计来说，递归的稍微快一点

但迭代的方法可以对链表进行排序（没有要求用数组）

Quick Sort

每次选好一个元素，想办法把它移到（在已经排好序情况下）的位置

之后，分别对小于4的部分和大于4的部分分别递归地使用快速排序

Partition

将数组元素分成两个部分

e>v

直接放在>v的后面，然后i++

e<v

先交换，然后j++,i++

结果

基础版Quick Sort

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
//对arr[l……r]部分进行partition操作
//返回p,使得arr[l……p-1] < arr[p]; arr[p+1……r] > arr[p] 
template<typename T>
int __partition(T arr[], int l, int r)
{
    T v = arr[l];
    //arr[l+1……j] < v; arr[j+1……i) > v 
    int j = l;
    for(int i = l+1; i<=r; i++)
    {
        if(arr[i] < v)
        swap(arr[++j], arr[i]);
    }
    swap(arr[j], arr[l]);
    return j;
}
template<typename T>
//对arr[l……r]部分进行快排 
void __quickSort(T arr[], int l, int r)
{
    if( l >= r) return;
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p-1);
    __quickSort(arr, p+1, r);  //千万注意这里是p+1
}
template<typename T>
void quickSort(T arr[], int n)
{
    __quickSort(arr, 0, n-1);
}
排序算法 所用时间
Merge Sort 0.029s
Merge SortBU 0.031s
Quick Sory 0.006s

但是在近乎于有序的情况下，这种快速排序很慢

基于logn层的，归并排序可以保证每次都是平均分

最坏的情况

改进1—随机选择pivot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template<typename T>
int __partition3(T arr[], int l, int r)
{
    **swap(arr[rand()%(r-l+1)+l], arr[l]);**
    T v = arr[l];
    //arr[l+1……j] < v; arr[j+1……i) > v 
    int j = l;
    for (int i = l + 1; i <= r; i++)
    {
        if (arr[i] < v)    swap(arr[++j], arr[i]);
    }
    swap(arr[j], arr[l]);
    return j;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<typename T>
int __partition3(T arr[], int l, int r)
{
    swap(arr[rand()%(r-l+1)+l], arr[l]);
    T v = arr[l];
    //arr[l+1……j] <= v; arr(j……r] >= v 
//    下面这个处理不了有相同元素的情况 
    int tmp = arr[l] ;
    while(l < r)
    {
        while(l < r && arr[r] > tmp)    r--;
        arr[l] = arr[r];
        while(l < r && arr[l] <= tmp)    l++;
        arr[r] = arr[l];
    }
    arr[l] = tmp;
    return l;
    
}

随机选择pivot并与第一个元素交换
此时，最坏时间复杂度仍然为O(N^2)，但是退化到这种最坏情况的可能下近乎为0（需要保证每次选择的pivot均为最小值）
在元素近乎有序的情况下明显好于partition1

改进2—双指针+均衡分配相等元素

当近乎有序的情况下，快速排序仍然会很慢，退化成O（N^2）

可能会造成分成的两块极度不均衡

最大的区别：
把等于v的元素分散到两部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
template<typename T>
int __partition2(T arr[], int l, int r)
{
    swap(arr[rand()%(r-l+1)+l], arr[l]);
    T v = arr[l];
    //arr[l+1……j] <= v; arr(j……r] >= v 
    int i = l+1, j=r;
    while(true)
    {
        while(i<=r && arr[i] < v)    i++;
        while(j >= l+1 && arr[j] > v)    j--;
        if(i > j)    break;
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    swap(arr[l], arr[j]);
    return j;
}

在存在大量重复元素的情况下要明显好于partition3

Quick Sort 3 ways（三路快速排序）

1） e ==v

2) e < v
与==v的第一个元素交换

3) e > v
与gt-1交换，成为大于v的第一个元素（接着gt–)

结果

然后只需要将l和lt交换即可

优点：不需要对大量==v的元素交换，在存在大量==v的元素的时候相当可以

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
//三路快速排序处理arr[l……r]
//将arr[l……r]分为 < v; ==v; >v 三部分
//之后递归对<v; >v两部分继续进行三路快速排序
template<typename T>
void __quickSort3Ways(T arr[], int l, int r) 
{
    if(r - l <= 12)
    {
        insertionSort(arr, l , r);
        return;
    }
    //partition
    swap(arr[l], arr[rand()%(r-l+1)+l]);
    T v = arr[l];
    int lt = l;    //arr[l+1……lt] < v
    int gt = r + 1;    //arr[gt……r] > v 
    int i = l+1;    //arr[lt+1……i) == v
    while( i < gt ) 
    {
        if(arr[i] < v)    
        {
            swap(arr[i], arr[lt+1]);
            lt++;
            i++;
        }
        else if(arr[i] > v)
        {
            swap(arr[i], arr[gt-1]);
            gt--;
        }
        else{
            i++;
        }
    }
    swap(arr[l], arr[lt]);
    __quickSort3Ways(arr, l, lt-1);
    __quickSort3Ways(arr, gt, r);
}

在测试中，三路快排在存在大量重复元素的数组中性能要远远好于其他，（但其他case稍稍慢一点点）
虽然是nlogn的算法，但快速排序在性能上要好于归并排序
一般系统级程序中，多用quickSort3Ways
因为它在处理大量重复键值的情况下优势明显，在处理其他情况性能也可以保障

Merge Sort 和 QuickSort的衍生问题

Merge Sort和 Quick Sort都使用了分治算法
思考：前人是如何想出来的

逆序对

  1. 考察每一个数对O(n^2)

  2. 归并排序求逆序对

    取出数组中第n大的元素

    （退化）取数组中最大值和最小值（从头遍历O（N））
    1.先排序，再索引O（nlog)
    2.用快速排序的思路