数据结构入门：插入排序与希尔排序详解

排序的概念及其应用

1.1 排序的概念

排序是指将一串记录按照特定规则递增或递减排列的操作。

1.2 排序的应用

生活中排序思想无处不在。例如电商购物时按好评数排序筛选商品，或大学按教学资源进行排名等。

插入排序

2.1 基本思想

在一个有序数组中，按照规则插入待排序的数字。

算法思路：从单趟排序讲起，选择待插入数字与已排序数组末端的数进行比较。若该值比待插入数字大，则将元素往后挪动一位，继续向前比较。若发现该值比待插入数字小，说明该值的后面一个位置就是待插入数字应该插入的位置，结束循环。

完整的插入排序是在循环地跑单趟排序，初始条件为从待插入数组的第二个元素下标开始。每当单趟排序跑完之后，设置循环条件的值（一开始比较数组末端的位置）。因为已经排好部分数组，每当来一个新数字就得在排好数组中插入，重复上述过程。

2.2 插入排序的代码实现

void InsertSort(int* a, int n){
    for(int i = 1; i < n; i++){
        int end = i - 1;
        int tmp = a[i];
        while(end >= 0){
            if(tmp < a[end]){
                a[end + 1] = a[end];
                end--;
            }else{
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

2.3 插入排序算法总结

• 元素集合越接近有序，直接插入排序算法的时间效率就越高。
• 时间复杂度：O(N^2)
• 空间复杂度：O(1)
• 稳定性：稳定

希尔排序

3.1 基本思想

先选定一个整数 gap，把待排序的数据分成个别组。分组的标准就是所有距离为 gap 的数据分在同一组，并对每一组内的记录进行排序。然后，缩小 gap 的值，重复上述分组和排序的工作。当 gap = 1 时，就相当于直接插入排序了。

3.2 希尔排序的代码实现

void ShellSort(int* a, int n){
    int gap = n;
    while(gap > 1){
        //gap /= 2;
        gap = gap / 3 + 1;
        for(int j = 0; j < gap; j++){
            for(int i = j; i < n; i += gap){
                int end = i - 1;
                int tmp = a[i];
                while(end >= 0){
                    if(tmp < a[end]){
                        a[end + 1] = a[end];
                        end--;
                    }else{
                        break;
                    }
                }
                a[end + 1] = tmp;
            }
        }
    }
}

3.3 希尔排序的特征总结

• 希尔排序是对直接插入排序的优化。
• 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。整体而言，可以达到优化的效果。
• 希尔排序的时间复杂度不好计算，因为 gap 的取值方法很多。一般认为时间复杂度为 O(N*logN)，严谨计算则为 O(N^1.3)。