python| #排序#

• 解法：
  1. 选择左侧第一个值作为基准point
  2. 从右边开始，找到第一个小于point的索引right
  3. 从右边开始，找到第一个大于point的索引left
  4. 交换两者
  5. 重复1-3,知道left=right
  6. 交换point 和right的值
  7. 此时，right左侧的值都小于right，右侧的值都大于right，然后递归即可

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
    def MySort(self , arr ):
        # write code here
        # write code here
        return self.QuickSort(arr,0,len(arr)-1)

    def QuickSort(self,arr,left,right):
        '''
        快速排序
        '''
        if left>=right:
            return 
        point = arr[left]
        low = left
        high = right
        while(left < right):
            while left <right and point <= arr[right]:
                right -= 1
            while left < right and point >= arr[left]:
                left += 1
            self.swap(arr,left,right)
        self.swap(arr,low,right)
        self.QuickSort(arr, low, right-1)
        self.QuickSort(arr, right+1, high)
        return arr 
    def swap(self,arr,i,j):
        temp = arr[i]
        arr[i] = arr[j]
        arr[j] = temp