快速排序.md

快速排序（Quick Sort）

思想

快速排序可以这样的大致区分为三个步骤

• 1、选择基准，先从数组（或者容器）中（随机）取出一个数作为基准数

• 2、分区过程，遍历数组将其中比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边（默认从左至右为从小到大的排列）

• 3、重复区分过程，再对左右区间重复第二步，直到各区间只有一个数，也就是最后左右两个指针指向了同一个位置。

Partition

快速排序中的 Partiton 函数的主要目的如下，给定一个数组 array[] 和 数组 中任意一个元素 a（一般快排中是选择下标最大的那个元素），重排数组使得 a 左边都小于它，右边都不小于它。

当然现在这个地方讲 Partition 的话单纯是针对 快速排序，但是 Partition 的使用不仅仅仅限于此，举个例子如果我想查找一堆数中的第 K 大的数用 Partition 也是可以实现的，大致的思路如下：

• 随机找个一个数进行 Partion
• 将 Partion 操作之后的这个随机数的索引 +1 与 K 比较
• 如果比 K 小 则在右部分继续，否则在左部分继续，直到索引 +1 == K （以上默认排列顺序从左到右为从小到大）

实现

C++ 实现代码如下：

Partiton：

int Partition(vector<int> arr, int left, int right, int RandIndex){
    if(RandIndex <= right && RandIndex >= left){
    int Flag = arr[RandIndex];
    swap(arr[RandIndex],arr[right]);
    int storeIndex = left;
    for(int i = left; i < right; i++){
        if(arr[i] < Flag){
            swap(arr[i],arr[storeIndex]);
            ++storeIndex;
        }
    }
    swap(arr[RandIndex],arr[right]);
    return storeIndex;
    }
}

    2 9 8 4 1 7 | 4 storeIndex = 0  i = 0
    2 9 8 7 1 4 | 4 storeIndex = 1  i = 1
    2 9 8 7 1 4 | 4 storeIndex = 1  i = 2
    2 9 8 7 1 4 | 4 storeIndex = 1  i = 3
    2 9 8 7 1 4 | 4 storeIndex = 1  i = 4
    2 1 8 7 9 4 | 4 storeIndex = 2  i = 5
    jump out for loop
    2 1 4 7 9 8 | 4 storeIndex = 2
    return storeIndex = 2

Quick Sort

//Recursion version
void QuickSort(int r[],int first,int end,Random(first,end))
{
	int index=0;
	if(first<end)
	{
		index=Partition(r,first,end);
		QuickSort(r,first,index-1);//前半部分递归
		QuickSort(r,index+1,end);//后半部分递归
	}
}