快速排序

python版本

  1. def partition(arr, low, high):
  2.     left = low  # 最小元素索引
  3.     pivot = arr[high]
  5.     for j in range(low, high):
  6.         # 当前元素小于或等于 pivot
  7.         if arr[j] <= pivot:
  8.             arr[left], arr[j] = arr[j], arr[left]
  9.             left += 1
  11.     arr[left], arr[high] = arr[high], arr[left]
  12.     return left
  15. # arr[] --> 排序数组
  16. # low  --> 起始索引
  17. # high  --> 结束索引
  19. # 快速排序函数
  20. def quickSort(arr, low, high):
  21.     if low < high:
  22.         pi = partition(arr, low, high)
  24.         quickSort(arr, low, pi - 1)
  25.         quickSort(arr, pi + 1, high)
  28. arr = [10, 7, 8, 9, 1, 5]
  29. quickSort(arr, 0, len(arr) - 1)
  30. print(arr)

java版

  1. /**
  2.  * @Description
  3.  * 快速排序  参考视频：https://www.bilibili.com/video/av39519566/
  4.  * @Author 田云
  5.  * @Date 2019/6/10 11:14
  6.  * @Version 1.0
  7.  */
  8. public class QuickSort {
  9.     public static void main(String[] args) {
  10.         int[] array = {2, 4, 6, 8, 5, 4, 6, 2, 6};
  11.         quickSort(array, 0, array.length - 1);
  12.         for (int i : array) {
  13.             System.out.println(i);
  14.         }
  15.     }
  17.     public static void quickSort(int[] array, int left, int right) {
  18.         if (left >= right) {
  19.             return;
  20.         }
  21.         int base = array[left];
  22.         int i = left;
  23.         int j = right;
  24.         while (i != j) {
  25.             while (array[j] >= base && i < j) {
  26.                 j--;
  27.             }
  28.             while (array[i] <= base && i < j){
  29.                 i++;
  30.             }
  31.             /**
  32.              * 交换
  33.              */
  34.             int tmp = array[i];
  35.             array[i] = array[j];
  36.             array[j] = tmp;
  37.         }
  38.         array[left] = array[i];
  39.         array[i] = base;
  41.         quickSort(array, left, i - 1);
  42.         quickSort(array, i + 1, right);
  44.     }
  45. }