leetcode----快速排序

原理介紹

假設我們需要對數組Array=[2,5,1,3,7,6,4]進行排序。首先我們把數組第一個元素作為基準數。然後，我們從右向左分别與基準數比較，找到比基準數小的索引；再從左向右分别于基準數比較，找到比基準數大的索引。找到兩個索引後，對調兩索引的元素。舉例子，我們看Array，把左右兩邊數的索引分别設為i=1，j=len(Array)-1，從右往左與2作比較，發現1小于2，再從左往右，發現5大于2，是以對調兩數。

Array = [2,1,5,3,7,6,4]

此時i=1，j=2，繼續在此索引下重複上述操作，即從j=2往左找小于基準數的數，發現1小于2，但是此時i，j相交，說明在索引為1的位置上，數字2左邊的數均小于它，右邊的數都大于它。是以，我們就找到了2在Array中順序排序的索引位置。我們将Aarry[i=1]與2對調位置。

Array=[1,2,5,3,7,6,4]

此時，我們發現2把數組分成了左右兩邊。是以，我們對左右兩邊的數組繼續進行上述操作。

Array1 = [1]

Array1隻有一個元素，它不需要排序，是以，我們把數組個數為1作為結束标志。

Array2=[5,3,7,6,4]

把5作為基準數，從右往左比較，發現4小于5，從左往右，發現7大于5，是以對調i=2，j=4。

Array2=[5,3,4,6,7]

繼續從j=4往右比較，發現4小于5，此時，j=2與i=2相遇。是以，判斷5在索引為2的位置時，其左均小于5，右均大于5。調換i=2，與基準數的位置。

Array2 = [4,3,5,6,7]

因為隻有個數為1的數組，我們才認為有序。故，繼續把Array2分為兩個數組Array3=[4,3],Array4=[6,7]

Array3=[4,3]

基準數是4，從右往左發現3小于4，但是i與j相遇，是以，直接對調i=1與4的位置，得到Array3=[3,4]. 同樣Array4也是如此。

最後，我們獲得順序序列Array=[1,2,3,4,5,6,7]

代碼

class Solution:
    def randomized_partition(self, nums, l, r):
       i = l
       j = r
       temp = nums[l]
       while(i !=j):
           while(nums[j] >= temp and i<j):
               j = j - 1
           while(nums[i] <= temp and i<j):
               i = i + 1
           if(i < j):
               nums[i], nums[j] = nums[j], nums[i]
       nums[l], nums[i] = nums[i], nums[l]
       return i

    def randomized_quicksort(self, nums, l, r):
        if r - l <= 0:
            return
        mid = self.randomized_partition(nums, l, r)
        self.randomized_quicksort(nums, l, mid - 1)
        self.randomized_quicksort(nums, mid + 1, r)

    def sortArray(self, nums):
        self.randomized_quicksort(nums, 0, len(nums) - 1)
        return nums

a = [2,5,1,3,7,6,4]
b = Solution()
print(b.sortArray(a))