常見的排序算法（三） 交換排序（冒泡排序，快速排序）

 今天，給大家帶來的是交換排序。

  首先，我們來了解一下什么叫交換排序。所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

  那么接下來，我們來看一下。冒泡排序。

冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。

它重復地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換，也就是說該數列已經排序完成。

冒泡排序算法的運作如下：

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

對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。

針對所有的元素重復以上的步驟，除了最后一個。

持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。

冒泡排序就是把小的元素往前調或者把大的元素往后調。比較是相鄰的兩個元素比較，交換也發生在這兩個元素之間。所以冒泡排序是一種穩定排序算法。

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]);
	}
}

  接下來就是比較難懂的快速排序了。

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

  快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。

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

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);
	
}

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

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

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的值是至關重要的，故而有人提出了優化。

int RandPartition(int* a, int left , int right)  //三數取中
{    
	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取到最大或者最小的情況，更加有利于快速排序。

但是，當區間很小的時候，還要遞歸，這樣不僅浪費資源，還使得運算速度變慢，故而有人便想到了，當區間小于某個程度是，我們是否可以用其他的排序來代替它呢？故而，又有一種優化

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);
	}
}

當區間小于13時便可以調插入排序（若不知道插入排序，請看本人博客（一））

非遞歸方法

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

以上方法是通過棧的方式實現的，注釋已經詳細說明。

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

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

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