快速排序java实现

快速排序

public static void quikSort(int[] arr, int lo, int hi) { if (lo >= hi){ return; } int j = partition(arr, lo, hi); quikSort(arr, lo, j - 1); quikSort(arr, j+1, hi); } private static int partition(int[] arr, int lo, int hi) { int i = lo, j = hi + 1; int v = arr[lo]; while (true) { while (arr[++i] <= v){ if (i == hi) break; } while (arr[--j] >= v){ if (j == lo) break; } if (i >= j) break; swap(arr, i, j); } swap(arr, lo, j); return j; } static void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }

三路快排

public static void sort(Comparable[] a, int lo, int hi){ if (lo >= hi) return; int lt = lo, i = lo + 1, gt = hi; Comparable v = a[lo]; while (i <= gt) { int cmp = a[i].compareTo(v); if (cmp < 0) swap(a, i++, lt++); else if(cmp > 0) swap(a, i, gt--); else i++; } sort(a, lo, lt - 1); sort(a, gt + 1, hi); } private static void swap(Comparable[] a, int i, int j){ Comparable temp = a[i]; a[i] = a[j]; a[j] = temp; }