排序算法——快速排序

问题描述 

现有一组数据：23,45,18,11,13,79,72,25,3,17,请使用快速排序算法将它们按照从小到大的顺序排列。

算法思想

（1）在无序数据中选一个基准数（通常为数据第一个）；

（2）将数据中小于基准数的数据移到基准数左边，大于基准数的移到右边；

（3）对于基准数左、右两边的数据，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。

程序代码

#include<iostream>
using namespace std;
void quickSort(int* arr, int begin, int end)//arr:需要排序的数组，begin:需要排序的区间左边界，end:需要排序的区间的右边界
{
	if (begin < end)//如果区间不只一个数
	{
		int temp = arr[begin]; //将区间的第一个数作为基准数
		int L = begin; //从左到右进行查找时的“指针”，指示当前左位置
		int R = end; //从右到左进行查找时的“指针”，指示当前右位置
		while (L < R)//不重复遍历
		{
			while (L<R && arr[R] > temp)//当右边的数大于基准数时，略过，继续向左查找。
				                        //不满足条件时跳出循环，此时的R对应的元素是小于基准元素的
				R--;
			arr[L] = arr[R];//将右边小于等于基准元素的数填入右边相应位置
			while (L < R && arr[L] <= temp)//当左边的数小于等于基准数时，略过，继续向右查找。
				                           //(重复的基准元素集合到左区间)。
										   //不满足条件时跳出循环，此时的i对应的元素是大于等于基准元素的
				L++;
			arr[R] = arr[L];//将左边大于基准元素的数填入左边相应位置
		}
		arr[L] = temp;//将基准元素填入相应位置,此时的L即为基准元素的位置
		quickSort(arr, begin, L - 1);//对基准元素的左边子区间进行相似的快速排序
		quickSort(arr, L + 1, end);//对基准元素的右边子区间进行相似的快速排序
	}
	else  return;//如果区间只有一个数，则返回
}
int main()
{
	int num[10] = { 23,45,18,11,13,79,72,25,3,17 };
	int n = 10;
	cout << "排序前的数组为：" << endl;
	for (int i = 0; i < n; i++)
		cout << num[i] << ' ';
	quickSort(num, 0, n - 1);
	cout << "\n排序后的数组为：" << endl;
	for (int i = 0; i < n; i++)
		cout << num[i] << ' ';
	return 0;
}