写个笔记。

冒泡算法不多说,很简单,基本思路就是不断的把最大的数送往最大数该有的位置,然后把第二大数送往第二大应有的位置。简单粗糙的实现代码:

void SortArray(int* _pArray, int _nArraySize)
{
	for(int i = 0; i < _nArraySize - 1; ++i)
	{
		for(int j = 0; j < _nArraySize - 1 - i; ++j)
		{
			if(_pArray[j] > _pArray[j+1])
			{
				int nSwap = _pArray[j];
				_pArray[j] = _pArray[j+1];
				_pArray[j+1] = nSwap;
			}
		}
	}
}

快速排序稍微有点复杂。理论上是一种分而治之的思维,而具体表现则是分多次循环,每一个循环,将待排序数组排序为 (比基准数小的数) 基准数 (比基准数大的数)。所以每次排序的核心算法就是把数组分割成2部分。

这个分割算法以前也没多研究过,前几天看了别人的文章,大概自己理解了下。基本思路就是创建两个索引,分别为头索引及尾索引,分别是数组头及尾的索引。基本思路如下:

1.首先选择基准数,现在选择头索引锁指向的值,并记录下基准数的索引值。

2.尾索引开始向头索引移动,分别判断索引指向的值,假设该值小于基准数,则尾索引扫描停止。假设尾索引到了头索引的位置,则停止扫描,将基准数与尾索引指向的值进行交换,记录下基准数现在所在的索引,此轮分割结束,直接跳向下轮分割(步骤5)

3.头索引向尾索引移动,分别判断头索引指向的值,假设该值大于基准数,则头索引扫描停止。假设头索引到了尾索引的位置,则停止扫描,将基准数与头索引指向的值进行交换,记录下基准数现在所在的索引,此轮分割结束,直接跳向下轮分割(步骤5)

4.在头索引及尾索引没有碰撞的情况下,则交换两个索引指向的值,跳向步骤2继续开始分割。

5.分割结束。则将基准数现在的索引旁边的2个字数组就行分割。

6.排序完成

步骤是有点多,核心内容就是尾索引向头索引移动,找到比基准数小的数,头索引相似。分割的结束点在两索引碰撞的时候,这时候分割就结束了,我们只要交换基准数和碰撞点的数就可以了。分割完成后基准数左边的数值都小于基准数,右边的数都大于基准数。

自己写了个简陋的算法,算是实现了自己理解的思路:

void QuickSort(int* _pArray, int _nHead, int _nTail)
{
	if(_nHead >= _nTail)
	{
		//	nothing
		return;
	}
 
	//	find the base number
	int nBaseNumber = _pArray[_nHead];
	int nBaseNumberPosition = _nHead;
	int nCheckHeadIndex = _nHead;
	int nCheckTailIndex = _nTail;
	bool bLoopBreak = false;
 
	for(;;)
	{
		for(; nCheckTailIndex >= nCheckHeadIndex; --nCheckTailIndex)
		{
			if(nCheckTailIndex == nCheckHeadIndex)
			{
				std::swap(_pArray[nCheckTailIndex], _pArray[nBaseNumberPosition]);
				nBaseNumberPosition = nCheckTailIndex;
				bLoopBreak = true;
				break;
			}
 
			if(_pArray[nCheckTailIndex] < nBaseNumber)
			{
				break;
			}
		}
 
		if(bLoopBreak){break;}
 
		for(; nCheckHeadIndex <= nCheckTailIndex; ++nCheckHeadIndex)
		{
			if(nCheckHeadIndex == nCheckTailIndex)
			{
				std::swap(_pArray[nCheckHeadIndex], _pArray[nBaseNumberPosition]);
				nBaseNumberPosition = nCheckHeadIndex;
				bLoopBreak = true;
				break;
			}
 
			if(_pArray[nCheckHeadIndex] > nBaseNumber)
			{
				break;
			}
		}
 
		if(bLoopBreak){break;}
 
		std::swap(_pArray[nCheckHeadIndex], _pArray[nCheckTailIndex]);
	}
 
	// sort the left 2 parts
	if(nBaseNumberPosition > _nHead + 1)
	{
		QuickSort(_pArray, _nHead, nBaseNumberPosition - 1);
	}
	if(nBaseNumberPosition < _nTail - 1)
	{
		QuickSort(_pArray, nBaseNumberPosition + 1, _nTail);
	}
}
共 0 条回复
暂时没有人回复哦,赶紧抢沙发
发表新回复

作者

sryan
today is a good day