image.png

    1. def partition(arr,low,high): 
    2.     # 左端
    3.     i = low - 1    
    4.     # 以最右端为基准元素
    5.     pivot = arr[high]     
    6.       # 遍历
    7.     for j in range(low , high): 
    8.         # 当前元素小于或等于 pivot 
    9.         if  arr[j] <= pivot:
    10.             # 左往前
    11.             i += 1
    12.             # 左右互换
    13.             arr[i], arr[j] = arr[j], arr[i] 
    14.     # 最后左端指向元素和pivot互换
    15.     arr[i + 1], arr[high] = arr[high],arr[ i + 1] 
    16.     # 返回新的划分点位置
    17.     return i + 1 
    19. # 快速排序函数
    20. def quickSort(arr, low, high): 
    22.     if low < high: 
    23.         pi = partition(arr,low,high) 
    24.         quickSort(arr, low, pi-1) 
    25.         quickSort(arr, pi+1, high)
    28. if __name__ == "__main__":
    29.     nums = [5, 2, 9, 7, 6, 12, 3, 4]
    30.     low, high = 0, len(nums) - 1
    31.     quickSort(nums, low, high)
    32.     print(nums)
    1. import java.util.Arrays;
    3. /**
    4.  * @Author dyliang
    5.  * @Date 2020/10/2 15:35
    6.  * @Version 1.0
    7.  */
    8. public class Sort {
    9.     private static int[] arr = {3,5,1,6,2,9};
    11.     public static void main(String[] args) {
    12.         quickSort(arr, 0, arr.length - 1);
    13.         System.out.println(Arrays.toString(arr));
    14.     }
    16.     private static void quickSort(int[] arr, int left, int right) {
    17.         if (left < right) {
    18.             int pivot = partition(arr, left, right);        // 将数组分为两部分
    19.             quickSort(arr, left, pivot - 1);                   // 递归排序左子数组
    20.             quickSort(arr, pivot + 1, right);                  // 递归排序右子数组
    21.         }
    22.     }
    24.     private static int partition(int[] arr, int left, int right) {
    25.         int pivot = arr[left];               // 枢轴记录
    26.         while(left < right) {
    27.             while (left < right && arr[right] >= pivot) --right;
    28.             arr[left] = arr[right];           // 交换比枢轴小的记录到左端
    29.             while (left < right && arr[left] <= pivot) ++left;
    30.             arr[right] = arr[left];           // 交换比枢轴小的记录到右端
    31.         }
    32.         // 扫描完成，枢轴到位
    33.         arr[left] = pivot;
    34.         // 返回的是枢轴的位置
    35.         return left;
    36.     }
    37. }

    一次partition的过程如下所示：
    image.png