快速排序

  1. class Solution:
  2.     # @param {int[]} A an integer array
  3.     # @return nothing
  4.     def sortIntegers2(self, A):
  5.         # Write your code here
  6.         self.quickSort(A, 0, len(A) - 1)
  8.     def quickSort(self, A, start, end):
  9.         if start >= end:
  10.             return
  12.         left, right = start, end
  13.         # key point 1: pivot is the value, not the index
  14.         pivot = A[(start + end) // 2]
  16.         # key point 2: every time you compare left & right, it should be 
  17.         # left <= right not left < right
  18.         while left <= right:
  19.             while left <= right and A[left] < pivot:
  20.                 left += 1
  21.             while left <= right and A[right] > pivot:
  22.                 right -= 1
  23.             if left <= right:
  24.                 A[left], A[right] = A[right], A[left]
  25.                 left += 1
  26.                 right -= 1
  28.         self.quickSort(A, start, right)
  29.         self.quickSort(A, left, end)