private static void quickSort(Integer[] toSortArray, int low, int high) {if (low >= high)return;int k = partition(toSortArray, low, high);quickSort(toSortArray, low, k - 1);quickSort(toSortArray, k + 1, high);}/**
* given a number index low, it partitions array* such that all numbers less than numbers[]low] are left* and greater are right* @param numbers* @param low* @param high* @return*/private static int partition(Integer[] numbers, int low, int high) {int leftIndex = low;int rightIndex = high + 1;while (true) {//find left index to swapwhile (numbers[++leftIndex] < numbers[low]) {if (leftIndex == high) {break;}}//find right index to swapwhile (numbers[low] < numbers[--rightIndex]) {if (rightIndex == low) {break;}}// pointers crossif (leftIndex >= rightIndex)break;//swapswap(leftIndex, rightIndex, numbers);}swap(low, rightIndex, numbers);return rightIndex;}private static void printArray(Integer[] toSortArray) {for (int i = 0; i < toSortArray.length; i++) {System.out.print(toSortArray[i] + " ");}System.out.println(" ");}/**
* swap 2 numbers at the index** @param minIndex* @param index* @param numbers*/private static void swap(int minIndex, int index, Integer[] numbers) {Integer temp = numbers[minIndex];numbers[minIndex] = numbers[index];numbers[index] = temp;}
Labels
Quick Sort in Java
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment