基础算法-插入排序

末蓝、 2022-07-27 15:58 137阅读 0赞

# 插入排序 #

使用插入排序的算法有直接**插入排序**和**希尔排序**。

## 直接插入排序 ##

### 基本原理 ###

条件：序列a1、a2、… an，分别取\{a1\}和\{a2, a3, … an\}为已排序列（从小到大的顺序）和待排序列。

第一步：取待排序列a2与已排序列\{a1\}中的a1比较：  
若a1 <= a2则a2添加到已排序列的末尾即已排序列为\{a1,a2\};  
若a1>a2则a2添加到已排序列的首位即已排序列为\{a2, a1\};  
那么未排序列为\{a3, a4,… an\}。

第二步：取待排序列\{a3, a4, … an\}中的a3，分别与已排序列\{a1, a2\}(或\{a2, a1\})中的元素从尾到头比较即a3先与a2进行比较：若a3>=a2则a3加入已排序列，则已排序列变为\{a1, a2, a3\};  
若a3< a2，则继续与a1进行比较：若a3>=a1则插入到已排序列a2的位置则已排序列变为\{a1, a3, a2\}；若`a3<a1`，则a3插入到已排序列a1的位置则已排序列变为\{a3, a1, a2\}。

第三步：直到取出所有的待排序列中的元素，并插入到已排序列中为止。

// 直接版
    void insertSort(int a[], int n) {
            for (int i = 1; i < n; ++i) { // i表示要插入元素的索引，在插入过程中不能改变
                    int key = i; // key表示插入元素在插入过程中的索引，可能随时改变
                    for (int j = i-1; j >= 0; --j) {
                            if (a[key] < a[j]) {
                                    int tmp = a[key];
                                    a[key] = a[j];
                                    a[j] = tmp;
                                    key = j;
                            }
                    }
    
            }
    }

// 一般版本
    // 使用数学概念中的取值范围来确定要移动元素的索引范围
    void insertSortOther(int a[], int n) {
            for (int i = 1; i < n; ++i) {
                    int j = i-1;
                    // 注意：循环的条件有两个：一个是数组索引范围，另一个是元素大小
                    while (j >= 0 && a[i] < a[j]) { 
                    // j的取值范围：[-1,i-1](其中j索引为-1，即a[0]~a[i-1]都大于a[i]) 或 [ j, i-1](其中a[j] >= a[i])
                            j--;
                    }
                    int temp = a[i];
                    for (int k = i; k > j; k--) { // k=(j, i]
                          a[k] = a[k-1];
                    }
                    a[j+1] = temp; // j+1才是a[i]元素最终的位置索引
            }
    }

## 希尔排序 ##

希尔排序(Shell Sort)是插入排序的一种。也称**缩小增量排序**，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

### 基本原理 ###

步骤1：序列\{a1, a2, a3, … an\}中以增量div 划分原序列为多个新的序列\{a1, a(1+div), a(1+2\*div)… a(1 + n\*div)\}, \{a2, a(2+div), a(2+2\*div)… a(2 + n\*div)\} …. \{an, a(n+div), a(n+2\*div)… a(n + n\*div)\};

步骤2：分别对新划分序列进行直接插入排序

步骤3：缩小div值div/ = 2，重新按步骤一方式划分子序列，进行直接插入排序

步骤n: 当div = 1时，对现有序列进行直接插入排序，得到排序后的序列。

### 希尔排序的时间性能优于直接插入排序的原因 ###

1.  当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
2.  当n值较小时，n和 的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0( )差别不大。
3.  在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。  
    因此，希尔排序在效率上较直接插入排序有较大的改进。

### 实现 ###

// 直接版
    void swap(int *pa, int *pb) {
            int tmp = *pa;
            *pa = *pb;
            *pb = tmp;
    }
    
    void shellSort(int a[], int n) {
            // 增量div {
       5, 2, 1}
            for (int div = 5; div > 0; div /=2) {
                    // 分组{
       0, 0+div, 0+2*div, ...},{
       1, 1+div, 1+2div,...},...
                    for (int i = 0; i < div; i++){
                            // 每一组进行直接插入排序
                            for (int j = i+div; j < n; j += div) {
                                    int key = j; // key值在变化
                                    for (int k = j-div; k >=0; k -= div) {
                                            if (a[key] < a[k]) {
                                                    swap(a+key, a+k);
                                                    key = k;
                                            }
                                    }
                            }
                    }
            }
    }