【算法】快速排序

快速排序

排序流程：

1. 每次选区第一个的数为基准数
2. 然后将大于和小于基准的元素分别置于基准数两边
3. 继续分别对基准数两侧未排序的数据使用分治法进行细分处理(分而治之)，直至整个序列有序。

如下图所示：

代码实现:

#include<iostream>
using namespace std;


void print(int* arr, int len)
{
	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
}

int parttion(int arr[], int low, int high)
{
	int i = low;//从左边开始
	int j = high;//从右边开始

	int base = arr[low];//定左边第一个为基准书，拿出来之后，该位置就可以被覆盖了

	//如果low就是最
	if (low < high)
	{
		//左找一个，右找一个......
		while (i < j) //i == j说明已经查找完毕
		{
			while (i < j && arr[j] >= base)//从右边开始遍历，比基准值大，不做改变，继续遍历，直到碰到比基准值小的
			{
				j--;
			}
			if (i < j)//右边找到小于基数的数
			{
				arr[i++] = arr[j];

			}
			while (i < j && arr[i] < base)//从左边开始遍历，比基准值小，不做改变，继续遍历，直到碰到比基准值大的
			{
				i++;
			}
			if (i < j)//左边已经找到大于基数的数
			{
				arr[j--] = arr[i];
			}
		}
		//查找完毕
		//将基准值放入它应该在的位置
		arr[i] = base;
	}	
	//返回基准值位置
	return i;
}

void QuickSort(int* arr,int low, int high)
{
	if (low < high)
	{
		int index = parttion(arr, low, high);//寻找基准值，然后开始分而治之
		//index这个位置的数已经是它该放的位置
		QuickSort(arr, low, index - 1);
		QuickSort(arr, index + 1, high);
	}
}

int main(void)
{
	int arr[] = { 3,1,4,5,5,4,1,3 };
	int len = sizeof(arr) / sizeof(arr[0]);
	QuickSort(arr, 0, len - 1);
	print(arr, len);
	return 0;
}