1.直接插入排序

//todo:1.直接插入排序
void insert_sort(int arr[],size_t n)
{
    int i,j;
    for(i=1;i<n;i++)
    {
        int key = arr[i];
        for(j=i-1;j>=0 && arr[j]>key;j--)
        {
            arr[j+1]=arr[j];
        }
        arr[j+1]=key;
        show(arr,n);
    }
}

2.折半插入排序

//todo:2.折半插入排序
void bin_insert_sort(int arr[],size_t n)
{
    int i, j;
    for (i = 1; i < n; i++)
    {
        int key = arr[i];
        int left = 0;
        int right = i - 1;
        while (left <= right)
        {
            int mid = (left + right) / 2;
            if (key < arr[mid])
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        for (j = i - 1; j >= left; j--)
        {
            arr[j + 1] = arr[j];
        }
        arr[left] = key;
        show(arr,n);
    }
}

3.希尔排序

//todo:3.希尔排序
void shell_sort(int arr[],size_t n)
{
    size_t step;
    //分组
    for(step = n/2;step > 0; step = step/2)
    {
        size_t i;
        for(i=step;i<n;i++)
        {
            int j;
            int key = arr[i];
            for(j=i-step;j>=0 && arr[j]>key;j=j-step)
            {
                arr[j+step] = arr[j];
            }
            arr[j+step] = key;
        }
        show(arr,n);
    }
}

4.冒泡排序

void bubble(int arr[],int n){
    int i,j;
    for(i=0;i<n-1;i++)
    {
        for(j=0;j<n-i-1;j++)
        {
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
        }
        show(arr,n);
    }
}

5.快速排序

void quick(int arr[],int left,int right,size_t n)
{

    if (left >= right)
        return;
    int i = left, j = right;
    int key = arr[i];
    while (i < j)
    {
        while (i < j && arr[j] >= key)
        {
            --j;
        }
        arr[i] = arr[j];
        while (i < j && arr[i] <= key)
        {
            ++i;
        }
        arr[j] = arr[i];
    }
    arr[i] = key;
    show(arr,n);
    if (i - 1 - left + 1 > 1)
        quick(arr, left, i - 1,n);
    if (right - (i + 1) + 1 > 1)
        quick(arr, i + 1, right,n);
}

6.简单选择排序

void choice_sort(int arr[],size_t n)
{
    size_t i,j;
    for(i=0;i<n;i++)
    {
        size_t m=0 ;
        for(j=1;j<n-i;j++)
        {
            if(arr[j]>arr[m])
            {
                m = j;
            }
        }
        if(n-i-1 != m){
            swap(arr[n-1-i],arr[m]);
        }
        show(arr,n);
    }
}

7.堆排序

void max_heapify(int arr[], int start, int end)
{
    //建立父节点指标和子节点指标
    int dad = start;
    int son = dad * 2 + 1;
    while (son <= end)  //若子节点指标在范围内才做比较
    {
        if (son + 1 <= end && arr[son] < arr[son + 1])
            //先比较两个子节点大小，选择最大的
            son++;
        if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数
            return;
        else  //否则交换父子内容再继续子节点和孙节点比较
        {
            swap(arr[dad], arr[son]);
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void heap_sort(int arr[], int len)
{
    int i;
    //初始化，i从最後一个父节点开始调整
    for (i = len / 2 - 1; i >= 0; i--)
        max_heapify(arr, i, len - 1);
    //先将第一个元素和已排好元素前一位做交换，再重新调整，直到排序完毕
    for (i = len - 1; i > 0; i--)
    {
        swap(arr[0], arr[i]);
        max_heapify(arr, 0, i - 1);
        show(arr,len);
    }
}

8.归并排序

//todo:8.归并排序
void mergeArr(int arr[],size_t n){
    if(n<=1){
        return ;
    }
    int mid = n/2;
    int len =mid;
    int *prr = (int *)malloc(sizeof(int)*len);
    size_t i;
    for(i=0;i<len;i++){
        prr[i] = arr[i];
    }
    size_t j,k;
    i=0;
    j=mid;
    k=0;
    while(i<len && j<n){
        if(prr[i]<arr[j]){
            arr[k++]=prr[i++];
        }else{
            arr[k++]=arr[j++];
        }
    }
    while(i<len){
        arr[k++]=prr[i++];
    }
    free(prr);
}

void merge_sort(int arr[],size_t n)
{
    if (n <= 1)
    {
        return;
    }

    int mid = n / 2;
    merge_sort(arr, mid);
    merge_sort(arr + mid, n - mid);
    mergeArr(arr, n);
    show(arr,n);
}

9.基数排序

void base_sort(int arr[],size_t n)
{
    queue<int> bucket[10];
    int max = arr[0];
    int i;
    for(i=0;i<n;i++)
    {
        if(max < arr[i])
        {
            max = arr[i];
        }
    }
    int div = 1;
    size_t j=0,k=0;
    do{
        for(i=0;i<n;i++)
        {
            int n = arr[i]/div%10;
            bucket[n].push(arr[i]);
        }
        k=0;
        for(i=0;i<10;i++)
        {
            while(!bucket[i].empty())
            {
                arr[k++] = bucket[i].front();
                bucket[i].pop();
            }
        }
        div = div*10;
        max = max/10;
        show(arr,n);
    }while(max!=0);
}