快速排序
排序流程：
- 每次选区第一个的数为基准数
- 然后将大于和小于基准的元素分别置于基准数两边
- 继续分别对基准数两侧未排序的数据使用分治法进行细分处理(分而治之)，直至整个序列有序。
如下图所示：
代码实现:
#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;
}
