快排python手写
排序
http://www.nowcoder.com/questionTerminal/2baf799ea0594abd974d37139de27896
1:首先取序列第一个元素为基准元素pivot=R[low]。i=low,j=high。 2:从后向前扫描,找小于等于pivot的数,如果找到,R[i]与R[j]交换,i++。 3:从前往后扫描,找大于pivot的数,如果找到,R[i]与R[j]交换,j--。 4:重复2~3,直到i=j,返回该位置mid=i,该位置正好为pivot元素。 完成一趟排序后,以mid为界,将序列分为两部分,左序列都比pivot小,有序列都比pivot大,然后再分别对这两个子序列进行快速排序。
以序列(30,24,5,58,18,36,12,42,39)为例,进行演示
演示原文地址
# # 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 # 将给定数组排序 # @param arr int整型一维数组 待排序的数组 # @return int整型一维数组 # class Solution: def MySort(self , arr ): # write code here return self.QuickSort(arr,0,len(arr)-1) def QuickSort(self,arr,i,j): if i>=j: return arr point=arr[i] low=i high=j while i<j: while i<j and point<=arr[j]: j-=1 arr[i]=arr[j] while i<j and arr[i]<=point: i+=1 arr[j]=arr[i] arr[j]=point self.QuickSort(arr, low,i-1) self.QuickSort(arr, i+1, high) return arr