首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >插入排序与希尔排序

插入排序与希尔排序

作者头像
zy010101
发布2019-05-25 19:57:29
7030
发布2019-05-25 19:57:29
举报
文章被收录于专栏:程序员程序员

插入排序描述:有一个数组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²)。

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

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018年08月21日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档