直接插入排序与希尔排序

Posted on Edited on In Views: Word count in article: 2.9k Reading time ≈ 29 mins.

直接插入排序与希尔排序)
前言：直接插入排序与希尔排序都属于插入排序，它们排序的思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止得到一个新的有序序列
在这里插入图片描述

注意：下文中所有排序都是升序

一、直接插入排序

 直接插入排序思想：每一趟将一个待排序的记录（元素），按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止

1.1 单趟排序实现

将待插入元素x插入[0,end]的有序序列，从后向前比较，当x值小于arr[end]时,arr[end+1] = arr[end],end减1。当end < 0或x >= arr[end]时候，退出循环,并arr[end+1] = x

在这里插入图片描述

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int	Sort(int* arr,int size,int x)
{
	int end = size-1; 
	while(end >= 0)
	{
		if(x < arr[end])
		{
			arr[end+1] = arr[end];
			end--;
		}
		else
		{
			break;
		}
	}
	arr[end+1] = x;
}

1.2 直接插入排序实现

 当一个数组有n个元素，数组下标范围为: [0,n-1],可以将第1个元素作为一个有序序列，将第2个元素进行单趟排序，然后将前2个元素作为一个有序序列，将第3个元素进行单趟排序… …直到将前n-1个元素作为有序序列，将第n个元素进行单趟排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void InsertSort(int* arr, int n)
{
	assert(arr);
	for (int i = 0; i < n - 1;i++) // 待排序趟数为n-1,下标小于等于i的元素已经是有序的，默认第一个元素有序，所以下标从0开始
	{ 
		int end = i;  
		int elem = arr[end+1]; // 待插入元素
		while (end >= 0)
		{
			if (elem < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = elem; 
	}
}

1.3 时间复杂度与空间复杂度

当待排序序列是逆序时，时间复杂度最坏：O(N^2) 当待排序序列本身是有序时，时间复杂度最好：O(N) 。直接插入排序只用了常数个辅助变量空间，空间复杂度：O(1)

说明：
 ●序列中元素越接近有序，直接插入排序的时间效率越高，序列逆序，效率很低
 ●直接插入排序是一个稳定的排序算法

二、希尔排序

 直接插入排序在两种情况下效率很高，情况一：当待排序的序列本身接近有序时候，只需要少量插入操作可以完成整个序列的排序。情况二：待排序序列元素个数比较少的时候。

 希尔排序是对直接插入排序的优化，希尔排序的思想：先选定一个整数gap，把待排序序列分为gap个子序列（组），所有距离为gap的元素分在同个子序列中，此时每个子序列元素个数比较少，然后对每个子序列进行直接插入排序。重复上述分组和排序的工作。当整个序列基本有序时进行一次直接插入排序，让序列中元素全部有序

  1. 多次分组预排序（让序列接近有序）
  2. 直接插入排序（让序列有序）
    在这里插入图片描述

2.1 对一组子序列的第一趟排序

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int gap = 5;
int end = 0; // 因为是第一组子序列，end=0
int elem = arr[end+gap];
while(end>=0)
{
	if(elem < arr[end])
	{
		arr[end+gap] = arr[end];
		end-=gap;	
	}
	else
	{
		break;
	}
}

arr[end+gap] = elem;

2.2 对一组子序列的直接插入排序

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int gap = 2;
for(int i = 0;i < n-gap;i += gap) // n 为数组元素个数
{
	int end = i; 
	int elem = arr[end+gap];
	while(end >= 0)
	{
		if(elem < arr[end])
		{
			arr[end+gap] = arr[end];
			end-=gap;	
		}
		else
		{
			break;
		}
	}
	arr[end+gap] = elem;
}

2.3 一次预排序

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int gap = 2;
for(int j = 0;j<gap;j++) // 对gap组子序列分别进行直接插入排序
{

	for(int i = j;i < n-gap;i += gap) // 对每一组子序列进行直接插入排序
	{
		int end = i; 
		int elem = arr[end+gap];
		while(end >= 0) // 对某一组的某一趟排序
		{
			if(elem < arr[end])
			{
				arr[end+gap] = arr[end];
				end-=gap;	
			}
			else
			{
				break;
			}
		}
		arr[end+gap] = elem;
	}
}

2.4 一次预排序（代码简单版）

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
/*
	2.3 一次预排序思想：是对gap组子序列分别进行直接插入排序，即先对第一组子序列直接插入排序、
	然后对第二组子序列直接插入排序......最后对第gap组子序列直接插入排序
	
	2.4 一次预排序思想：对gap组子序列混合进行直接插入排序，因为某一组子序列需要进行多趟排序，可以首先对
	第一组子序列进行第一趟排序、对第二组子序列进行第一趟排序......对第gap组子序列进行第一趟排序。
	然后对第一组子序列进行第二趟排序、对第二组子序列进行第二趟排序......对第gap组子序列进行第二趟排序。
	......
	最后第一组子序列进行最后一趟排序、然后对第二组子序列进行最后一趟排序......最后对第gap组子序列进行最后一趟排序。
*/
int gap = 2;
for(int i = 0;i < n-gap;i++) // 对gap组子序列混合进行直接插入排序
{
	int end = i; 
	int elem = arr[end+gap];
	while(end >= 0) 
	{
		if(elem < arr[end])
		{
			arr[end+gap] = arr[end];
			end-=gap;	
		}
		else
		{
			break;
		}
	}
	arr[end+gap] = elem;
}

2.5 希尔排序

希尔排序：1. 进行多次分组预排序 2. 直接插入排序

进行多次分组预排序首先要确定gap的值，但是对gap怎样取值使希尔排序时间效率最高是一个数学难题。这里用gap=[n/2]
gap = [gap/2]的取法，即第一次分组预排序gap值为数组元素个数一半，后续分组预排序gap值为上次分组预排序gap值的一半，当gap=1时相当于进行了直接插入排序

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
void ShellSort(int* arr, int n)
{
	assert(arr);
	int gap = n;
	while (gap > 1)
	{
		gap /= 2; // 当gap大于1时是多次分组预排序，当gap等于1时是直接插入排序
		for (int i = 0; i < n - gap; i++) 
		{
			int end = i;
			int elem = arr[end + gap];
			while (end >= 0)
			{
				if (elem < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = elem;
		}
	}
}

2.6 时间复杂度与空间复杂度

对于gap取值有多种方法，并且进行多次分组预排序后数组接近有序，后续分组预排序以及直接插入排序每趟比较次数越来越少。所以希尔排序的时间复杂度分析是一个十分复杂问题，时间复杂度大约为O(N^1.3) 。空间复杂度：O(1)

说明：
 ●希尔排序适合序列中元素个数较多情况
 ●希尔排序是一个不稳定的排序算法

三、直接插入排序与希尔排序性能测试

排序时间效率与CPU紧密相关，不同计算机上测出结果可能不同，我们只需要关注同一计算机下两种排序所耗费时间相差倍数

3.1 基础代码

因为要进行多种情况测试，为了避免代码庸余，在后续测试中只需要把基础代码粘贴进去即可

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
44
45
46
47
48
49
50
51
52
53
54
55
#include <stdio.h>
#include <assert.h>
#include <time.h>
#include <stdlib.h>

void InsertSort(int* arr, int n)
{
	assert(arr);
	for (int i = 0; i < n - 1;i++) // 待排序次数为n-1,下标小于等于i的元素已经是有序的
	{ 
		int end = i;  
		int elem = arr[end+1]; // 待插入元素
		while (end >= 0)
		{
			if (elem < arr[end])
			{
				arr[end + 1] = arr[end];
				end--;
			}
			else
			{
				break;
			}
		}
		arr[end + 1] = elem; 
	}
}

void ShellSort(int* arr, int n)
{
	assert(arr);
	int gap = n;
	while (gap > 1)
	{
		gap /= 2; // 当gap大于1时是多次分组预排序，当gap等于1时是直接插入排序
		for (int i = 0; i < n - gap; i++) 
		{
			int end = i;
			int elem = arr[end + gap];
			while (end >= 0)
			{
				if (elem < arr[end])
				{
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = elem;
		}
	}
}

3.2 数组元素个数较少情况

数组元素个数为：1万，两个数组元素完全相同，分别使用直接插入排序与希尔排序

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
void test()
{
	
	int N = 10000; // 数组元素个数

	int* arr1 = (int*)malloc(sizeof(int) * N);
	int* arr2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		arr1[i] = rand()%1000; // 生成[0,999]范围内随机数
		arr2[i] = arr1[i]; // 数组arr2元素等于数组arr1元素
	}

	int begin1 = clock(); // 排序前时间
	InsertSort(arr1, N);
	int end1 = clock(); // 排序后时间

	int begin2 = clock();
	ShellSort(arr2, N);
	int end2 = clock();

	printf("InsertSort：%d\n", end1 - begin1);
	printf("ShellSort：%d\n", end2 - begin2);

	free(arr1);
	free(arr2);
}


int main()
{
	srand((unsigned int)time(NULL));
	test();
	return 0;
}

输出 （单位为毫秒）

1
2
InsertSort：15
ShellSort：1

结论：元素个数较少情况，直接插入排序与希尔排序所花时间没有太大差距，在元素个数极少情况下，直接插入排序比希尔排序所花时间更少

3.3 数组元素个数较多情况

数组元素个数为：100万，两个数组元素完全相同，分别使用直接插入排序与希尔排序

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
void test()
{
	
	int N = 1000000; // 数组元素个数

	int* arr1 = (int*)malloc(sizeof(int) * N);
	int* arr2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		arr1[i] = rand()%1000; // 生成[0,999]范围内随机数
		arr2[i] = arr1[i]; // 数组arr2元素等于数组arr1元素
	}

	int begin1 = clock(); // 排序前时间
	InsertSort(arr1, N);
	int end1 = clock(); // 排序后时间

	int begin2 = clock();
	ShellSort(arr2, N);
	int end2 = clock();

	printf("InsertSort：%d\n", end1 - begin1);
	printf("ShellSort：%d\n", end2 - begin2);

	free(arr1);
	free(arr2);
}


int main()
{
	srand((unsigned int)time(NULL));
	test();
	return 0;
}

输出 （单位为毫秒）

1
2
InsertSort：148991
ShellSort：121

结论：元素个数较多情况，直接插入排序与希尔排序所花时间有着巨大差距，希尔排序远优于直接插入排序

3.4 直接插入排序有序与逆序情况测试

数组元素个数为：1万，arr1为有序，arr2为逆序，都用直接插入排序

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
void test()
{
	
	int N = 10000; // 数组元素个数

	int* arr1 = (int*)malloc(sizeof(int) * N);
	int* arr2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		arr1[i] = i; // arr1为有序
		arr2[i] = N-arr1[i]; // arr2为逆序
	}

	int begin1 = clock(); // 排序前时间
	InsertSort(arr1, N);
	int end1 = clock(); // 排序后时间

	int begin2 = clock();
	InsertSort(arr2, N);
	int end2 = clock();

	printf("InsertSort 有序情况：%d\n", end1 - begin1);
	printf("InsertSort 逆序情况：%d\n", end2 - begin2);

	free(arr1);
	free(arr2);
}


int main()
{
	test();
	return 0;
}

输出 （单位为毫秒）

1
2
InsertSort 有序情况：0
InsertSort 逆序情况：1948

结论：当数组接近有序，使用直接插入排序效率最高，时间复杂度为O(N)。当数组接近逆序,使用直接插入排序效率很低，时间复杂度为O(N^2)

3.5 希尔排序有序与逆序情况测试

数组元素个数为：100万，arr1为有序，arr2为逆序，都用希尔排序

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
void test()
{
	
	int N = 1000000; // 数组元素个数

	int* arr1 = (int*)malloc(sizeof(int) * N);
	int* arr2 = (int*)malloc(sizeof(int) * N);
	for (int i = 0; i < N; i++)
	{
		arr1[i] = i; // arr1为有序
		arr2[i] = N-arr1[i]; // arr2为逆序
	}

	int begin1 = clock(); // 排序前时间
	ShellSort(arr1, N);
	int end1 = clock(); // 排序后时间

	int begin2 = clock();
	ShellSort(arr2, N);
	int end2 = clock();

	printf("ShellSort 有序情况：%d\n", end1 - begin1);
	printf("ShellSort 逆序情况：%d\n", end2 - begin2);

	free(arr1);
	free(arr2);
}


int main()
{
	test();
	return 0;
}

输出 （单位为毫秒）

1
2
ShellSort 有序情况：36
ShellSort 逆序情况：42

结论：希尔排序相对于直接插入排序，面对逆序情况下有了很好的优化