常见的排序算法（三） 交换排序（冒泡排序，快速排序）

 今天，给大家带来的是交换排序。

  首先，我们来了解一下什么叫交换排序。所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

  那么接下来，我们来看一下。冒泡排序。

冒泡排序（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

这篇博文列举了交换排序，基本可以掌握其中概要，管中窥豹，不求甚解。如果你有任何建议或者批评和补充，请留言指出，不胜感激，更多参考请移步互联网。