排序算法-快速排序

Quick Sort

时间复杂度O(nlogn)

最好情况O(nlogn)

最坏情况O(n**2) 按照冒泡的方法，数组完全倒序

空间复杂度O(logn)

In-place

快速排序是基于比较交换的排序，首先设定一个基准值，一般为数组第一项，设置两个指针分别指向数组开头和末尾，末尾指针首先向前搜索第一个小于基准值的数，将其和基准值交换位置，然后开头指针加一；这时候开头指针向后寻找第一个小于基准值的数，将其和基准值交换位置，然后末尾指针加一。

循环以上过程直到两个指针位置相同，停止。

此时基准值已经在中间位置，其左面为比他小的值，右面为比他大的值；将数组分为左右两部分递归调用上面的方法。

Java：

public class QuickSort {
    public static void QuickSort(int[] arr,int begin, int end){
        if (begin arr[i]) {
                    i++;
                }
                if (i < j) {
                    tem = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tem;
                    j--;
                }
                QuickSort(arr, begin, i - 1);
                QuickSort(arr, j + 1, end);
            }
        }
    }
}

 Python：

def QuickSort(num_list,begin,end):
    if(beginnum_list[i]:
                i += 1
            if i