1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77
| import java.util.Arrays;
import static java.lang.System.out;
public class QuickSort {
public static int midIndex(int[] a, int i, int j) { int l = i, r = j; int x = a[i]; while (l < r) { while (l < r && a[r] >= x) r--; if (l < r) { a[l] = a[r]; l++; } while (l < r && a[l] <= x) l++; if (l < r) { a[r] = a[l]; r--; } } a[l] = x; return l; }
static void sort(int[] a, int l, int r) { if (l < r) { int midIndex = midIndex(a, l, r); sort(a, l, midIndex - 1); sort(a, midIndex + 1, r); } }
public static void quickSort(int[] a, final int left, final int right) { if (null != a && a.length > 0 && left >= 0 && right > left && right < a.length) { int i = left, j = right; int x = a[left]; while (i < j) { while (i < j && a[j] >= x) j--; if (i < j) { a[i++] = a[j]; } while (i < j && a[i] <= x) i++; if (i < j) { a[j--] = a[i]; } } a[i] = x; quickSort(a, left, i-1); quickSort(a, i+1, right); } }
public static void main(String[] args) { int[] a = {1, 2, 3, 7, 1, 6, 7, 8, 4, 3, 3, 9}; sort(a, 0, a.length - 1); Arrays.stream(a).forEach(out::print); System.out.println("\n=================="); int []b = {1, 2, 3, 7, 1, 6, 7, 8, 4, 3, 3, 9}; quickSort(b,0,b.length-1); Arrays.stream(b).forEach(out::print); } }
|