8-11二路插入排序

一.基本概念
通过增加辅助空间来减少移动次数

下面对序列49,38,65,97,76,13,27,49进行从小到大排序。将其放入a数组中

创建一个数组b，长度与a相同

int n = 8;
int *b = (int*)malloc(n * sizeof(int));
1
2

为b数组设置head和tail，其中head指向当前序列的最小元素，tail指向当前序列的最大元素，因此从head到tail遍历即可得到从小到大的序列。

将a[0]放入b[0]，完成第一个元素49的插入。此时只有一个元素，最大最小都是49，head和tail都指向0

int head,tail;
	head = tail = 0;
1
2

设置变量i，从1起对a数组的每个元素处理

for (int i = 1; i < n; i++) 
1

a[i]=38 当前head为0，可以将数组看成是循环数组，即0号位的左边是7号位。因此head–写为head=(head-1+n)%n，这里n是元素个数，为8

if (a[i] < b[head]) {
	  head=(head-1+n)%n;
	  b[head] = a[i];
}
1
2
3
4

通过for循环i++，再去处理下一个元素

a[i]=65>b[tail]=49，tail++（可以看成，tail不会越界，因此不需要模除），将a[i]放入tail所指位置

if (a[i] > b[tail]) {
		tail++;
		b[tail] = a[i];
}
1
2
3
4

a[i]=97>b[tail]=65，tail++，b[tail] = a[i]

a[i]=76不小于b[head]也不大于b[tail]，从a[tail]处按直接插入排序进行插入

先让97后移

tail++;
b[tail] = b[tail - 1];
1
2

j=tail-1为第一个可能插入的点
对比a[i]和b[j-1]，b[j-2]…，大的b逐个后移，直到跳出循环，将a[i]放入

for (j = tail - 1; b[j-1] > a[i];j--) {
		b[j] = b[j - 1];
}
b[j] = a[i];
1
2
3
4

继续对下一个元素处理

a[i]=13，head–，b[head]=a[i]
（代码中对head的-1处理都要加模除）

处理a[i]=27，tail++，97后移，j指向tail-1，作为第一个可能插入的位置

通过for循环对j处理，76后移j- -（j=2），65后移j- -（j=1），49后移j- -（j=0），38后移j- -（j=7）（注意模除），在7号位插入a[i]，即a[j]=a[i]

对上述代码（需要移动元素的代码）加入模除，即将j- -改为j=(j-1+n)%n

for (j = tail - 1; b[(j-1+n)%n] > a[i];j=(j-1+n)%n) {
		b[j] = b[(j - 1 + n) % n];
}
b[j] = a[i];
1
2
3
4

处理最后一个元素49，按照代码b大的后移，等的不动，因此该算法是稳定的。因此97,76,65后移，2号位插入49

至此在b数组中完成了排序，下面从head到tail依次复制到数组a[0]到a[7]

for (int k = 0; k < n; k++) {
	a[k] = b[head];
	head=(head+1)%n;//可能越界的加入模除
}
1
2
3
4

二.完整代码

#include
#include
using namespace std;
int n = 8;
int *b = (int*)malloc(n * sizeof(int));

void twInsert(int a[], int n) {
	b[0] = a[0];
	int head,tail;
	head = tail = 0;
	for (int i = 1; i < n; i++) { //处理a[i]
		if (a[i] < b[head]) { //比b[head]小
			head=(head-1+n)%n;
			b[head] = a[i];
		}
		else if (a[i] > b[tail]) { //比b[tail]大
			tail++;
			b[tail] = a[i];
		}
		else { //在中间，需要移动元素
			int j;
			tail++;
			b[tail] = b[tail - 1];
			for (j = tail - 1; b[(j-1+n)%n] > a[i];j=(j-1+n)%n) { //大的后移，等的不动
				b[j] = b[(j - 1 + n) % n];
			}
			b[j] = a[i];//a[i]插入
		}
	}
	for (int k = 0; k < n; k++) {//复制到a数组
		a[k] = b[head];
		head=(head+1)%n;
	}
}
int main()
{
	int a[8] = { 49,38,65,97,76,13,27,49 };
	twInsert(a, 8);
	for (int i = 0; i < 7; i++)
	{
		cout << a[i] << " ";
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

三.效率分析
1.时间复杂度：（分析过程仅供参考）取决于移动元素和比较元素。最坏情况：放第一个元素，移动0，比较0，放第二个元素移动0比较1，放第三个元素比较2移动1，放第四个元素比较3移动2，放第五个元素比较4移动3…放第n个元素比较(n-1)移动(n-2)，求和为n²-2n+1，此外还有最后复制到a数组的时间+n，即n²-n+1，因此总的时间复杂度为O(n²)
2.空间复杂度：O(n)
3.稳定性：稳定