Algorithm - Quick Sort（Java）

ゝ一世哀愁。 2022-05-24 07:58 145阅读 0赞

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击[http://www.captainbed.net][http_www.captainbed.net]

package peace.learn.java.algorithm.sort;
 
 import java.util.Arrays;
 
 /**
 * @author Peace
 * 
 * Basic Thought:
 * 
 * Quick Sort:
 * Separate the data to two independent parts by one round of sorting,
 * 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 data becomes sorted sequence.
 * 
 * One Trip Quick Sort:
 * Assume the array is a[0]...a[n-1],
 * first arbitrarily select one element as pivot
 * (usually set the first element as pivot),
 * 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 of Quick Sort.
 * 
 * 
 * Algorithm:
 * 
 * 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 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
 */
 private 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("Pivot: %2d, Pivot Value: %2d, Array: %s%n", pivot, a[pivot], Arrays.toString(a));
 
 // Sort the left part of pivot
 quickSort(a, low, pivot - 1);
 
 // Sort the right part of pivot
 quickSort(a, pivot + 1, high);
 }
 
 /**
 * One trip of 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;
 
 // 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;
 }
 
 /**
 * Test program
 *
 * @param args The arguments
 */
 public static void main(String[] args) {
 int[] a = {11, 16, 22, -3, 99, 0, 16, 6, -1, 99};
 
 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));
 }
 
 }
 
 /* ------ Running Result ------
 Before quick sort:
 [11, 16, 22, -3, 99, 0, 16, 6, -1, 99]
 In quick sort:
 Pivot: 4, Pivot Value: 11, Array: [-1, 6, 0, -3, 11, 99, 16, 22, 16, 99]
 Pivot: 1, Pivot Value: -1, Array: [-3, -1, 0, 6, 11, 99, 16, 22, 16, 99]
 Pivot: 2, Pivot Value: 0, Array: [-3, -1, 0, 6, 11, 99, 16, 22, 16, 99]
 Pivot: 8, Pivot Value: 99, Array: [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 Pivot: 5, Pivot Value: 16, Array: [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 Pivot: 6, Pivot Value: 16, Array: [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 After quick sort:
 [-3, -1, 0, 6, 11, 16, 16, 22, 99, 99]
 */

[http_www.captainbed.net]: http://www.captainbed.net/troubleshooter