Algorithm - Quick Sort（Java）

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.Algorithm.Sort; import java.util.Arrays; /** * @author LiveEveryDay * * Basic Thought: * * Quick Sort: * Split the sequence into two independent parts by One Trip Quick Sort, * of which one part data is smaller than the other. * And then perform Quick Sort separately on the two parts, * the whole process can be recursive, * hereby the whole sequence becomes sorted sequence. * * One Trip Quick Sort: * Assume the array is a[0]...a[n-1], * adjust the array pivot to the middle value of three: a[low], a[(low+high)/2], a[high]; * and swap the pivot to the first element. * then put all the elements smaller than the pivot before the pivot, * put all the elements bigger than the pivot after the pivot, * this process is called One Trip Quick Sort. * * Algorithm: * * Quick Sort algorithm is designed as following: * 1. Set two variable low and high, if low >= high, terminate recursive process. * 2. Perform One Trip Quick Sort and get pivot. * 3. Quick Sort the left part of pivot recursively. * 4. Quick Sort the right part of pivot recursively. * * One Trip Quick Sort algorithm is designed as following: * 1. Set two variable i and j, i = 0, j = n - 1. * 2. Set the first element as pivot, i.e. pivot = a[i]. * 3. Search forward from j (j--), * find the first element that a[j] < pivot, * assign a[j] to a[i]. * 4. Search backward from i (i++), * find the first element that a[i] > pivot, * assign a[i] to a[j]. * 5. Repeat step3 and step4 until i == j. * Then, a[i] = pivot, return i. * * Complexity: * The average time complexity of Quick Sort is O(nlog2n). * * Stability: * Note that Quick Sort is not stable, * i.e. the relative positions of equal elements may be changed after Quick Sort. */ public class QuickSort { /** * Quick Sort * * @param a The array to be sorted * @param low The start position of sorting * @param high The end position of sorting */ public static void quickSort(int[] a, int low, int high) { if (a == null || a.length == 0) { return; } if (low >= high) { return; } int pivot = oneTripQuickSort(a, low, high); // Print each trip of sorting System.out.printf("Array: %s, pivot position: %2d, pivot value: %2d%n", Arrays.toString(a), pivot, a[pivot]); // Sort the left part of pivot quickSort(a, low, pivot - 1); // Sort the right part of pivot quickSort(a, pivot + 1, high); } /** * One Trip Quick Sort * * @param a The array to be sorted * @param low The start position of sorting * @param high The end position of sorting * @return The pivot position */ private static int oneTripQuickSort(int[] a, int low, int high) { int i = low; int j = high; // Adjust pivot in array adjustPivot(a, i, j); System.out.printf("Adjust pivot of array: %s%n", Arrays.toString(a)); // Set the first element as pivot int pivot = a[i]; while (i < j) { // From right to left, find the first element that less than pivot. while (i < j && a[j] >= pivot) { j--; } // Replace a[i] = a[j]; // From left to right, find the first element that greater than pivot. while (i < j && a[i] <= pivot) { i++; } // Replace a[j] = a[i]; } // Hereto, i must be equal to j, i (or j) is the pivot position. a[i] = pivot; // Return the pivot position return i; } /** * Adjust the array pivot to the middle value of three: a[low], a[(low+high)/2], a[high]; * and swap the pivot to the first element. * * @param a The array * @param low The low index * @param high The high index */ private static void adjustPivot(int[] a, int low, int high) { int mid = (low + high) >> 1; if ((a[mid] > a[low] && a[mid] < a[high]) || (a[mid] > a[high] && a[mid] < a[low])) { swap(a, low, mid); } if ((a[high] > a[mid] && a[high] < a[low]) || (a[high] > a[low] && a[high] < a[mid])) { swap(a, low, high); } } /** * Swap two elements in array * * @param a The array * @param i The element index i * @param j The element index j */ private static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } /** * Test program * * @param args The arguments */ public static void main(String[] args) { int[] a = {-11, 68, 22, -3, 99, 0, 16, 6, -1, 99, 101}; System.out.println("Before quick sort:"); System.out.println(Arrays.toString(a)); System.out.println("In quick sort:"); QuickSort.quickSort(a, 0, a.length - 1); System.out.println("After quick sort:"); System.out.println(Arrays.toString(a)); } } /* ------ Output ------ Before quick sort: [-11, 68, 22, -3, 99, 0, 16, 6, -1, 99, 101] In quick sort: Adjust pivot of array: [0, 68, 22, -3, 99, -11, 16, 6, -1, 99, 101] Array: [-1, -11, -3, 0, 99, 22, 16, 6, 68, 99, 101], pivot position: 3, pivot value: 0 Adjust pivot of array: [-3, -11, -1, 0, 99, 22, 16, 6, 68, 99, 101] Array: [-11, -3, -1, 0, 99, 22, 16, 6, 68, 99, 101], pivot position: 1, pivot value: -3 Adjust pivot of array: [-11, -3, -1, 0, 99, 22, 16, 6, 68, 99, 101] Array: [-11, -3, -1, 0, 68, 22, 16, 6, 99, 99, 101], pivot position: 8, pivot value: 99 Adjust pivot of array: [-11, -3, -1, 0, 22, 68, 16, 6, 99, 99, 101] Array: [-11, -3, -1, 0, 6, 16, 22, 68, 99, 99, 101], pivot position: 6, pivot value: 22 Adjust pivot of array: [-11, -3, -1, 0, 6, 16, 22, 68, 99, 99, 101] Array: [-11, -3, -1, 0, 6, 16, 22, 68, 99, 99, 101], pivot position: 4, pivot value: 6 Adjust pivot of array: [-11, -3, -1, 0, 6, 16, 22, 68, 99, 99, 101] Array: [-11, -3, -1, 0, 6, 16, 22, 68, 99, 99, 101], pivot position: 9, pivot value: 99 After quick sort: [-11, -3, -1, 0, 6, 16, 22, 68, 99, 99, 101] */