快速排序

速度快，占内存（迭代）

• 先从后往前找最小的，再从前往后找最大的；
• 在数据中选取一个元素，将所有比其大的放在左边，将所有比其小的放在右边；
• 然后再将左边的和右边的分别选出一个元素，进行上述操作直到排序结束。

具体实施&思想

1.对所有待排序元素，设定i为最左边下标，j为最右边下标，k为选取的元素（arr[i]，即将arr[i]“挖掉”，i为“坑”）。
2.从j开始，j--，找出<=k的，令arr[i] = arr[j],相当于将j元素“挖掉”，填到i，此时j为“坑”；接着从i开始，i++，找>=k的，令arr[j] = arr[i]，即将i元素“挖掉”，填到j，此时i为“坑”。
3.重复上面步骤直到i==j，这时k左边的元素（m）都比k小，k右边的元素（n）都比k大
4.令arr[i] = k，将arr[i]的“坑”填住。
5.将m，n分为两个数据集，再进行1~3操作，直到m，n中只有一个元素，排序结束。

void quick(int i,int j,int[] arr){
    if (i < j) {
    int l = i;//前
    int r = j;//后
    int k = arr[i];//把初始的元素提取出来，产生了一个“坑”
    //这里的j>i是为了控制循环结束------只要j==i，一轮循环就会结束
    while (j > i) {
        //j > l保证j不会向右越界，arr[j] > k是为了从后向前寻找比k小的元素
        while (arr[j] >= k&& j > i) {
            j--;
        }
        //一旦有比k小的元素，就将他存到k上次挖出的“坑”里面，此时在arr[j]里面生成一个“坑”
        arr[i] = arr[j];
        //i < r保证i不会向左越界，arr[i] < k是为了从前向后寻找比k大的元素
        while (arr[i] < k&&j > i) {
            i++;
        }
        //用刚刚发现的比k大的元素填到之前在k的后面挖出的“坑”里面，此时在k的前面arr[i]处挖出一个“坑”
        arr[j] = arr[i];
    }
    //将刚才的“坑”填上，至此，一轮循环结束，以k分隔了所有大于/小于他的元素
    arr[i] = k;
    //进行下一轮遍历
    quick(l,i -1,arr);
    quick(i + 1, r, arr);
    }
}