排序算法 六 快速排序

快速排序它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

对快速排序不是很理解的人可以点击白话经典算法系列之六 快速排序 快速搞定，该博主写的非常清楚易懂，比喻也比较形象。

1.对于一个待排序列，可以找一个基准点，然后将所有大于基准点的数放到基准点左边，所有小于基准点的数，放到基准点右边。

2.以基准点为分界线，将序列分成左右两个序列，然后在对基准点两边的序列重复操作，直到每个子序列只有一个元素。这是一个递归的过程

void QSort(int k[], int low, int high)
{
	int point = 0;//基准点
	if (low < high)//只要序列包含一个以上的元素,递归进行
	{
		point = Partition(k, low, high);//找基准点和排序
		QSort(k, low, point - 1);//对基准点左边的序列进行快速排序
		QSort(k, point + 1, high);//对基准点右边的数进行快速排序
	}
}

对于基准点，可以选取待排序列的第一个元素作为基准点。

对于待排序列a[10]=5, 2, 6, 0, 3, 9, 1, 7, 4, 8

1.

第一次，基准点为5，首先从末尾开始找一个小于5 的数， 可以找到4比5小，交换4和5的位置

2.从头开始找一个大于基准点5的数，将它与基准点现在所在的位置交换

3.重复上述步骤，直到比基准点5大的数都在5左边，比5小的数都在基准点右边

对基准点的处理过程代码如下：

int Partition(int k[],int low,int high)
{

	int point = k[low];//其中一种解决方式，每次令基准点=序列第一个元素，
	while (low < high)
	{
		//在右边找一个小于基准点的数
		while (low < high&&k[high] >= point)
		{
			high--;
		}
		//交换位置
		swap(k, low, high);
		//在左边找一个小于基准点的数
		while (low < high&&k[low] <= point)
		{
			low++;
		}
		swap(k, low, high);
	}
	return low;//返回基准点最后所在的位置
}

4.对于5左右两边的序列，快速排序，处理过程 重复1,2,3

完整代码入下：

#include <stdio.h>

void swap(int k[], int low, int high)
{
	int temp;
	temp = k[low];
	k[low] = k[high];
	k[high] = temp;
}
int Partition(int k[],int low,int high)
{

	int point = k[low];//其中一种解决方式，每次令基准点=序列第一个元素，
	while (low < high)
	{
		//在右边找一个小于基准点的数
		while (low < high&&k[high] >= point)
		{
			high--;
		}
		//交换位置
		swap(k, low, high);
		//在左边找一个小于基准点的数
		while (low < high&&k[low] <= point)
		{
			low++;
		}
		swap(k, low, high);
	}
	return low;//返回基准点最后所在的位置
}
void QSort(int k[], int low, int high)
{
	int point = 0;//基准点
	if (low < high)//只要序列包含一个以上的元素,递归进行
	{
		point = Partition(k, low, high);//找基准点和排序
		QSort(k, low, point - 1);//对基准点左边的序列进行快速排序
		QSort(k, point + 1, high);//对基准点右边的数进行快速排序
	}
}
void QuickSort(int k[], int n)
{
	QSort(k, 0, n - 1);
}



int main()
{
	int a[10] = { 5, 2, 6, 0, 3, 9, 1, 7, 4, 8 };
	QuickSort(a, 10);
	for (int i = 0; i <10; i++)
	{
		printf(\"%d \", a[i]);
	}
	return 0;
}

关于快速排序还有很多优化的方式，主要优化在基准点的选取