十种排序

题目描述

给定你一个长度为 n 的整数数列。

请你使用快速排序对这个数列按照从小到大进行排序。

并将排好序的数列按顺序输出。

输入格式

输入共两行，第一行包含整数 n。

第二行包含 n 个整数（所有整数均在1∼109范围内），表示整个数。

输出格式

输出共一行，包含 n 个整数，表示排好序的数列。

数据范围

1 ≤ n ≤ 100000

输入样例：

5
3 1 2 4 5

输出样例：

1 2 3 4 5

代码

快速排序

(1) 时间复杂度
    a. 最好情况：O(nlogn)
    b. 平均情况：O(nlogn)
    c. 最坏情况：O(n^2)
(2) 空间复杂度
    O(logn)
(3) 不稳定

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010 ;

int n , q[N];

void quick_sort(int l , int r)
{
    if (l >= r) return ;
    int i = l - 1, j = r + 1 , x = q[l + r >> 1];
    //注意这里是取基准值x 而不是取他的下标 mid = l + r >> 1 , 因为 while中的下标mid的值不一定一直是x

    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap (q[i] , q[j]);
    }

    quick_sort(l , j);
    quick_sort(j + 1 , r);
}

int main()
{
    cin >> n ;

    for (int i = 0 ; i < n ; i ++) cin >> q[i] ;

    quick_sort(0 , n - 1);

    for (int i = 0 ; i < n ; i ++) cout << q[i] << " ";

    return 0;
}

直接插入排序

a. 时间复杂度
   [1] 最好情况：O(n)
   [2] 平均情况：O(n^2)
   [3] 最坏情况：O(n^2)
b. 辅助空间复杂度
   O(1)
c. 稳定

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010 ;

int n , q[N];

void insert_sort()
{
    for (int i = 1 ; i < n ; i ++)
    {
        int j = i , x = q[i];
        while (j && q[j - 1] > x) // >
        {
            q[j] = q[j - 1];
            j --;
        }
        q[j] = x;
    }
}

int main()
{
    cin >> n ;

    for (int i = 0 ; i < n ; i ++) cin >> q[i] ;

    //insert_sort();

    for (int i = 0 ; i < n ; i ++) cout << q[i] << " ";

    return 0;
}

折半插入排序

只是优化了直接插入排序的比较次数，但瓶颈在移动次数上，所以没有时间复杂度没有改变
    a. 时间复杂度
        [1] 最好情况：O(n)
        [2] 平均情况：O(n^2)
        [3] 最坏情况：O(n^2)
    b. 辅助空间复杂度
        O(1)
    c. 稳定

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010 ;

int n , q[N];

void binary_search_insert_sort()
{
    for (int i = 1 ; i < n ; i ++)
    {
        if (q[i - 1] < q[i]) continue; // 特判 //不需要比较，元素此时已在有序的位置

        int l = 0 , r = i - 1 , x = q[i] ;
        while (l < r)
        {
            int mid = l + r >> 1 ;
            if (q[mid] > x) r = mid ;
            else l = mid + 1;
        }

        for (int j = i ; j > l ; j --)
        {
            q[j] = q[j - 1];
        }
        q[l] = x;
    }
}

int main()
{
    cin >> n ;

    for (int i = 0 ; i < n ; i ++) cin >> q[i] ;

    binary_search_insert_sort();

    for (int i = 0 ; i < n ; i ++) cout << q[i] << " ";

    return 0;
}

冒泡排序

    (1) 时间复杂度
        a. 最好情况：O(n)
        b. 平均情况：O(n^2)
        c. 最坏情况：O(n^2)
    (2) 空间复杂度
        O(1)
    (3) 稳定

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010 ;

int n , q[N];

void bubble_sort()  // 冒泡排序
{
    for (int i = 0 ; i < n - 1 ; i ++) // n - 1 次
    {
        bool flag = true;
        for (int j = n - 1 ; j > i ; j --) // 从后往前冒到i
        {
            if (q[j - 1] > q[j])
            {
                swap (q[j - 1] , q[j]) ;
                flag = false ;
            }
        }
        if (flag) break;
    }

}

int main()
{
    cin >> n ;

    for (int i = 0 ; i < n ; i ++) cin >> q[i] ;

    bubble_sort();

    for (int i = 0 ; i < n ; i ++) cout << q[i] << " ";

    return 0;
}

简单选择排序

    (1) 时间复杂度
        a. 最好情况：O(n^2)
        b. 平均情况：O(n^2)
        c. 最坏情况：O(n^2)
    (2) 空间复杂度
        O(1)
    (3) 不稳定

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010 ;

int n , q[N];


void select_sort()
{
    for (int i = 0 ; i < n - 1; i ++)
     {
         int j = i;

         for (int k = j + 1 ; k < n ; k ++)
             if (q[k] < q[j]) j = k ;

         if (j != i) swap(q[i] , q[j]);
     }
}

int main()
{
    cin >> n ;

    for (int i = 0 ; i < n ; i ++) cin >> q[i] ;

    select_sort();

    for (int i = 0 ; i < n ; i ++) cout << q[i] << " ";

    return 0;
}

希尔排序

    (1) 时间复杂度
        O(n^(3/2))
    (2) 空间复杂度
        O(1)
    (3) 不稳定

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010 ;

int n , q[N];

void shell_sort()  // 希尔排序
{
    for (int d = n / 3 ; d ; d = d == 2 ? 1 : d / 3)//增量
    {
        for (int start = 0 ; start < d ; start ++)//分组的起点
        {
            for (int i = start + d ; i < n ; i += d)//各组分别插入排序
            {
                int j = i , x = q[i];
                while (j > start && q[j - d] > x) // j > start // x前全部是有序的q[j -d] > x
                {
                    q[j] = q[j - d];
                    j -= d;
                }
                q[j] = x ;
            }
        }
    }
}

int main()
{
    cin >> n ;

    for (int i = 0 ; i < n ; i ++) cin >> q[i] ;

    shell_sort();

    for (int i = 0 ; i < n ; i ++) cout << q[i] << " ";

    return 0;
}

归并排序

    (1) 时间复杂度
        a. 最好情况：O(nlogn)
        b. 平均情况：O(nlogn)
        c. 最坏情况：O(nlogn)
    (2) 空间复杂度
        O(n)
    (3) 稳定

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010 ;

int n , q[N];
int b[N];//归并排序的辅助数组

void merge_sort(int l , int r)
{
    if (l >= r ) return;

    int mid = l + r >> 1 ;

    merge_sort (l , mid) , merge_sort (mid + 1 , r);

    int k = 0 , i = l , j = mid + 1 ;// i = l 不是 0
    while (i <= mid && j <= r)
    {
        if (q[i] <= q[j]) b[k ++] = q[i ++];
        else b[k ++] = q[j ++];
    }

     while (i <= mid) b[k ++] = q[i ++]; 
     while (j <= r) b[k ++] = q[j ++]; 

    for (i = l , j = 0 ; j < k ; ) q[i ++] = b[j ++]; // i = l ,不是 0
}

int main()
{
    cin >> n ;

    for (int i = 0 ; i < n ; i ++) cin >> q[i] ;

    merge_sort(0 , n - 1);

    for (int i = 0 ; i < n ; i ++) cout << q[i] << " ";

    return 0;
}

堆排序

    (1) 时间复杂度
        a. 最好情况：O(nlogn)
        b. 平均情况：O(nlogn)
        c. 最坏情况：O(nlogn)
    (2) 空间复杂度
        O(logn)
    (3) 不稳定

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 100010 ;

int n , q[N];
int b[N];//归并排序的辅助数组
int sz ; //堆排序需要用的堆元素的个数

void down(int u)
{
    int t = u ;
    if (u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
    if (u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;
    if (t != u)
    {
        swap (q[u] , q[t]);
        down(t);
    }
}

void heap_sort()
{
    sz = n ;
    //建立大根堆
    for (int i = n / 2 ; i ; i --)
        down(i);

    //堆排序 ，每次堆顶元素与堆尾元素交换 (最大值排到末尾)， 知道堆内没有元素
    while (sz)
    {
        swap (q[1] , q[sz]);
        sz --;
        down (1);
    }
}

int main()
{
    cin >> n ;

    for (int i = 1 ; i <= n ; i ++) cin >> q[i] ;

    heap_sort(); // i 从 1 开始 

    for (int i = 1 ; i <= n ; i ++ ) cout << q[i] << " ";

    return 0;
}

桶排序(计数排序) 和 基数排序

1. 桶排序
    (1) 时间复杂度
        a. 最好情况：O(n + m) // m 是元素值的上界 所以在基数排序中m = r 因为每次只比较 r 进制下的每一位 那个数肯定是不大于 r 即上界 m = r
        b. 平均情况：O(n + m)
        c. 最坏情况：O(n + m)
    (2) 空间复杂度
        O(n + m)
    (3) 稳定

2. 基数排序
    (1) 时间复杂度
        a. 最好情况：O(d(n + r)) 
        b. 平均情况：O(d(n + r))
        c. 最坏情况：O(d(n + r))
    (2) 空间复杂度
        O(n + r)
    (3) 稳定  

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 1000010;

int n ;
int q[N] , w[N] , s[N]; //桶排序辅助数组w[N]

void bucket_sort() // 桶排序 (计数排序) ：数据过大会越界
{
    for (int i = 0 ; i < n ; i ++) s[q[i]] ++ ; //桶排序
    for (int i = 1 ; i < N ; i ++) s[i] += s[i - 1]; //桶的前缀和
    for (int i = n - 1 ; i >= 0 ; i --) w[-- s[q[i]]] = q[i] ; //s[q[i]]表示<= q[i]的元素个数
    for (int i = 0 ; i < n ; i ++) q[i] = w[i] ; //copy回原数组
}

void radix_sort(int d, int r) //基数排序 //d:元素转换为r进制后的位数
{
    int radix = 1 ; //初始1 取个位
    for (int j = 0 ; j < d ; j ++) // 迭代d次桶排序
    {
     for (int i = 0 ; i < r ; i ++) s[i] = 0 ; //每次都要把桶先清空
     for (int i = 0 ; i < n ; i ++) s[q[i] / radix % r] ++ ; //桶排序，一共r个桶
     for (int i = 1 ; i < r ; i ++) s[i] += s[i - 1]; // 前缀和
     for (int i = n - 1 ; i >= 0 ; i --) w[-- s[q[i] / radix % r]] = q[i]; //从前往后对原数组排序
     for (int i = 0 ; i < n ; i ++) q[i] = w[i]; // copy回原数组
     radix *= r ; //radix *= r 使下次取到高一位的数
    }
}

int main()
{
    cin >> n ;

    for (int i = 0 ; i < n ; i ++) cin >> q[i];

    //bucket_sort();
    radix_sort(10 , 10);

    for (int i = 0 ; i < n ; i ++) cout << q[i] << " ";

    return 0 ;
}