在之前的基础上将快速排序和归并排序重写形成了模板 在y 总那里学来的 ~

排序算法

快速排序

快速排序思想

快速排序的思想：基于分治的思想 选择一个分界点 使分界点的左侧的值比它小，右侧的值比它大， 不满足则交换，递归直到数组有序。

步骤

  • 快速排序算法的步骤：

    1. 确定数组的分界点 一般为arr[l], arr[(i + l) / 2], arr[r] 或随机
    2. 调整区间 假设边界点为x，小于等于x在x左边， 大于等于x的在x右边。
    3. 递归执行此过程，直到数组的为有序的。

代码实现

  • 结合以上的思路快速排序代码:

    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
    /*
    快速排序的代码模板的使用
    */
    #include <iostream>
    #include <cstdio>
    using namespace std;
    const int N = 1e6 + 10;
    int n, q[N];
    // 以左边的值为边界点 进行排序
    void quick_sort(int q[], int l, int r){
        if (l >= r) return ;
        int temp = q[l], i = l - 1, j = r + 1;
        while (i < j){
            do i ++; while (q[i] < temp);
            do j --; while (q[j] > temp);
            if (i < j) swap(q[i], q[j]);
        }
        quick_sort(q, l, j), quick_sort(q, j + 1, r);
    }
    int main(){
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
        quick_sort(q, 0, n - 1);
        for (int i = 0; i < n; i ++ ) printf("%d", q[i]);
       return 0;
    }

  • 快速排序代码的模板为：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void quicksort(int q[], int l, int r){
        if (l >= r) return ;
        int temp = q[l], i = l - 1, j = r + 1;
        while (i < j){
            do i ++; while (q[i] < temp);
            do j --; while (q[j] > temp);
            if (i < j) swap(q[i], q[j]);
        }
        quick_sort(q, l, j), quick_sort(q, j + 1, r);
    }

归并排序

思想

  • 归并排序的思想：分治的思想，将给定的数组不断二分，保证被

步骤

  • 是想排序的步骤 ：
    1. 找分界点 mid = r + l >> 1
    2. 由left right递归排序
    3. 将分割的数组归并为一

代码实现

  • 归并排序的代码实现：

    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
    /*
    归并排序的代码模板的使用
    */
    #include <iostream>
    #include <cstdio>
    using namespace std;
    const int N = 1e6 + 10;
    int n, q[N], tmp[N];
    // 以左边的值为边界点 进行排序
    void merge_sort(int q[], int l, int r){
        if (l >= r) return;
        //找到区间中点
        int mid = (l + r) / 2;
        //递归执行 区间划分
        merge_sort(q, l, mid);
        merge_sort(q, mid + 1, r);
        int k = 0, i = l, j = mid + 1;
        //归并为一排序
        while (i <= mid && j <= r){
            if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
            else tmp[k ++ ] = q[j ++ ];
        }
        while (i <= mid) tmp[k ++ ] = q[i ++ ];
        while (j <= r) tmp[k ++ ] = q[j ++ ];
        //保存到原数组中
        for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    }
    int main(){
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
        merge_sort(q, 0, n - 1);
        for (int i = 0; i < n; i ++ ) printf("%d ", q[i]);
       return 0;
    }

  • 由此得到归并排序的代码模板为 ：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    void merge_sort(int q[], int l, int r){
        if (l >= r) return;
        int mid = (l + r) / 2;
        merge_sort(q, l, mid);
        merge_sort(q, mid + 1, r);
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r){
            if (q[i] < q[j]) tmp[k ++ ] = q[i ++ ];
            else tmp[k ++ ] = q[j ++ ];
        }
        while (i <= mid) tmp[k ++ ] = q[i ++ ];
        while (j <= r) tmp[k ++ ] = q[j ++ ];
        for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
    }

分析

时间复杂度的分析：

归并排序的时间复杂度为 {nlogn} ,如何计算的呢？

  1. 长度为n的数组每次将它分为两部分不断执行此过程， 划分为n个长度为1的数组，那么需要划分的次数为 {logn} 次 （以2为底数）。
  2. 而每层加起来的比较的次数为n
  3. 所以时间复杂度为 {nlogn}