排序——插入排序

直接插入排序

插入排序的原理类似于打扑克牌，通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到响应位置并插入。

算法步骤

将待排序序列的第一个元素做为有序序列，吧第二个元素到最后一个元素当成未排序序列

从头到尾一次扫描未排序序列，将扫面的每个元素插入有序序列的适当位置

代码实现

void insertion_sort(vector<int> &arr) {
    for (int i = 1; i <= arr.size(); i++) {
        int temp = arr[i];
        int j = i - 1;
        while ((j >= 1) && (temp < arr[j])) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11

折半插入排序

它是在直接插入排序的基础上的一种改进，因为在查找插入位置时没索要查找的序列一定是有序序列，所以我们利用折半二分的思想来优化查找的效率。

算法步骤

1. 设待排序的记录存放在数据$arr[n]$中，$arr[1]$是一个有序序列
2. 循环$n-1$次，每次使用折半查找，查找$arr[i]$在已排好序列的序列中插入位置，然后将$arr[i]$插入表长为$i-1$的有序序列，直到将$arr[n]$插入有序序列中。

代码实现

typedef struct {
	int key[100];
	int length;
}Sqlist;
void BInsertSort(Sqlist &arr){
	for(int i = 2; i <= arr.length; i++){
		arr.key[0] = arr.key[i];//将待插入的记录暂时存到哨兵位置
		int low = 1, high = i -1;//初始化查找区间
		while(low <= high){
			int m = (low + high) / 2;//折半
			if(arr.key[0] < arr.key[m]) high = m - 1;
			else low = m + 1;
		}
		for(int j = i - 1; j >= high + 1; j--) arr.key[j+1] = arr.key[j];//记录后移
		arr.key[high + 1] = arr.key[0];
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

希尔排序

希尔排序，也称之为递减增量排序算法，是插入排序的一种更高效的版本。它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

void shell_sort(vector<int> &arr) {
    int h = 1, len = arr.size();
    while (h < len / 3) h = h * 3 + 1;
    while (h >= 1) {
        for (int i = h; i < len; i++) {
            for (int j = i; j >= h && arr[j] < arr[j - h]; j -= h) {
                swap(arr[j], arr[j - h]);
            }
        }
        h = h / 3;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13