【算法】简单插入排序与希尔排序

朴灿烈づ我的快乐病毒、 2022-06-14 05:50 229阅读 0赞

## **简单插入排序** ##

简单插入排序的思想非常简单：就是将待排序列分为已经排好的和未排序的两个序列，初始时已排序序列包含第一个元素，未排序序列为其余的元素；之后每次从未排序序列中取一个元素插入已排序序列，直到未排序序列元素个数为零，排序就完成了。  
下面给出代码

void InsertionSort(int A[], int n)
    {
        /*A[]为待排数组，n为数组中元素个数*/
        int temp;
        for(int i = 1; i<n; i++){
       //从第二个元素，即未排序序列的第一个元素开始
            temp = A[i];
            for(int j = i; j>0; j--){
                /*从后向前进行比较插入*/
                if(temp < A[j-1]){
                    A[j] = A[j-1];
                    A[j-1] = temp;
                }
                else break;
            }
        }
    }

## **希尔排序** ##

对于简单插入排序我们很容易得出它的时间复杂度为O(n^2),所以效率并不高。希尔排序是对简单插入排序的改进，它的思想是：

1.  将待排序列以相同的间隔分为几组（比如分为n组，那么每组组内相邻元素的间隔为n-1），然后分别对各组数据进行简单插入排序，尽管简单插入排序复杂度为O(n^2)，但是分组后每组元素数量减少，所以整体速度是快于对整个待排序列进行简单插入排序的。
2.  之后我们不断减小所取的间隔（即增加分组数量），重复步骤1的操作，在这个过程中待排序列整体会逐渐变得有序。
3.  最后取间隔为1，即对整个待排序列进行一次简单插入排序，之后排序完成。注意到经过之前的几次分组排序，待排序列已经基本有序，所以此次排序的时间效率会得到很大的提升。
    
    下面给出代码

void ShellSort(int A[],int n,int Incre[],int m)
    {
        /*A[]为含n个元素的待排序列
          Incre[]为含m个增量的序列，递减有序，且最后一个元素为1*/
        int increment, temp;
        for(int i = 0; i < m; i++){
            increment = Incre[i];//从增量数组中依次选取增量，由此将待排序列分为与增量相同的组数
            for(int j = increment; j<n; j++){
       //对每一组元素分别进行插入排序
                temp = A[j];
                for(int k = j; k >= increment; k-=increment){ //注意k的取值范围应与j相同
                    if(temp < A[k-increment]){
                        A[k] = A[k-increment];
                        A[k-increment] = temp;
                    }
                    else break;
                }
            }
        }
    }