疾速排序的道理及java代碼完成。本站提示廣大學習愛好者：（疾速排序的道理及java代碼完成）文章只能為提供參考，不一定能成為您想要的結果。以下是疾速排序的道理及java代碼完成正文
概述
疾速排序是由東尼·霍爾所成長的一種排序算法。在均勻狀態下，排序 n 個項目要Ο(nlogn)次比擬。現實上，疾速排序平日顯著比其他Ο(nlogn) 算法更快，由於它的外部輪回（inner loop）可以在年夜部門的架構上很有用率地被完成出來，而且在年夜部門真實世界的數據，可以決議設計的選擇，削減所需時光的二次方項之能夠性。
疾速排序，經由過程一趟排序將待排記載朋分成自力的兩部門，個中一部門記載的症結字均比另外一部門的症結字小，然後分離對這兩部門記載持續停止排序,以到達全部序列有序的目標。
抽象圖示：
步調
選擇一個基准元素，平日選擇第一個元素或許最初一個元素
經由過程一趟排序將待排序的記載朋分成自力的兩部門，個中一部門記載的元素值均比基准元素值小。另外一部門記載的元素值均比基准值年夜
此時基准元素在其排好序後的准確地位
然後分離對這兩部門記載用異樣的辦法持續停止排序，直到全部序列有序。
實例
原始數據：
3 5 2 6 2
選擇 3 作為基准
第一輪
從右往左找比3小的，2相符，將2和3對換 2 5 2 6 3 對換一次，查找的偏向反向，從左向右找比3年夜的，5相符，對換 2 3 2 6 5 再從右往左找比3小的，2相符，對換 2 2 3 6 5 一輪停止
第二輪
對 [2 2] 采取同上的方法停止，獲得 2 2 3 6 5
第三輪
對 [6 5] 采取同上的方法停止，獲得 2 2 3 5 6
終究成果
2 2 3 5 6
代碼完成(Java)
package com.coder4j.main.arithmetic.sorting;
public class Quick {
private static int mark = 0;
/**
* 幫助交流辦法
*
* @param array
* @param a
* @param b
*/
private static void swap(int[] array, int a, int b) {
if (a != b) {
int temp = array[a];
array[a] = array[b];
array[b] = temp;
// 找到相符的，對換
System.out.println("對換" + array[a] + "與" + array[b] + ",獲得");
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
}
}
/**
* 新一輪分隔
*
* @param array
* @param low
* @param high
* @return
*/
private static int partition(int array[], int low, int high) {
int base = array[low];
mark++;
System.out.println("正在停止第" + mark + "輪分隔，區域：" + low + "-" + high);
while (low < high) {
while (low < high && array[high] >= base) {
high--;
System.out.println("從右往左找比" + base + "小的，指針更改：" + low + "-" + high);
}
swap(array, low, high);
while (low < high && array[low] <= base) {
low++;
System.out.println("從左往右找比" + base + "年夜的，指針更改：" + low + "-" + high);
}
swap(array, low, high);
}
return low;
}
/**
* 對數組停止疾速排序，遞歸挪用
*
* @param array
* @param low
* @param heigh
* @return
*/
private static int[] quickSort(int[] array, int low, int heigh) {
if (low < heigh) {
int division = partition(array, low, heigh);
quickSort(array, low, division - 1);
quickSort(array, division + 1, heigh);
}
return array;
}
/**
* 快排序
*
* @param array
* @return
*/
public static int[] sort(int[] array) {
return quickSort(array, 0, array.length - 1);
}
public static void main(String[] args) {
int[] array = { 3, 5, 2, 6, 2 };
int[] sorted = sort(array);
System.out.println("終究成果");
for (int i : sorted) {
System.out.print(i + " ");
}
}
}
測試輸入成果：
全選復制放進筆記正在停止第1輪分隔，區域：0-4 對換2與3,獲得 2 5 2 6 3 從左往右找比3年夜的，指針更改：1-4 對換3與5,獲得 2 3 2 6 5 從右往左找比3小的，指針更改：1-3 從右往左找比3小的，指針更改：1-2 對換2與3,獲得 2 2 3 6 5 從左往右找比3年夜的，指針更改：2-2 正在停止第2輪分隔，區域：0-1 從右往左找比2小的，指針更改：0-0 正在停止第3輪分隔，區域：3-4 對換5與6,獲得 2 2 3 5 6 從左往右找比6年夜的，指針更改：4-4 終究成果 2 2 3 5 6
經測試，與實例中成果分歧。
