首页 > 代码库 > 若干排序算法简单汇总(一)

若干排序算法简单汇总(一)

转载请注明出处

http://blog.csdn.net/pony_maggie/article/details/35819279


作者:小马


从题目看,首先不是全部是若干。排序算法很多,我个人的能力也有限,不可能都讲到。另外,是简单汇总,是希望能用最简单的代码,最简短的语言说明问题,不搞太多理论分析。

 

就像前面说的,排序算法有很多,而且不存在哪一种最不好,哪一种最好这样的说法。根据用途不同选择最适合的就行了。不过仅从时间复杂度来看,基本上有两种,一种是O(n^2), 一种是O(nlogn)。

 

所谓的时间复杂度,其实是基于多少次基本操作定义的,在排序算法中,基本操作指两类,一是比较,二是记录从一个位置移动另一个位置。下面讲到的排序算法都会涉及到这些操作。

 

 

一直接插入排序

 

先从一个最简单的切入。它的思种是这样的,把一个数插入到已排好的序列中。比如已有一个有序序列:

{ 12, 23, 25, 40}

现在有一个数18要插入进来,并且保证插入后序列还是有序。18开始和序列中的所有数逐一比较(从右向左比较),比40小,40后移,比25小,25后移,比23小,23后移,跟12比,发现比12大,停在这里,插入到23的位置,最终变为:

{ 12, 18, 23, 25, 40}

 

上面的过程叫一趟插入排序,基于这个思想, 我们可以认为数组第一个元素是有序的,所以可以从第二个元素开始,每个元素都做一趟插入排序就可以得到一个有序序列。代码就很简单了,

int insertSort(int nArray[], int nLength)
{
	int i = 0;
	int j = 0;
	int nSerity = 0;//备份要插入的那个元素

	for (i = 1; i < nLength; i++)
	{
		if (nArray[i] < nArray[i-1])
		{
			nSerity = nArray[i];
			nArray[i] = nArray[i-1];
			for (j = i-2; (j >= 0)&&(nSerity < nArray[j]); j--)
			{
				nArray[j+1] = nArray[j];
			}
			nArray[j+1] = nSerity;
		}
	}
	return 0;
}
很容易看出它的时间复杂度是O(n^2)

 

二冒泡排序

这个排序算法基本是大学老师必讲的,因为它除了简单之外,也确实比较好玩。思路是这样的,一个无序序列a[n], a[1]和a[2]比较,如果a[1]>a[2], 它们就交换位置,否则不做处理。继续a[2]和a[3]同样的原理比较,一直到a[n-1]和a[n]比较。

 

上面的过程叫一趟冒泡,请你在脑海里想像下这个过程,我下面要说的这个结论希望你能想明白,那就是经过一趟冒泡后,序列中最大的那个元素已经被换到a[n]的位置了。有没有觉得这个过程就像冒泡一样,只不过这个泡是向下冒的。

 

做第二趟冒泡时,只要对a[1]~a[n-1]操作就行了,结果是序列中第二大的那个元素在a[n-1]的位置了。然后经过n趟冒泡后,排序就完成了。

 

通过上面的过程也很容易得出冒泡排序的时间复杂度是O(n^2),可以上代码了,

//bChange作用是为了对于已排好序的序列,能
//及时退出来。
int bubbleSort(int nArray[], int nLength)
{
	int i = 0;
	int j = 0;
	int nTemp = 0;

	bool bChange = true;
	for (i = 0; (i < nLength) &&(bChange); i++)
	{
		bChange = false;
		for (j = 0; j < (nLength - i - 1); j++)
		{
			if (nArray[j] > nArray[j+1])
			{
				nTemp = nArray[j];
				nArray[j] = nArray[j+1];
				nArray[j+1] = nTemp;
				bChange = true;
			}
		}
	}

	return 0;
}
可以好好理解一下代码中bChange变量的作用,这里不多说解释了,留给大家思考。


这篇就打算写这么多了,主要篇幅太长怕大家看着厌烦,过几天有空了再接着写吧。

 

代码下载地址:

http://download.csdn.net/detail/pony_maggie/7568971

https://github.com/pony-maggie/SortDemo