八大排序算法之快速排序

算法思想：

找到一个基准（第一个数据），从后往前找比基准小的数据往前移动，从前往后找比基准大的数据往后移动，重复前两步，直到找到基准位置，  这是快速排序的一次划分，之后多次调用一次划分，直到完全有序

代码实现（递归）

 //快速排序的一次排序
int partition(int* arr, int low, int high)
{
	int tmp = arr[low];
	while (low < high)
	{
		//从后往前找比基准小的数字
		while (low < high && arr[high] > tmp)
		{
			high--;
		}
		if (low < high)
		{
			arr[low] = arr[high];
		}

		//从前往后找比基准大的数字
		while (low < high && arr[low] < tmp)
		{
			low++;
		}
		if (low < high)
		{
			arr[high] = arr[low];
		}
	}
	
	arr[low] = tmp;
	return low;
}

void QuickSort(int* arr, int low,int high)
{
	int par = partition(arr, low, high-1);
	if (low < par - 1)//左边数字超过一个
	{
		QuickSort(arr, low, par - 1);
	}
	if (par+1 < high)//右边的数据超过一个
	{
		QuickSort(arr, par + 1, high);
	}
}

效率分析

O(nlogn),O(logn),不稳定

快速排序特点：

缺点：不稳定，空间复杂度大

最大缺点：越有序越慢，完全有序时间复杂度为O(n^2)

快速排序如果越有序越慢，完全有序退化成选择排序