插入排序------基本有序序列的最佳选择

插入排序( Insertion Sort )是又一经典排序算法,因每次将一个新元素插入到有序序列并保持序列有序而得名。插入排序是处理基本有序序列的最佳选择。

算法原理/步骤

  1. 从序列中取出第一个元素,形成一个有序序列;
  2. 从待排序序列中取出下一个元素,从有序序列尾部向前开始检索,找到一个位置,使得将新元素放在该处后,仍然有序;
  3. 将该元素插入到该位置
  4. 重复过程2、3,直到取完所有元素;

(来自维基百科)

时间复杂度

从算法原理中可以看到,每次只对一个元素进行排序,故原序列第K个位置上的元素最多需要K次比较和1次赋值、最少1次比较和1次赋值即可完成,故时间复杂度最快为O(N),最差为O(N^2),平均为O(N^2)。注:最好情况:序列有序;最坏:序列逆序。

稳定性

插入排序中元素间交换不是跳跃性的,所以是稳定的排序。

算法演示

下面给出是对某组数据进行排序的过程演示。(还是维基的)

注:演示的过程与文中所给代码有些许差异,在于图片中先找到位置再插入,而文中代码则是一边检索位置一边交换。对应的代码请 点击查看 查看。

更加高大上的演示,请 猛击这里

实例代码

#include<iostream>
#include<cstdlib>
#include<ctime>

using namespace std;

#define MAXN 10

int insert_sort(int *, int);

int main()
{
	int src[MAXN];
	for(int i=0; i<MAXN; i++)
		src[i] = rand()%10000;//先随机生成MAXN个数字,做测试用

	for(int i=0; i<MAXN; i++)
		cout<<src[i]<<" ";
	cout<<endl;//输出原始数据

	//执行插入排序
	insert_sort(src, MAXN);

	/*检查排序结果*/
	for(int i=0; i<MAXN-1; i++)
	{
		if(src[i]>src[i+1]){
			cout<<"wrong"<<endl;
		}
	}

	cout<<"sort finished!"<<endl;
	return 0;
}


int insert_sort(int *src, int size)
{
	for(int i=0; i<size; i++)
	{
		//从第一个元素开始,每次取出一个加入到有序序列中
		int j=i;
		while(j<0 && c[j-1])
		{
			//找到新元素在有序序列中的位置
			swap(src[j], src[j-1]);
			j--;
		}
	}

	return 0;
}

算法改进

  1. 文中给出的代码在处理每一个元素时,都会经过最多i次比较、K次交换(3次赋值)。可以通过先比较得出位置再赋值的办法来减少赋值(K+1次交换)。
  2. 检索位置过程中利用二分查找可以减少一定次数的比较。
  3. 添加哨兵节点(即在序列头加入一个无穷小的元素),减少越界判断操作。(想出这办法的人太聪明了)

总结

插入排序算法是一种思想简单明了的算法,在处理一些基本有序的序列上甚至优于其他算法,例如快速排序。

详细代码请 点击这里 查看。

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章