【数据结构】排序的基本概念、插入排序、希尔排序

1. 排序的基本概念

1. 基本概念

排序（Sort），就是重新排列表中的元素，使表中的元素满足按关键字有序的过程。

输入：n个记录R1,R2,...,Rn，对应表中的关键字为k1,k2,...,kn。

输出：输入序列的一个重排R1',R2',...,Rn'，使得k1'<=k2'<=...<=kn'（也可递减）。

2. 排序算法的评价指标

时间复杂度（参考之前的文章）。

【数据结构】时间复杂度

空间复杂度（参考之前的文章）。

【数据结构】算法的空间复杂度

算法的稳定性。若待排序表中有两个元素Ri和Rj，其对应的关键字相同即keyi=keyj，且在排序前Ri在Rj的前面，若使用某一排序算法排序后，Ri任然在Rj的前面，则称这个排序算法是稳定的，否则称排序算法是不稳定的。

3. 排序算法的分类

内部排序：数据都在内存中。

外部排序：数据太多，无法全部放入内存。

说明：内部排序关注如何使算法时间和空间复杂度更低。外部算法除了时间和空间复杂度外，还要关注如何使读/写磁盘次数更少。

2. 插入排序

1. 算法思想

每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中，直到全部记录插入完成。

2. 算法实现

// 直接插入排序
void InsertSort(int A[],int n){
    int i,j,temp;
    for(i=1;i<n;i++){  // 将各元素插入已排好序的序列中
        if(A[i]<A[i-1]){  // 若A[i]关键字小于前驱
            temp=A[i];  // 用temp暂存A[i]
            for(j=i-1;j>=0 && A[j]>temp;--j){  // 检查所有前面已排好序的元素
                A[j+1]=A[j];  // 所有大于temp的元素都向后移位
            }
            A[j+1]=temp;  // 复制到插入位置
        }
    }
}

// 直接插入排序（带哨兵）
void InsertSort(int A[],int n){
    int i,j;
    for(i=2;i<=n;i++){  // 依次将A[2]~A[n]插入到前面已排序序列
        if(A[i]<A[i-1]){  // 若A[i]关键码小于其前驱，将A[i]插入有序表
            A[0]=A[i];  // 复制为哨兵，A[0]不存放元素
            for(j=i-1;A[0]<A[j];--j){  // 从后往前查找待插入位置
                A[j+1]=A[j];  // 向后挪位
            }
            A[j+1]=A[0];  // 复制到插入位置
        }
    }
}

3. 算法效率分析

空间复杂度：O(1)。

最好时间复杂度（全部有序）：O(n)。

最坏时间复杂度（全部逆序）：O(n^2)。

平均时间复杂度：O(n^2)。

时间复杂度：主要来自于对比关键字、移动元素。若有n个元素，则需要n-1趟处理。

算法稳定性：稳定。

4. 优化思路

思路：先用折半查找找到应该插入的位置，再移动元素。

当low>high时折半查找停止，应将[low, i-1]内元素全部右移，并将A[0]复制到low所指的位置。当A[mid]=A[0]时，为了保证算法的“稳定性”，应继续在mid所指位置右边寻找插入位置，直到low>high。

代码实现：

// 折半插入排序
void InsertSort(int A[],int n){
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){  //  依次将A[2]~A[n]插入前面的已排序序列
        A[0]=A[i];  // 将A[i]暂存到A[0]
        low=1;high=i-1;  // 设置折半查找的范围
        while(low<=high){  // 折半查找（默认递增有序）
            mid=(low+high)/2;  // 取中间点
            if(A[mid]>A[0]){
                high=mid-1;  // 查找左半子表
            }else{
                low=mid+1;  // 查找右半子表
            }
        }
        for(j=i-1;j>=hgih+1;--j){
            A[j+1]=A[j];  // 统一后移元素，空出插入位置
        }
        A[high+1]=A[0];  // 插入操作
    }
}

比起“直接插入排序”，比较关键字的次数减少了，但是移动元素的次数没变，整体来看时间复杂度依然是O(n^2)。

5. 对链表插入排序

移动元素的次数变少了，但是关键字对比的次数依然是O(n^2)数量级，整体来看时间复杂度依然是O(n^2)。

3. 希尔排序

1. 算法思想

希尔排序：先将待排序表分割成若干形如L(i,i+d,i+2d,..,i+kd)的“特殊”子表，对各个子表分别进行插入排序。缩小增量d，重复上述过程，直到d=1为止。

说明：希尔排序先追求表中元素部分有序，再逐渐逼近全局有序。

说明：当d=1时，希尔排序转化为直接插入排序。

希尔本人建议：每次将增量缩小一半。

2. 算法实现

// 希尔排序
void ShellSort(int A[],int n){
    int d,i,j;
    // A[0]只是暂存单元，不是哨兵，当j<=0时，插入位置已到
    for(d=n/2;d>=1;d=d/2){  // 步长变化
        for(i=d+1;i<=n;++i){
            if(A[i]<A[i-d]){  // 需将A[i]插入有序增量子表
                A[0]=A[i];  // 暂存在A[0]
                for(j=i-d;j>0 && A[0]<A[j];j-=d){
                    A[j+d]=A[j];  // 记录后移，查找插入的位置
                }
                A[j+d]=A[0];  // 插入
            }
        }
    }
}