排序方法(希尔、快速、堆)

这三种属于比较重要的排序方法，直接上代码

//希尔排序
void shell_sort(int arr[], size_t n)
{
    int step;
    int i, j;
    for(step = n / 2; step > 0; step /= 2)    //每次步数为当前的一半
    {
        for(i = step; i < n; i++)
        {
            int key = arr[i];    //一定要先记录当前i位置的值
            for(j = i - step; j >= 0 && key < arr[j]; j -= step)    //j每次减step
                arr[j + step] = arr[j];
            if(j + step != i)    //有过交换才会把key的值赋过去
                arr[j + step] = key;

        }
    }
}

//快速排序
void quick_sort(int arr[], size_t n)
{
    if(n <= 1)
        return;
    int left = 0, right = n - 1;
    int key = arr[0];    //取arr[0]为标识
    while(left < right)
    {
        //先从右往左找    找到第一个比key小的值放在left的位置
        while(left < right && key <= arr[right])//要带=号 不然会交换相同的值 进入死循环
            right--;
        arr[left] = arr[right];
        //然后再从左往右找    找到第一个比key大俄值放在right的位置
        while(lefty < right && arr[left] <= right)
            left++;
        arr[right] = arr[left];
    }
    //出循环后left == right
    arr[left] = key;
    //分别对key左边与右边的区间重复上面的操作
    if(1 < left)
        quick_sort(arr, left);    //[0, left)
    if(left + 1 < n)
        quick_sort(arr + left + 1, n - 1 - left);    //[left+1, n)
}

//构建大根堆
void reheap(int arr[], size_t pos, size_t n)
{
    int key = arr[pos];
    int child = pos * 2 + 1;    //获取左孩子的下标
    while(child < n)
    {
        if(child + 1 < n && arr[child] < arr[child + 1])
            child++;    //右孩子存在且比左孩子大;
        if(key < arr[child])
        {
            arr[pos] = arr[child];
            pos = child;
            child = pos * 2 + 1;
        }
        else
            break;
    }
    arr[pos] = key;
}

//堆排序
void heap_sort(int arr[], size_t n)
{
    int i;
    for(i = 2 / n - 1; i >= 0; i--)    //最后一个分支结点
    {
        reheap(arr, i, n);
    }
    for(i = n - 1; i >= 0; i--)
    {
        int tmp = arr[0];
        arr[0] = arr[i];
        arr[i] = tmp;
        reheap(arr, 0, i);    //每次把最大值放到末尾    对前面的数重新调整大根堆
    }
}