快速排序算法

算法思想是通过一组排序将数列分割成两部分，其中一部分的所有数据都要比另一部分所有数据小；然后再按照此方法对着两部分数据分别进行快速排序，整个排序过程可以递归进行。

1 算法过程：

1. 选取val = arr[l]的作为基准（可以在这里进行优化：**arr[l+r]**为基准）。

2. 从r开始往前找一个小于val的数字，放在l的位置，l++;

3. 从l开始往后找一个大于val的数字，放在r的位置，r++;

4. 循环步骤2 和 3，最后返回。

2 时间复杂度和空间复杂度

分别分析平均和最坏情况下的时间复杂度。

2.1平均时间复杂度：O(logn) * O(n)

递归是树形，所以时间复杂度是O(logn) ；分割处理需要从前向后对比，所以时间复杂度是O(n);

2.2平均空间复杂度：O(logn)

树形所以是O(logn)；

2.3最坏情况下时间复杂度：O(n)*O(n)=O(n^2)

假如数据是有序的（升序或者降序），以升序为例，会出现下面情况，该树的形状如下：

所以最坏情况下的时间复杂度是O(n)*O(n)=O(n^2);

2.4最坏情况下的空间复杂度：O(n)

3 代码

快速排序可以用递归实现，在考虑递归时候，只考虑水平方向一层即可，计算机的调用的垂直方式进行的。

// 快排分割处理函数
int Partition(int arr[], int left, int right)
{
	int val = arr[left];
	while (left < right)
	{
		// 1. 从右边开始，找到比val小的就停止
		while (left < right && arr[right] > val)
		{
			--right;
		}
		if (left < right)
		{
			arr[left] = arr[right];
			left++;
		}
		
		// 2. 从左边开始向后找，找到比val大的就停止 
		while (left < right && arr[left] < val)
		{
			++left;
		}
		if (left < right)
		{
			arr[right] = arr[left];
			right--;
		}
	}
	// left 和 right指向了同一个位置
	arr[left] = val;
	return left;
}
// 快速排序算法
// 时间复杂度：处理数据从头到尾O(n)；树形递归O(logn) 
// 最坏情况下时间复杂度：一颗只有左子树或右子树的树O(n*n)
// 空间复杂度：O(logn)，最坏情况下空间复杂度O(n)
// 稳定性：进行交换时候，
void QuickSort(int arr[], int left, int right)
{
	// 递归结束条件
	if (left >= right)
	{
		return;
	}
	int pos = Partition(arr, left, right);
	QuickSort(arr, left, pos);
	QuickSort(arr, pos + 1, right);
}

void QuickSort(int arr[], int size)
{
	QuickSort(arr, 0, size - 1);
}
int main()
{
	const int CONNT = 10;
	int arr[CONNT] = { 1,2,3,9,10,4,5,6,7,8, };
	show(arr, CONNT);
	QuickSort(arr, CONNT);
	show(arr, CONNT);
	//int idx = BinartSearch1(arr,  CONNT, 4);
	system("pause");
	return 0;
}

4 算法优化

优化1：随着快速排序执行，数据会变得越来越有序，这时候采用插入排序，算法效率是最高的。
优化2：“三数取中法”，从一列数据中，找到基准数，这个基准数处于有序元素中间的位置。

// 插入排序  
void InsertSort1(int arr[], int size)
{
	for (int i = 1; i < size; i++) // 控制趟数,同时arr[i]是每趟中的无序元素
	{
		int val = arr[i];  // 每次比较时，将最后一个值拿出来了，所以可以进行下边的arr[j+1] = arr[j];
		int j = i - 1;
		for (; j >= 0; j--)   // 控制有序元素中，依次从后向前比较
		{
			if (arr[j] <= val)
			{
				break;
			}
			arr[j + 1] = arr[j];
		}
		arr[j + 1] = val;
	}
}

// 快排分割处理函数
int Partition(int arr[], int l,int r)
{
	// 优化2：选择基准数的优化，“三数取中”，arr[l] arr[r]  arr[(l+r)/2]

	// 基类基准数
	int val = arr[l];
	// 一次快排处理 O(n)
	while (l < r)
	{
		while (l < r && arr[r] > val)  // 从右边开始往前找一个小于val的数字
		{
			r--;
		}
		if (l < r)
		{
			arr[l] = arr[r];
			l++;
		}

		while (l < r && arr[l] < val)  // 从左边开始找到大于val的数
		{
			l++;
		}
		if (l < r)
		{
			arr[r] = arr[l];
			r--;
		}
	}
	// 最后，当l == r时候，arr[r] = val
	arr[r] = val;
	return r;

}
// 时间复杂度：O(logn)   * O(n)
// 空间复杂度：递归占用的栈内存 O(logn)
// 最坏时间复杂度：n*O(n) = o(n^2)
void QuickSort(int arr[],int begin,int end)  // 1 递归的参数
{
	// 2 递归的结束条件 
	if (begin >= end)
	{
		return;
	}
	// 优化1：当[begin,end]序列的元素个数小于指定数量时候，采用插入排序
	if (end - begin <= N)  // 这个 N 根据实际的数量进行调试，确定。
	{
		InsertSort1(arr, end - begin);
		return;
	}
	// 3 在begin 和 end 之间做一次快排分割处理
	int pos = Partition(arr, begin, end);  // O(n)

	// 对基准数的左右序列，再分别进行快排。
	QuickSort(arr, begin, pos - 1);
	QuickSort(arr, pos + 1, end);
}