DS 图解快排

　　　　快速排序是交换排序,是冒泡排序的改进版。

　　　　快排过程:

　　　　　　1.选定一个分界值

　　　　　    2.分成三个部分(小于分界部分,分界值,大于分界值部分)

                     

　　　　　　3.对于分开的两部分重复上述操作,直到排序完成

　　　　　　

　　　　C/C++代码:

//分界值切分

//挖坑法:

int PartSortWakeng(int *a, int begin, int end)

{

	//挖空第一个值作为分界值

	int tmp = a[begin];

	while (begin<end)

	{

		//右指针碰到小于基准值,填坑,原位置变坑

		while (begin < end && a[end] >= tmp)

		{

			--end;

		}

		a[begin] = a[end];

		//左指针碰到大于基准值,填坑,原位置变坑

		while (begin<end && a[begin] <= tmp)

		{

			++begin;

		}

		//填右坑

		a[end] = a[begin];

	}

	//将基准值填到坑里

	a[begin] = tmp;

	return tmp;     //返回分界值位置

}

//快排：1.找到分界值 2.切分成三部分 3.对于剩下两部分进行上述操作

void QuickSort(int *a, int left,int right)

{

	//终止条件: 待排序部分只剩一个或没有元素了,已经有序

	if (left >= right)

	{

		return;

	}

       //分界值切分

	int div = PartSort(a, left, right);

       //剩余部分重复操作

	QuickSort(a, left, div - 1);

	QuickSort(a, div + 1, right);

}

　　　　稳定性: 不稳定

　　　　时间复杂度: O(nlogn)