搜索与排序算法
的根基之一是数组。基于数组的排序算法有多种，如冒泡，插入排序，归并排序等。现在主要介绍快排，快排里面用到了分治思想，可以采用递归完成排序功能。
分治思想的核心是原始问题可以分解成独立子问题，子问题还可继续分解，直到问题的求解较容易实现。在数组排序中，分治的思想从空间角度分析，它分解原始问题的思路是把原数组分成两份，解决分出来的子数组排序问题后，原数组的排序问题可以递归解决。
假定我们得到一个无序的数组，如[2,1,3,4,9,......]。思考如何排序使它有序呢？无序数组变有序是我们的原始问题，用分治思想，可以将母问题进行分解吗？快排的思路是，从数组元素中选择一个中心数，使中心数左边的所有元素小于该中心数，中心数右边的所有元素大于该中心数。若我们选的中心数不是最小或最大的元素，原数组会被我们分成俩部分。这俩部分子数组排序问题变成我们的子问题。子数组的排序也可按照该分治思路进行分解，直到子数组元素个数为1和0。
快排的时间复杂度与空间复杂度分析还是要看代码实现思路。
快排为了实现原址排序，不用再额外开辟新的空间存储子数组，遍历数组时它会记录小于中心数的元素的下一索引（pivot_index），若遍历到小于中心数的元素，交换pivot_index指向的元素，pivot_index增1。
跟原数组的排序情况有关，如果原数组已经是有序的，则时间复杂度是O(n2);一般情况是O(nlogn)。
arr =[1,2,5,4,3,9,4,8,7] def partition(arr, start, end): pivot = arr[end] i = start for j in range(start, end): if arr[j] < pivot: temp = arr[i] arr[i] = arr[j] arr[j] = temp i += 1 temp1 = arr[i] arr[i] = pivot arr[end] = temp1 return i def sort(arr, start, end): if start >= end : return pivot_index = partition(arr,start,end) sort(arr,start,pivot_index-1) sort(arr,pivot_index+1,end) def quick_sort(arr): size = len(arr) sort(arr, 0, size-1) quick_sort(arr) print(arr)
