quick sort

快速排序使用分治法（divide and conquer）策略来把一个序列（list）分为较小和较大的两个子序列，然后递归地排序两个子序列。

基本思想：在序列中找一个划分值，作为“基准”（pivot），通过一趟排序将未排序的序列排序成独立地两个部分，其中左边部分序列都比划分值小，右边部分的序列比划分值大，此时划分值的位置已经确定，然后再对这两个序列按照同样的方法进行排序，从而达到整个序列都有序的目的。

步骤：

• 挑选基准值：从数列中挑出一个元素，称为“基准”。

• 分割：重新排序数列。

• 递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。

递归到最底部的判断条件是序列的大小是0或1，此时该数列显然已经有序。

选取基准值有多种具体方法，不同选取方法对排序时间性能有决定性影响。

当数据有序时，以第一个关键字为基准分为两个子序列，前一个子序列为空，此时执行效率最差。

当数据随机分布时，以第一个关键字为基准分为两个子序列，两个子序列的元素个数接近相等，此时执行效率最好。

算法分析：

• 稳定性：快排是一种不稳定排序，比如基准值得前后都存在于基准值相同的元素，那么相同值就会被放在一边，这样就打乱了之前的相对排序。

• 比较性：因为排序时元素之间需要比较，所以是比较排序。

• 归并排序与快排 ：归并排序与快排两种排序思想都是分而治之，但是它们分解和合并的策略不一样：归并是从中间直接将数列分成两个，而快排是比较后将小的放左边大的放右边，所以在合并的时候归并排序还是需要将两个数列重新再次排序，而快排则是直接合并不再需要排序，所以快排比归并排序更高效一些，可以从示意图中比较二者之间的区别。

• 快速排序有一个缺点就是对于小规模的数据集性能不是很好。

时间复杂度	空间复杂度
​	​，因为排序需要另外申请空间，而且随着数列规模增大而增大

def Partition(arr,low,high):
   i = (low - 1) #最小元素索引
   pivot = arr[high]
   for j in range(low,high):
       #当前元素小于或等于pivot
       if arr[j] <= pivot:
           i += 1
           arr[i],arr[j] = arr[j],arr[i]
   arr[i+1],arr[high] = arr[high],arr[i+1]
   return i+1

# arr[] --> 排序数组
# low --> 起始索引
# high --> 结束索引

def QuickSort(arr,low,high):
   if low < high:
       pi = Partition(arr,low,high)
       
       QuickSort(arr, low, pi-1)
       QuickSort(arr, pi+1, high)

arr = [10, 7, 8, 9, 1, 5] 
n = len(arr) 
QuickSort(arr,0,n-1) 
print ("排序后的数组:") 
for i in range(n): 
   print ("%d" %arr[i])