排序算法之插入排序

最新推荐文章于 2021-07-26 19:58:28 发布

algorithm_only

最新推荐文章于 2021-07-26 19:58:28 发布

阅读量1.4k

点赞数 4

文章标签：算法 shell output n2 insert list

本文链接：https://blog.csdn.net/algorithm_only/article/details/7007479

版权

本节主要分析插入排序算法的直接插入排序和希尔（shell）排序（又称缩小增量排序）。

1. 直接插入排序

该排序是最简单的排序方法，其基本思想是：假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1..i-1]中，生成含n个记录的有序区。

直接插入排序算法：

void insert_sort(sqlist *s)
{
	int		i, j;

	for (i = 2; i <= s->len; ++i) {
		if (s->data[i].key < s->data[i-1].key) {	/* 仅当待排记录比前一个小时才进行排序 */
			s->data[0] = s->data[i];				/* 复制为哨兵，作为副本 */
			s->data[i] = s->data[i-1];
			for (j = i - 2; s->data[0].key < s->data[j].key; --j) {
				s->data[j + 1] = s->data[j];		/* 记录后移 */
			}
			s->data[j + 1] = s->data[0];			/* 在正确位置上进行插入 */
		}
		output_list(*s);						/* 测试用，查看每一趟排序结果 */
	}
}

直接插入排序从第2个元素开始，用该元素和其前面的元素进行比较，当待排记录比前一个小时该趟要发生数据移动，首先将待排元素复制一份作为比较时用，然后将待排元素前一个元素后移，覆盖在待排元素的位置（因为刚才已经比较过一次了，前一个元素大，要后移），再将待排元素和前面的比较，若待排元素小就再将和其比较的元素后移，直到有一个元素小于或等于待排元素，此时找到正确位置，将待排元素插入，一趟排序完毕。再将第3、4······到最后一个元素重复上述步骤，此时排序完毕。

直接插入排序分析：

从上面叙述可见，直接插入排序算法简洁，容易实现。从空间来看，只需要一个辅助空间，从时间看，基本操作为：比较两个关键字大小何移动记录。花时间最少情况：待排序列按关键字非递减有序排列（正序），只需比较关键字次数达最小值n-1，记录不需移动。花时间最多情况：待排序列按关键字非递增有序排列（逆序），总比较次数达最大值(n+2)(n-1)/2，记录移动次数也达到最大值(n+4)(n-1)/2。考虑随机情况：可取上述最小和最大值的平均值作为直接插入排序是所需进行关键字的比较次数和移动次数，约为n方/4。故直接插入排序时间复杂度为O（n方）。

2. 希尔排序（Shell’s Sort）

希尔排序也是一种插入排序类的方法，其在时间效率上角前述几种排序方法右较大改进。从上面直接插入排序分析可知，若待排记录序列按关键字基本有序时，直接插入排序效率可大大提高。另一方面，直接插入排序算法简单，在n值很小时效率也比较高。希尔排序正是从这两点分析出发对直接插入排序进行改进的到的一种插入排序算法。

希尔排序算法基本思想：先取一个小于n的整数d₁作为第一个增量，把文件的全部记录分成d₁个组。所有距离为d_l的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量d₂<d₁重复上述的分组和排序，直至所取的增量d_t=1(d_t<d_t-l<…<d₂<d₁)，即所有记录放在同一组中进行直接插入排序为止。

希尔排序算法：

void shell_sort(sqlist *s)
{
	int		d, i, j;
	
	d= s->len;
	do {
		d = d / 3 + 1;					/* 确定增量 */
		for (i = d+1; i <= s->len; ++i) {	/* 和直接插入排序类似，只是增量不一样 */
			if (s->data[i].key < s->data[i-d].key) {
				s->data[0] = s->data[i];
				for (j = i-d; j>0 && s->data[0].key < s->data[j].key; j-=d)
					s->data[j+d] = s->data[j];
				s->data[j+d] = s->data[0];
			}
		}
		output_list(*s);				/* 测试用，查看每一趟排序结果 */
	} while (d > 1);
}

Shell排序的增量暂时没有最好的的序列，增量序列有个种取法，但应注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须为1.

有人通过大量实验得出结论：当n较大时，比较和移动的次数约在n^l.25到1.6n^1.25之间。

3. 两种算法比较

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

希尔排序是不稳定的。根据shell排序算法分析，两个相同关键字在排序前后的相对次序很可能发生变化。