本文将介绍七大排序算法的三种，其中另外四种见博客冒泡排序、选择排序、插入排序、堆排序，其中本文用到的两个数的交换函数也在该博客中有介绍。

1.希尔排序

（1）实现思想：

（2）时间复杂度：取决于步长序列，若使用希尔序列：N/2,N/4,N/8.......1，时间复杂度为O（n^2）；若选择一个最优序列，可达到O（n^1.3）

（3）空间复杂度：O（1）

（4）稳定性：不稳定排序

（5）实现代码：

//5.希尔排序：分组式的插入排序
//定义一个初始步长(下标间隔)gap，按步长将待排序数列分组
//将分好的组，每组插入排序,然后gap--
//重复以上步骤，直至gap=0
//N/2,N/4,N/8...希尔序列，时间复杂度为O(N)
void ShellSort(int arr[], size_t size)
{
    if(size <= 1)
        return;
    int64_t gap = size/2;//使用希尔序列
    //1.第一重循环，生成步长序列
    for(; gap>0; gap /= 2)
    {
        //2.第二重循环，进入插入排序
        //此循环的执行顺序，相当于先处理第一组的第一个
        //再处理第二组的第一个....
        //再第二组的第一个....
        int64_t bound = gap;//此处相当于插入排序中的bound=1
        for(; bound<size;++bound)
        {
            int bound_value = arr[bound];//待插入元素
            //3.第三重循环，线性表的搬运(一边找一边搬运)
            int64_t cur = bound;
            for(; cur>=gap;cur -= gap)//cur-=gap是为了找到同组元素的上一个元素
            {
                if(arr[cur-gap] > bound_value)//进行搬运
                    arr[cur] = arr[cur-gap];
                else//找到了合适的插入位置
                    break;                                                                                                                            
            }
            arr[cur] = bound_value;
        }
    }
}

2. 归并排序

（1）实现思想：

（2）时间复杂度：O（n^logn）

（3）空间复杂度：O（n）

（4）稳定性：稳定排序

（5）实现代码：

1）递归实现：

//6.归并排序
//(1)递归版本
void _MergeArr(int arr[], int64_t beg, int64_t mid, int64_t end, int* tmp)
{//归并两个子区间，传入的两个子区间本身有序
    int64_t cur1 = beg;
    int64_t cur2 = mid;
    int64_t tmp_index = beg;
    while(cur1<mid && cur2<end)//有一个子区间比较结束了，循环结束，可将另一个子区间剩下的元素一次性全放进去，因为每个子区间本身有序
    {//将数据按从小到大存放到tmp空间中
        if(arr[cur1] < arr[cur2])
            tmp[tmp_index++] = arr[cur1++];
        else
            tmp[tmp_index++] = arr[cur2++];
    }
    while(cur1 < mid)
        tmp[tmp_index++] = arr[cur1++];
    while(cur2 < end)
        tmp[tmp_index++] = arr[cur2++];
    //把tmp中的内容拷贝到数组，进行归并处理时的区间是arr[beg,end)
    memcpy(arr+beg, tmp+beg, sizeof(int)*(end-beg));
    return;
}


void _MergeSort(int arr[], int64_t beg, int64_t end, int* tmp)
{//[beg,end)为当前要处理的子区间
    //size_t类型作减法很危险，所以这里用int64_t
    if(end - beg <= 1)//最多一个元素或非法区间
        return;                                                                                                                                       
    int64_t mid = beg + (end-beg)/2;
    //此时有两个区间[beg,mid)、[mid,end)
    _MergeSort(arr, beg, mid, tmp);
    _MergeSort(arr, mid, end, tmp);
    _MergeArr(arr, beg, mid, end, tmp);
}

void MergeSort(int arr[], size_t size)
{
    if(size <= 1)
        return;
    //创建临时空间，用于辅助归并元素
    int* tmp = (int*)malloc(sizeof(int)*size);
    _MergeSort(arr, 0, size, tmp);
    free(tmp);
}

2）非递归实现：

//(2)非递归版本
void MergeSortByLoop(int arr[], size_t size)
{
    if(size <= 1)
        return;
    int* tmp = (int*)malloc(sizeof(int)*size);
    //定义一个初始步长gap=1,相当于每次合并两个长度为gap的有效区间
    size_t gap = 1;
    for(; gap<size; gap*=2)
    {
        //在当前gap下，我们利用i辅助完成所有长度为gap的区间的合并
        size_t i = 0;
        for(; i<size; i+=2*gap)
        {//[beg,mid)、[mid,end)
            size_t beg = i;
            size_t mid = i+gap;
            if(mid > size)//防止mid超过数组最大范围
                mid = size;
            size_t end = i+2*gap;
            if(end > size)//防止end超过数组最大范围
                end = size;
            _MergeArr(arr, beg, mid, end, tmp);
        }
    }
    free(tmp);                                                                                                                                        
}

3. 快速排序

（1）实现思想：

（2）时间复杂度：平均情况O（n^logn），最坏时为O（n^2）

（3）空间复杂度：O（1）

（5）实现代码：

1）递归实现：

//7.快速排序
//(1)递归版本

int64_t Partion(int arr[], int64_t beg, int64_t end)//1.交换法
{
    if(end-beg <= 1)
        return beg;
    int64_t left = beg;
    int64_t right = end-1;//前闭后开区间
    int key = arr[right];//最后一个元素作为基准值
    while(left < right)
    {
        //从左到右找一个大于key的元素
        while(left < right && arr[left] <= key)
            ++left;
        //从右到左找一个小于Key的元素
        while(left < right && arr[right] >= key)
            --right;
        if(left < right)
            Swap(&arr[left], &arr[right]);
    }
    Swap(&arr[left], &arr[end-1]);
    return left;
}

int64_t Partion1(int arr[], int64_t beg, int64_t end)//1.挖坑法
{
    if(end-beg <= 1)
        return beg;
    int64_t left = beg;
    int64_t right = end-1;//前闭后开区间                                                                                                              
    int key = arr[right];//最后一个元素作为基准值
    while(left < right)
    {
        while(left < right && arr[left] <= key)
            ++left;
        //此时left指向一个大于基准值Key的元素
        //可以把该值填到right所指的坑，赋值完成后，left所指又变成一个坑
        if(left < right)
            arr[right--] = arr[left];
        while(left < right && arr[right] >= key)
            --right;
        if(left < right)
            arr[left++] = arr[right];
    }
    //left与right重合，整个区间整理完毕，只剩下left=right位置为坑，将基准值填入即可
    arr[left] = key;
    return left;
}

void _QuickSort(int arr[], int64_t beg,int64_t end)
{
    if(end-beg <= 1)//当前区间内最多只有一个元素
        return;
    //[beg,mid)左半部分区间，[mid+1, end)右半部分区间，左半部分元素一定小于等于右半部分区间元素
    //int64_t mid = Partion(arr, beg, end);
    int64_t mid = Partion1(arr, beg, end);
    _QuickSort(arr, beg, mid);
    _QuickSort(arr, mid+1, end);
    return;
}

void QuickSort(int arr[], size_t size)
{
    _QuickSort(arr, 0, size);                                                                                                                         
    return;
}

2）非递归实现：

//(2)非递归版本实现
void QuickSortByLoop(int arr[], size_t size)
{
    if(size <= 1)
        return;
    SeqStack stack;
    SeqStackInit(&stack);
    int64_t beg = 0;
    int64_t end = size;
    SeqStackPush(&stack, beg);
    SeqStackPush(&stack, end);

    while(1)
    {
        int ret = SeqStackGetTop(&stack, &end);
        if(ret == 0)//栈空，说明快排结束
            break;
        SeqStackPop(&stack);
        SeqStackGetTop(&stack, &beg);
        //[beg,end)相当于即将要进行快排整理的区间
        if(end-beg <= 1)
            continue;
        //int64_t mid = Partion(arr, beg, end);
        int64_t mid = Partion1(arr, beg, end);
        
        //[beg, mid),[mid+1, end)
        SeqStackPush(&stack, beg);
        SeqStackPush(&stack, mid);
        SeqStackPush(&stack, mid+1);                                                                                                                  
        SeqStackPush(&stack, end);
    }
}

快排的改进方法：

（1）可以调整选取基准值的方法：头、尾、中间，三个元素取值为中间大的数为基准值；

（2）当递归到一定深度时，就不再递归，而是将排序算法改为堆排序

（3）当递归到一定程度时，子区间的元素较少时，把排序算法改为插入排序

下面介绍几种不常用的排序算法，这里只做简单介绍，并无实现。

4. 计数排序

（1）实现思想

（2）只适用于正整数

（3）时间复杂度：O（n）

（4）空间复杂度：O（n）

5. 基数排序

（1）实现思想：

（2）适用于解决数据范围大

6. 睡眠排序

实现思想：

        借助线程，每读一个待排序元素，都创建一个线程，并让它sleep元素值得秒数，按照醒来时间，我们即可排序。

7. 猴子排序

（1）实现思想：

        一直排（没有方法的排），直至整个有序，排序结束。

（2）时间复杂度：无穷大