Jesonwoo's Blog

珍爱家人，珍惜财富，保持进步

0%

常用排序算法总结

发表于 更新于 分类于 ， Valine：

学习排序算法时的总结和记录

各种排序算法比较

排序 时间复杂度 空间复杂度 稳定性
直接插入排序 O(n^2) O(1) 稳定
希尔排序 根据增量序列的不同时间复杂度不同；可以很接近O(nlogn) O(1) 不稳定
冒泡排序 O(n^2) O(1) 稳定
快速排序 期望值O(nlogn),需要考虑数组几乎有序和存在大量重复元素的情况 O(1) 不稳定
归并排序 O(nlogn) O(n) 不稳定
堆排序 O(nlogn) O(n) 不稳定

直接插入排序（InsertSort）

1
2
3
4
5
6
7
8
9
10
11
12
template <typename T>
void SelectSort(T* arr, int n) {
    for (int i = 0; i < n; i++) {
        int idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[idx]) {
                idx = j;
            }
        }
        swap(arr[i], arr[idx]);
    }
}

希尔排序（ShellSort）

普通希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T>
void ShellSort(T* arr, int n) {
    for (int gap = n / 2; gap > 0; gap /= 2) {

        for (int i = gap; i < n; i++) {
            int j;
            T tmp = arr[i];
            for (j = i; j >= gap && arr[j - gap] > tmp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = tmp;
        }
    }
}

优化希尔排序（调整increment sequence）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
template<typename T>
void ShellSort(T arr[], int n) {

    int h = 1;
    while (h < n / 3)
        h = 3 * h + 1;
    // 计算 increment sequence: 1, 4, 13, 40, 121, 364, 1093...

    while (h >= 1) {
        // h-sort the array
        for (int i = h; i < n; i++) {

            // 对 arr[i], arr[i-h], arr[i-2*h], arr[i-3*h]... 使用插入排序
            T e = arr[i];
            int j;
            for (j = i; j >= h && e < arr[j - h]; j -= h)
                arr[j] = arr[j - h];
            arr[j] = e;
        }

        h /= 3;
    }
}

冒泡排序（BubbleSot）

1
2
3
4
5
6
7
8
9
10
template <typename T>
void BubbleSot(T* arr, int n) {
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

冒泡排序的优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// * 用一个变量flag记录下最后一个发生交换的位置，后面没有发生交换的已经有序 
// * 所以可以用这个值来作为下一次比较结束的位置 
template<typename T>
void BubbleSot(T *arr, int n)
{
    int flag = n;
    int j, k;
    for(int i = 0; i < flag; i++) {
        k = flag; //保存最后一次交换的位置下标
        flag = 0; //如果flag值不变则说明之后的数据有序，因此可退出程序
        for(j = 0; j < k; j++) {
            if(arr[j] > arr[j+1]) {
                flag = j;
                swap(arr[j], arr[j+1]);
            }
        }
    }
}

快速排序（QuickSort）

普通快排

​ 快排核心步骤就是partition操作，partition操作一般情况下就是以arr[l]元素（记为tmp）为基准将arr分为大于tmp和小于tmp两部分 ， 最终将其分为 arr[l … j] < tmp和arr[j+1 … r] > tmp两部分

partition

各个变量定义

  • l：arr左边界

  • r：arr有边界

  • i：准备进行判断比较的位置

  • j：arr[l ... j] < tmp，一开始 j == l 时表示没有元素小于tmp

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T>
int _Partition(T* arr, int l, int r) {
    int j = l;
    T tmp = arr[l];
    for (int i = l + 1; i <= r; i++) {
        if (arr[i] < tmp) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
    swap(arr[j], arr[l]);
    return j;
}

普通快排的缺陷

  • 当数组近乎有序的时候,算法会退化成O(n^2)级别的算法

​ 采用随机选择一个标定元素，则该排序的期望值为O(nlogn)，大概率上避免退化成O(n^2)；在partition一开始的位置 swap(arr[l], arr[(rand() % (r - l + 1)) + l]);

  • 当存在大量重复元素的时候,算法也会退化成O(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
28
29
30
31
32
33
34
35
36
template <typename T>
void _QuickSort3(T* arr, int l, int r) {
    // 当元素少于16个时，使用插入排序作为快速排序的自排序更为高效
    if (r - l <= 16) {
        InsertSort(arr + l, r - l + 1);
        return;
    }

    swap(arr[l], arr[(rand() % (r - l + 1)) + l]);

    int tmp = arr[l];
    int lt  = l;     // arr[l...lt] < tmp
    int gt  = r + 1; // arr[gt...r] > tmp
    int i   = l + 1; // arr[lt+1...i-1] == tmp

    while (gt > i) {
        if (arr[i] < tmp) {
            swap(arr[++lt], arr[i++]);
        } else if (arr[i] > tmp) {
            swap(arr[--gt], arr[i]);
        } else { // tmp == arr[i]
            i++;
        }
    }

    swap(arr[lt], arr[l]);

    _QuickSort3(arr, l, lt - 1);
    _QuickSort3(arr, gt, r);
}

template <typename T>
void QuickSort3(T* arr, int n) {
    srand(time(NULL));
    _QuickSort3(arr, 0, n - 1);
}

归并排序（MergeSort）

Merge操作

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
// 将arr[l, mid]和arr[mid+1, r]进行合并
template <typename T>
void _Merge(T* arr, int l, int mid, int r) {

    T* aux = new T[r - l + 1];
    for (int i = l; i <= r; i++) {
        aux[i - l] = arr[i];
    }
    int i = l;
    int j = mid + 1;
    for (int k = l; k <= r; k++) {
        if (i > mid) {
            arr[k] = aux[j - l];
            j++;
        } else if (j > r) {
            arr[k] = aux[i - l];
            i++;
        } else if (aux[i - l] < aux[j - l]) {
            arr[k] = aux[i - l];
            i++;
        } else {
            arr[k] = aux[j - l];
            j++;
        }
    }
    delete[] aux;
}

// 对于arr[l, r]进行归并排序;l,r是闭区间
template <typename T>
void _MergeSort(T* arr, int l, int r) {
    // arr长度不大于15的时候使用插入排序
    // 可提升算法效率
    if (r - l <= 15) {
        InsertSort(arr + l, r - l + 1);
        return;
    }
    if (l >= r) {
        return;
    }
    int mid = (r + l) / 2;
    _MergeSort(arr, l, mid);
    _MergeSort(arr, mid + 1, r);
    _Merge1(arr, l, mid, r);
}

template <typename T>
void MergeSort(T* arr, int n) {
    _MergeSort(arr, 0, n - 1);
}