【精华】排序算法汇总——希尔排序与堆排序

日常说明：有错误欢迎大家指正,希望对你们有用。
更多算法请关注我的算法专栏https://blog.csdn.net/column/details/20417.html

三、希尔排序（shell sort）
算法思想：希尔排序又称为缩小增量排序，也属于插入类排序方法。具体的操作是：先将整个待排记录序列分割成若干子序列，然后对子序列分别进行插入排序，最后再进行一次直接插入排序。复杂度为O(n^(3/2))。
如：49 38 65 97 76 13 27 47 55 04，假定第一趟增量为5，第二趟增量为3，第三趟增量为1
第一趟排序：13 27 47 55 04 49 38 65 97 76
第二趟：13 04 47 38 27 49 65 97 76
第三趟：04 13 27 38 47 49 65 76 97
核心代码：

shell_insert(List&list,int increm)  //increm为增量，增量放在数组中
{
    for (int i = increm+1; i <=list.length; ++i)
    {
        if (list.elem[i] < list.elem[i - increm])
        {
            list.elem[0] = list.elem[i];//将要插入的值list.elem[i]暂存在第一个位置。
            int j;
            for (j = i - increm; j >0&&(list.elem[0]<list.elem[j]); j-=increm)
            {
                list.elem[j + increm] = list.elem[j];
            }//比较增量后子序列的大小，将大于list.elem[0]的数往后移动，list.elem[0]插入。
            list.elem[j + increm] = list.elem[0];
        }   
    }
}

shell_sort(List&list)
{
    int arr[3] = { 5,3,1 };//增量数组
    for (int i = 0; i < 3; i++)
    {
        list.shell_insert(list, arr[i]);
    }
};

堆排序
算法思想：堆排序可以建大顶堆或者小顶堆，就是最大的数在顶端或者最小的数在顶端。我们把数据序列逻辑化为完全二叉树，对一棵子树比较根节点和左右孩子的大小，将最大的数放在根节点。依次对每棵子树都进行此操作，这是建堆后不断调整为大顶堆的过程。建好堆后需要进一步调整即排序，使得根节点>左孩子>右孩子。简单说，通过筛选将完全二叉树中最大的数放在根节点，变成大顶堆。然后将根节点的数和最后一个数交换位置，除了最后一个数其他的数再调整为大顶堆，再交换到最后，几趟下来就排好序了。复杂度为O(nlogn)
核心代码：

HeapAdjust(int arr[], int root, int length)
{
    int lchild = root * 2 + 1;
    if (lchild!=NULL&&lchild < length)  
    {
        int temp = lchild;
        int rchild = lchild + 1;  
        if (rchild < length) 
        {
            if (arr[rchild] > arr[temp])//找出左右子结点中的最大值  
            {
                temp = rchild;
            }
        }
        if (arr[root] < arr[temp])
        {
            Swap(arr[root], arr[temp]);
            HeapAdjust(arr, temp, length);//从此次最大子节点的那个位置开始递归建堆  
        }
    }
}

Heap_sort(int arr[], int len)
{
    for (int i = len / 2; i >= 0; --i)//从最后一个非叶子节点的父结点开始建堆  
    {
        HeapAdjust(arr, i, len);
    }

    for (int j = len - 1; j > 0; --j) 
    {
        Swap(arr[0], arr[j]);//交换首尾元素,将最大值交换到数组的最后位置保存  
        HeapAdjust(arr, 0, j);//去除最后位置的元素重新建堆，此处j表示数组的长度，最后一个位置下标变为len-2  
    }

}