常見(jiàn)的排序算法（三） 交換排序（冒泡排序，快速排序）

 今天，給大家?guī)?lái)的是交換排序。

  首先，我們來(lái)了解一下什么叫交換排序。所謂交換，就是根據(jù)序列中兩個(gè)記錄鍵值的比較結(jié)果來(lái)對(duì)換這兩個(gè)記錄在序列中的位置，交換排序的特點(diǎn)是：將鍵值較大的記錄向序列的尾部移動(dòng)，鍵值較小的記錄向序列的前部移動(dòng)。

  那么接下來(lái)，我們來(lái)看一下。冒泡排序。

冒泡排序（Bubble Sort），是一種計(jì)算機(jī)科學(xué)領(lǐng)域的較簡(jiǎn)單的排序算法。

它重復(fù)地走訪過(guò)要排序的數(shù)列，一次比較兩個(gè)元素，如果他們的順序錯(cuò)誤就把他們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換，也就是說(shuō)該數(shù)列已經(jīng)排序完成。

冒泡排序算法的運(yùn)作如下：

比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。

對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。

針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。

持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。

冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào)。比較是相鄰的兩個(gè)元素比較，交換也發(fā)生在這兩個(gè)元素之間。所以冒泡排序是一種穩(wěn)定排序算法。

void BubbleSort(int* a,int size)   //冒泡排序
{
	for(int j= 0;j<size-1;j++)
	for(int i = 0;i<size-j-1; i++)
	{
		if(a[i]>a[i+1])
		swap(a[i],a[i+1]);
	}
}

  接下來(lái)就是比較難懂的快速排序了。

  首先，我們的了解什么事快速排序。

  快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過(guò)一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨(dú)立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對(duì)這兩部分?jǐn)?shù)據(jù)分別進(jìn)行快速排序，整個(gè)排序過(guò)程可以遞歸進(jìn)行，以此達(dá)到整個(gè)數(shù)據(jù)變成有序序列。

快速排序有遞歸寫法和非遞歸寫法。首先，我為大家介紹的遞歸的寫法。

int Mid(int* a,int left,int right)
{
	int key = a[right];
	int begin = left;
	int end = right;
	while(begin <end)
	{
		while(begin <end && a[begin] <=key)
			begin++;

		if(begin <end)
                 a[end--] =a[begin];

		while(begin <end && a[end] >=key)
			end--;

		if(begin <end)
		 a[begin++] =a[end];	
	}
	
	a[begin] = key;
	return begin;
	
}


void QuickSort(int* a,int left ,int right)  //快速排序
{
	
	if(left >= right)
		return;

	int indix = Mid(a,left,right);
	QuickSort(a,left,indix-1);
	QuickSort(a,indix+1,right);
	
}

以上的方式，便是最常見(jiàn)的快速排序的遞歸寫法。

下面的另外一種是《算法導(dǎo)論》中所提及的方法，讀者可以看看

int QuickSort_OR(int* a,int left ,int right)
{
	int prev = left - 1;
	int cur = left;
	int key = a[right];
	for(;cur <= right; cur++)
	{
		if(a[cur] <= key )
		{
			++prev;
			swap(a[prev],a[cur]);
		}
	}

	return prev;

}


void QuickSort(int* a,int left ,int right)  //快速排序
{
	
	if(left >= right)
		return;

	int indix = QuickSort_OR(a,left,right);
	QuickSort(a,left,indix-1);
	QuickSort(a,indix+1,right);
	
}

從以上的兩種方法便可以看出，在快速排序中找到KEY的值是至關(guān)重要的，故而有人提出了優(yōu)化。

int RandPartition(int* a, int left , int right)  //三數(shù)取中
{    
	assert(a);
	int mid = left + (right-left)/2;
	if(a[left]<a[mid])
	{
		if(a[mid] < a[right])
			return a[mid];
		else if(a[left] > a[right])
			return a[left];
		else
			return a[right];
	}
	else     //
	{
		if(a[mid]> a[right])
			return a[mid];
		else if(a[left] > a[right])
			return a[right];
		else
			return a[left];

	}
}

這樣就可以極大的減少key取到最大或者最小的情況，更加有利于快速排序。

但是，當(dāng)區(qū)間很小的時(shí)候，還要遞歸，這樣不僅浪費(fèi)資源，還使得運(yùn)算速度變慢，故而有人便想到了，當(dāng)區(qū)間小于某個(gè)程度是，我們是否可以用其他的排序來(lái)代替它呢？故而，又有一種優(yōu)化

void QuickSort(int* a,int left ,int right)  //快速排序
{
	if(right - left<13)
		InserSort(a,right-left);
	else
	{
	if(left >= right)
		return;

	int indix = Mid1(a,left,right);
	QuickSort(a,left,indix-1);
	QuickSort(a,indix+1,right);
	}
}

當(dāng)區(qū)間小于13時(shí)便可以調(diào)插入排序（若不知道插入排序，請(qǐng)看本人博客（一））

非遞歸方法

void QuickSort_no(int* a,int left,int right)
{
     assert(a);
     stack<int> s;
     s.push(left);//壓棧數(shù)組的左下標(biāo)
     s.push(right);//壓棧數(shù)組的有下標(biāo)
    while (!s.empty())
  {
           int tmpRight = s.top();
             s.pop();
            int tmpLeft = s.top();
              s.pop();  
	int div = Mid1(a, tmpLeft, tmpRight);//把數(shù)組排序成左區(qū)間的數(shù)小于等于有區(qū)間的數(shù)
 
            if (tmpLeft < div - 1)
           {                                    //壓棧左區(qū)間的左右兩個(gè)數(shù)的下標(biāo)
                   s.push(tmpLeft);
                    s.push(div - 1);
            }
         
             if (div + 1 < tmpRight)
          {
                   s.push(div + 1);     //壓棧右區(qū)間的左右兩個(gè)數(shù)的下標(biāo)
                    s.push(tmpRight);
           }
   }
  
}

以上方法是通過(guò)棧的方式實(shí)現(xiàn)的，注釋已經(jīng)詳細(xì)說(shuō)明。

若想視覺(jué)感受各排序算法http://blog.jobbole.com/11745/

如果想對(duì)快速排序有進(jìn)一步的了解和加深的同學(xué)，可以看看http://dsqiu.iteye.com/blog/1707060

這篇博文列舉了交換排序，基本可以掌握其中概要，管中窺豹，不求甚解。如果你有任何建議或者批評(píng)和補(bǔ)充，請(qǐng)留言指出，不勝感激，更多參考請(qǐng)移步互聯(lián)網(wǎng)。