c++代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
//--------------------------------------------------------------------------
//直接插入排序
//              时复            空复            稳定性
//  最好情况    O(n)            0(1)            稳
//  平均情况    O(n ^ 2)            
//  最坏情况    O(n ^ 2)
void insert_sort()
{
    for(int i = 1; i < n; i ++)
    {
        int j = i;
        int t = q[j];
        while(j > 0 && q[j - 1] > q[j])
        {
            q[j] = q[j - 1];
            j--;
        }
        q[j] = t;
    }
}
//--------------------------------------------------------------------------------------
//二分插入排序
//              时复            空复            稳定性
//  最好情况    O(n)            0(1)            稳
//  平均情况    O(n ^ 2)            
//  最坏情况    O(n ^ 2)
//只优化了比较次数
int bi_search(int l, int r, int key)
{
    while(l < r)
    {
        int mid = (l + r) / 2;
        if(q[mid] < key) l = mid + 1;
        else r = mid;
    }
    return l;
}
void bi_insert_sort()
{
   for(int i = 1; i < n; i ++)
   {
       if(q[i - 1] <= q[i]) continue;
       int j = i;
       int t = q[i];
       int pos = bi_search(0, i - 1, t);
       while(j > 0 && j > pos)
       {
           q[j] = q[j - 1];
           j--;
       }
       q[j] = t;
   }
}
//----------------------------------------------------------------
//冒泡排序
//              时复            空复            稳定性
//  最好情况    O(n)            0(1)            稳
//  平均情况    O(n ^ 2)            
//  最坏情况    O(n ^ 2)
void bubble_sort()
{
    for(int i = 0; i < n - 1; i ++)
    {
        bool has_swap = false;
        for(int j = n - 1; j > i; j--)
        {
            if(j > 0 && q[j] < q[j - 1])
            {
                swap(q[j], q[j - 1]);
                has_swap = true;
            }
        }
        if(has_swap == false) break;
    }
}
//-------------------------------------------------------------
//简单选择排序
//              时复            空复            稳定性
//  最好情况    O(n ^ 2)        0(1)            不稳！！
//  平均情况    O(n ^ 2)            
//  最坏情况    O(n ^ 2)
//不管什么情况都得走完全部流程
void select_sort()
{
    for(int i = 0; i < n - 1; i ++)
    {
        int min = i;
        for(int j = i + 1; j < n; j ++)
        {
            if(q[j] < q[min]) min = j;
        }
        swap(q[i], q[min]);
    }
}
//----------------------------------------------------------------
//希尔排序
//              时复            空复            稳定性
//  平均情况    O(n ^ 2)        O(1)            不稳            
void shell_sort()
{
//d为公差 逐渐减小至1，组内进行直接插入排序
//因直接插入排序在组内部分有序的情况下效率变高
    for(int d = n / 2; d > 0; d /= 2)
    {
        for(int start = 0; start < d; start ++)
        {
            for(int i = start + d; i < n; i += d)
            {
                int t = q[i];
                int j = i;
                while(j > 0 && q[j - 1] > t)
                {
                    q[j] = q[j - 1];
                    j -= d;
                }
                q[j] = t;
            }
        }
    }
}
//-------------------------------------------------------------
//快速排序
//              时复            空复            稳定性
//  最好情况    O(nlogn)        0(nlogn)        不稳
//  平均情况    O(nlogn)            
//  最坏情况    O(n ^ 2)
void quick_sort(int l, int r)
{
    if(l >= r)  return ;
    int x = q[(l + r) / 2], i = l - 1, j = r + 1;
    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, i - 1);
    quick_sort(j + 1, r);
}
//-------------------------------------------------------------
//堆排序
//              时复            空复            稳定性
//  最好情况    O(nlogn)        0(1)        不稳
//  平均情况    O(nlogn)            
//  最坏情况    O(nlogn)
//  建堆        O(n)
int m, cnt;
int h[N];

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

//建堆
//    for(int i = n / 2; i > 0; i--)
//    {
//        down(i);
//    }

//-------------------------------------------------------------
//二路归并排序
//              时复            空复            稳定性
//  最好情况    O(nlogn)        0(n)            稳
//  平均情况    O(nlogn)            
//  最坏情况    O(nlogn)
//不管什么情况都会走完所有流程
//辅助数组temp[N];
void merge_sort(int l, int r)
{
    if(l >= r) return ;
    int mid = (l + r) / 2;

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

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

    for(int i = l; i <= r; i++) q[i] = temp[i];
}
int main()
{
    cin >> n;
    //输入
    for(int i = 0; i < n; i++) scanf("%d", &q[i]);

    select_sort();
    //输出
    for(int j = 0; j < n; j ++) cout << q[j] << ' ';

    return 0;

}