插入排序

发表于

插入排序介绍

  • 直接插入排序
  • 折半插入排序
  • 希尔排序

直接插入排序

思路

n个待排数据存放在a[n]中。开始时，a[0]为唯一的有序数据，a[1]~a[n-1]为n-1个无序数据。排序过程都是取出无序数据中的第一个数据插入到前面已经有序的数据中，这样经过了n-1次插入后，完成排序工作。

图示

image

代码实现

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
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int a[] = { 6, 5, 3, 1, 8, 7, 2, 4 };

	int i = 1;
	int j = 0;
	int temp = 0;
	for (i = 1; i < 8; i++)
	{
		if (a[i - 1] > a[i])     /* a[i] > a[i -1]，此时已经有序，无序排序 */
		{
		    //取出第一个数据
			temp = a[i];
			//寻找插入位置
			for (j = i - 1; temp < a[j] && j >= 0; --j)
			{
			     /* 将数据往后移动，给需要插入的那个数腾个空间 */
				a[j + 1] = a[j];      
			}
			a[j + 1] = temp;          /* 插入到合适的位置  */
		}
	}

	for (i = 0; i < 8; i++)
	{
		printf("%d,", a[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}

算法分析

最好情况为正序的时候，最坏情况为逆序的时候。时间复杂度为o(n*n)。

折半插入排序

思路

在前面直接插入排序的基础上，优化了寻找插入位置段的代码，通过折半查找的方式查找插入位置，来寻找插入的位置。

代码实现

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
#include <stdio.h>
#include <stdlib.h>

int main()
{
	int a[] = { 6, 5, 3, 1, 8, 7, 2, 4 };

	int i = 1;
	int j = 0;
	int temp = 0;
	int high = 0;
	int low = 0;
	int mid = 0;
	for (i = 1; i < 8; i++)
	{
		if (a[i - 1] > a[i])     /* a[i] > a[i -1]，此时已经有序，无序排序 */
		{
			temp = a[i];
			high = i - 1;
			low = 0;
			while (low <= high) //折半查找插入的位置
			{
				mid = low + (high - low) / 2;

				if (temp < a[mid])
				{
					high = mid - 1;
				}
				else
				{
					low = mid + 1;
				}
			}

			/* 将数组的内容后移 */
			for (j = i; j > low; --j)
			{
				a[j] = a[j - 1];
			}
			a[low] = temp;
		}
	}

	for (i = 0; i < 8; i++)
	{
		printf("%d,", a[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}

算法分析

折半插入排序优化了最坏的情况下的比较次数，但是还是记录的移动次数是没有减少的，所以其时间复杂度还是：O(n*n)

希尔排序

思路

先将整个待排记录序列分割成若干个序列分别进行直接插入排序，待整个序列的记录“基本有序”时，再对全体进行一次直接插入排序。

图示

把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到1时，整个数据合成为一组，构成一组有序记录，则完成排序。

image

代码实现

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
#include <stdio.h>
#include <stdlib.h>

/* 直接插入排序 */
void insert_sort(int *a, int start, int gap,int len)
{
	int i = 0;
	int j = 0;
	int temp = 0;
	for (i = start + gap; i < len; i = i + gap)          /* 步长为gap */
	{
		if (a[i - gap] > a[i])
		{
			temp = a[i];

			for (j = i - gap; j >= start && temp < a[j]; j = j - gap)   //这个注意我们是从start开始的
			{
				a[j + gap] = a[j];
			}
			a[j + gap] = temp;
		}
	}
}

void sort(int * a, int len)
{
	int start = 0;
	int gap = 0;
	int i = 0;
	for (gap = len / 2; gap > 0; gap = gap / 2)    /* 几趟希尔排序 */
	{
		for (start = 0; start < gap; start++)      /* gap为组数，对每组进行直接插入排序*/
		{
			insert_sort(a, start, gap, len);
		}
	}
}

int main()
{
	int a[] = { 84, 83, 88, 87, 61, 50, 70, 60, 80, 99 };
    int i = 0;
	sort(a, 10);
	for (i = 0; i < 10; i++)
	{
		printf("%d,", a[i]);
	}
	printf("\n");
	system("pause");
	return 0;
}

算法分析

希尔排序中对于增量序列的选择十分重要，直接影响到希尔排序的性能。我们上面选择的增量序列{n/2,(n/2)/2…1}(希尔增量)，其最坏时间复杂度依然为O(n*n)，一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n^1.5)。

总结

今天学习了三种排序算法，其中希尔排序算法在性能上是最好的，希尔排序算法是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多，原因是，当n值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。当n值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。正是这两种情况的结合才使希尔排序效率比插入排序高很多。

参考：

动态参考
博客参考