快速排序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;
}

另外,这篇博客写的挺好的,形象易懂:

坐在马桶上看算法之快速排序

上一篇:用jQuery实现限制输入字数的文本框


下一篇:sphinx续4-coreseek的工作原理