常用的内部排序算法

#include <bits/stdc++.h>
using namespace std;


//选择排序
void xuan_sort(int *a, int n)
{
    int *t = (int *)malloc(sizeof(int)*(n+1));
    memcpy(t, a, sizeof(int)*(n+1));
    for(int i = 1; i < n; i++)
    {
        for(int j = i+1; j <= n; j++)
        {
            if(t[i] > t[j])
                swap(t[i], t[j]);
        }
    }
    for(int i = 1; i <= n; i++)
        printf("%d ", t[i]);
    free(t);
}


//插入排序
void cha_sort(int *a, int n)
{
    int *t = (int *)malloc(sizeof(int)*(n+1));
    memcpy(t, a, sizeof(int)*(n+1));
    int j;
    for(int i = 2; i <= n; i++)
    {
        int k = t[i];
        for(j = i; j > 1 && k < t[j-1]; j--)
        {
            t[j] = t[j-1];
        }
        t[j] = k;
    }
    for(int i = 1; i <= n; i++)
        printf("%d ", t[i]);
    free(t);
}


//冒泡排序
void mao_sort(int *a, int n)
{
    int *t = (int *)malloc(sizeof(int)*(n+1));
    memcpy(t, a, sizeof(int)*(n+1));
    for(int i = n; i >= 2; i--)
        for(int j = 1; j < i; j++)
        {
            if(t[j]>t[j+1])
                swap(t[j], t[j+1]);
        }
    for(int i = 1; i <= n; i++)
        printf("%d ", t[i]);
    free(t);
}


//希尔排序
void xi_sort(int *a, int n)
{
    int *t = (int *)malloc(sizeof(int)*(n+1));
    memcpy(t, a, sizeof(int)*(n+1));
    int j;
    for(int k = n/2; k>0; k/=2)
    {
        for(int i = k; i <= n; i++)
        {
            int x = t[i];
            for(j = i; j>k && t[j-k]>x; j-=k)
                t[j] = t[j-k];
            t[j] = x;
        }
    }
    for(int i = 1; i <= n; i++)
        printf("%d ", t[i]);
    free(t);
}


//快速排序
void q_sort(int *t, int l, int r)
{
    if(l>=r) return;
    int mid = (l+r)>>1;
    if(t[l]>t[r]) swap(t[l], t[r]);
    if(t[mid]>t[r]) swap(t[mid], t[r]);
    if(t[l]>t[mid]) swap(t[l], t[mid]);
    swap(t[mid], t[l]);
    int i = l, j = r;
    while(i<j)
    {
        while(i<j && t[j]>=t[l]) j--;
        while(i<j && t[i]<=t[l]) i++;
        if(i < j) swap(t[i], t[j]);
        else break;
    }
    swap(t[l], t[i]);
    q_sort(t, l, i-1);
    q_sort(t, i+1, r);
}
void quick_sort(int *a, int n)
{
    int *t = (int *)malloc(sizeof(int)*(n+1));
    memcpy(t, a, sizeof(int)*(n+1));
    q_sort(t, 1, n);
    for(int i = 1; i <= n; i++)
        printf("%d ", t[i]);
    free(t);
}


//堆排序
void pushdown(int *t, int rf, int n)
{
    int base = t[rf];
    while(rf*2<=n)
    {
        int child = rf*2;
        if(child+1<=n&&t[child+1]>t[child]) child++;
        if(base>t[child]) break;
        t[rf] = t[child];
        rf = child;
    }
    t[rf] = base;
}
void dui_sort(int *a, int n)
{
    int *t = (int *)malloc(sizeof(int)*(n+1));
    memcpy(t, a, sizeof(int)*(n+1));
    for(int i = n/2; i>=1; i--)
    {
        pushdown(t, i, n);
    }
    for(int i = n; i>=2; i--)
    {
        swap(t[1], t[i]);
        pushdown(t, 1, i-1);
    }
    for(int i = 1; i <= n; i++)
        printf("%d ", t[i]);
    free(t);
}


//归并排序
void Merge(int *t, int *p, int l, int m, int r)
{
    int i = l, j = m, cas = l;
    while(i<m && j<=r)
    {
        if(t[i]>t[j]) p[cas++] = t[j++];
        else p[cas++] = t[i++];
    }
    while(i<m) p[cas++] = t[i++];
    while(j<=r) p[cas++] = t[j++];
    for(i = l; i <= r; i++) t[i] = p[i];
}
void gui(int *t, int *p, int l, int r)
{
    int mid = (l+r)>>1;
    if(l < r)
    {
        gui(t, p, l, mid);
        gui(t, p, mid+1, r);
        Merge(t, p, l, mid+1, r);
    }
}
void gui_sort(int *a, int n)
{
    int *t = (int *)malloc(sizeof(int)*(n+1));
    memcpy(t, a, sizeof(int)*(n+1));
    int *p = (int *)malloc(sizeof(int)*(n+1));
    gui(t, p, 1, n);
    for(int i = 1; i <= n; i++)
        printf("%d ", t[i]);
    free(t);
}


int main()
{
    int n, a[100];
    while(1)
    {
        printf("

请输入元素个数：");
        cin>>n;
        printf("请输入%d个元素
", n);
        for(int i = 1; i <= n; i++)
            scanf("%d", a+i);
        printf("
简单选择排序：");
        xuan_sort(a, n);
        printf("
直接插入排序：");
        cha_sort(a, n);
        printf("
冒泡排序：    ");
        mao_sort(a, n);
        printf("
希尔排序：    ");
        xi_sort(a, n);
        printf("
快速排序：    ");
        quick_sort(a, n);
        printf("
堆排序：      ");
        dui_sort(a, n);
        printf("
归并排序：    ");
        gui_sort(a, n);
    }
    return 0;
}

测试图：