快速排序C++

/*
 * quick_sort.cpp
 *
 *  Created on: 2016-3-21
 *      Author: Lv_Lang
 */

//快速排序
#include <iostream>
using namespace std;

int a[100];//全局定义数组，方便函数使用

void swap(int i,int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

/*快速排序解释：
核心思想是找一个基准元素（一般选取首位元素），
然后遍历元素，比基准小的放左边，比基准大的放右边。
但其实按这个思想来写代码其实比较难写的，
所以说的更通俗一点就是：先把首位的拿出来被比较，
用一个哨兵j从数组最右边开始扫描，如果有小于基准的，先停下来；
然后哨兵i开始从数组最左边开始扫描，如果有大于基准的，也停下来；
此时左边有个比基准大的，右边有个比基准小的，交换二者就行了。
最后当两个哨兵相遇时，证明左右都扫了一遍了，
然后把他们相遇的那个点的元素跟基准元素互换位置，这就得到了一个初步排序的序列。
然后把刚才得到的序列切成两半（不含基准元素），
基准前面的元素是一半，基准后面的元素是另一半，对这两个子序列重复刚才的那个步骤。
递归一下，就能最终得到排好序的序列了。*/

void quick_sort(int left,int right)
{
	if(left >= right)//递归临界条件
		return;
	int i,j,temp;
	i = left;
	j = right;
	temp = a[left];
	while(i < j)
	{
		while(a[j] >= temp && i < j)
			j--;
		while(a[i] <= temp && i < j)
			i++;
		swap(i,j);
	}
	swap(left,i);
	quick_sort(left,i-1);
	quick_sort(i+1,right);
}

int main()
{
	int n;
	cin>>n;
	for(int i=0;i < n;i++)
		cin>>a[i];
	quick_sort(0,5);
	for(int i=0;i<5;i++)
		cout<<a[i]<<" ";
	cout<<a[5]<<endl;

	return 0;
}
另外，这篇博客写的挺好的，形象易懂：
坐在马桶上看算法之快速排序
巴特西

快速排序C++

最新文章

热门文章
