专栏首页程序员插入排序与希尔排序

插入排序与希尔排序

插入排序描述:有一个数组num[n];它有n个元素,假设其中n-1已经排好序了,那么把剩余的那个元素插入到合适的位置即可,这样就完成了排序。根据这个思想,很明显的可以使用递归来完成它。下面是递归版本的代码.

#include <iostream>
using namespace std;
void InsertionSort(int *num, int n);
int temp;
int main()
{
	int num[10] = { 0,2,4,9,8,5,6,7,3,1};
	//int num[10] = { 0,1,1,1,1,0,1,1,1,1 };
	InsertionSort(num, 10);
	for (int i = 0; i < 10; i++)
	{
		cout << num[i] << '\t';
	}
	cout << endl;
	system("pause");
}
void InsertionSort(int *num, int n)
{
	if (1 == n)		//基准条件
	{
		return ;
	}
	else
	{
		int i;
		InsertionSort(num, n - 1);
		if (num[n - 1] > num[0])
		{
			for (i = n - 2; i >= 0; i--)
			{
				if (num[n - 1] > num[i])		//已经排序好的序列中有比第n-1个小的
				{
					temp = num[n - 1];
					for (int j = n - 1; j > i; j--)
					{
						num[j] = num[j - 1];
					}
					num[i + 1] = temp;
					break;
				}
			}
		}
		else	//已经排序好的序列中都比第n-1个大
		{
			temp = num[n - 1];
			for (int i = n - 1; i > 0; i--)
			{
				num[i] = num[i - 1];
			}
			num[0] = temp;
		}
	}
}

递归版本的插入排序,这个程序比较复杂,时间复杂度是Ω(n³)的,因为那个双层循环至少迭代n次,并且循环最大是O(n²)。这个递归版本写起来也不好写。因为数组的插入时间复杂度就是O(n)。如果将数组改成链表,那么数组的插入这个操作的时间复杂度将会降低为O(1)。那么采用循环实现的插入排序的时间复杂度就会降低为O(n²)。

void InsertionSort1(int *num, int n)		//循环方式
{
	int temp;
	int j;
	for (int i = 0; i < n - 1; i++)
	{
		temp = num[i + 1];
		for (j = i + 1; j > 0; j--)
		{
			if (temp > num[j - 1])         
			{
                //如果当前要插入的元素大于等于序列中的某个元素大,那么插入该位置
				num[j] = temp;
				break;
			}
			else          //把小于要插入元素的值向后移动一个位置,为插入工作做准备。
			{
				num[j] = num[j - 1];
			}
		}
	}
}

很明显,循环实现的代码时间复杂度只有O(n²)。

基于限位器版本的插入排序,它省略了j > 0的这个判断操作。限位器加在了序列的最前面。在这里就是num[0]。这个限位器保证了它不会超出数组的范围。

void InsertionSort2(int *num, int n)
{
	int temp;
	int j;
	for (int i = 1; i < n; i++)
	{
		temp = num[i + 1];
		num[0] = temp;					 //限位器
		for (j = i + 1;; j--)            //省略了j > 0这个判断
		{
			if (temp >= num[j - 1])		//直接接在后面
			{
				num[j] = temp;
				break;
			}
			else						//把数组里面的数据向后移动一个位置。
			{
				num[j] = num[j - 1];
			}
		}
	}
}

插入排序在输入的数组是严格降序的情况下,(因为此处排序算法是按照升序排列的)该算法出现最坏情况。但是时间复杂度仍然维持在O(n²)。但是该算法对于基本按照升序排列的输入数据有着优秀的表现。(刚好和快速排序相反)这个优点使得它领先于同样时间复杂度的选择排序和冒泡排序。

值得一提的是,上面插入的过程中,可以将顺序查找改为二分查找,但是这个改动仅对链表有效,对于数组而言,没有用,因为即使找到位置变快了,但是移动的次数并不会减少。所以说算法和数据结构是息息相关的。数据结构设计的好,算法的效率也会得到提高。

基于插入排序,Shell发明了希尔排序,希尔排序使用一个增量序列h1,h2,...,ht。要求这个序列中h1必须等于1.在使用hk的一趟排序之后,对于每一个i有num[i] <= num[i + hk]成立。所有相隔hk的元素都被排序。Shell本人给出的增量序列是ht = n/2和hk = h(k+1)/2.(k,t是下标).根据这个策略实现的代码如下。

#include "pch.h"
#include <iostream>
using namespace std;

void ShellSort(int *num, int size);
int main()
{
	int num[10] = { 0,2,4,9,8,5,6,7,3,1 };
	ShellSort(num, 10);
	for (int i = 0; i < 10; i++)
	{
		cout << num[i] << '\t';
	}
	cout << endl;
	system("pause");
}

void ShellSort(int * num, int size)
{
	int i, j, increasement;
	int temp;
	for ( increasement = size / 2; increasement > 0; increasement /= 2)
	{
		for (i = increasement; i < size; i++)
		{
			temp = num[i];
			for ( j = i; j >= increasement; j -= increasement)
			{
				if (temp < num[j - increasement])
				{
					num[j] = num[j - increasement];
				}
				else
				{
					break;
				}
			}
			num[j] = temp;
		}
	}
}

但是这个增量序列并不是足够好。它的最坏情况是退化为插入排序。因此增量问题在于增量序列未必是互为质数。希尔排序看起来比较简单。但是它的时间复杂度的分析时非常困难的。最坏情况下希尔排序为θ(n²)。

但是希尔排序的实际性能是可以接受的,即使面对很大的数据也是如此。在希尔排序中,增量序列的设计是困难的,它的好坏决定了希尔排序的快慢。(因为它的运行时间依赖于增量序列的选择)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数组循环移动的几种解决方法

    本文转载自:https://blog.csdn.net/lanceleng/article/details/8707168

    zy010101
  • 分治法

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.ne...

    zy010101
  • PAT(乙级)1019

    分析:这个题目,没什么难度。但是我被超时问题困扰了一会儿,可能是scanf函数用的次数有点多,所以改了一下,直接通过了。

    zy010101
  • 排序算法总结

    关于各种排序算法的总结表格,这里偷个懒直接用Simple life的博客http://blog.csdn.net/whuslei/article/details...

    用户1215536
  • 欧拉计划problem13

    37107287533902102798797998220837590246510135740250 463769376774900097126481248...

    小二哥
  • BZOJ 2038: [2009国家集训队]小Z的袜子(hose)【莫队算法裸题&&学习笔记】

    2038: [2009国家集训队]小Z的袜子(hose) Time Limit: 20 Sec  Memory Limit: 259 MB Submit: 9...

    Angel_Kitty
  • 分治法

    版权声明:本文为博主原创文章,转载请注明博客地址: https://blog.csdn.ne...

    zy010101
  • 杨辉三角形

    梦_之_旅
  • 【GPLT】L1-034 点赞

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • 程序员面试金典 - 面试题 05.07. 配对交换(位运算)

    配对交换。编写程序,交换某个整数的奇数位和偶数位,尽量使用较少的指令(也就是说,位0与位1交换,位2与位3交换,以此类推)。

    Michael阿明

扫码关注云+社区

领取腾讯云代金券