資訊專欄INFORMATION COLUMN
摘要：快速排序，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，然后分別對這兩部分記錄繼續(xù)進行排序以達到整個序列有序的目的。
概述
快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(nlogn)次比較。事實上，快速排序通常明顯比其他Ο(nlogn) 算法更快，因為它的內(nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實現(xiàn)出來，并且在大部分真實世界的數(shù)據(jù)，可以決定設(shè)計的選擇，減少所需時間的二次方項之可能性。
快速排序，通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分的關(guān)鍵字小，然后分別對這兩部分記錄繼續(xù)進行排序,以達到整個序列有序的目的。
形象圖示：
步驟選擇一個基準元素，通常選擇第一個元素或者最后一個元素
通過一趟排序?qū)⒋判虻挠涗浄指畛瑟毩⒌膬刹糠?，其中一部分記錄的元素值均比基準元素值小。另一部分記錄的元素值均比基準值?/p>
此時基準元素在其排好序后的正確位置
然后分別對這兩部分記錄用同樣的方法繼續(xù)進行排序，直到整個序列有序。
實例原始數(shù)據(jù)：
3 5 2 6 2
選擇 3 作為基準
第一輪
從右往左找比3小的，2符合，將2和3對調(diào) 2 5 2 6 3 對調(diào)一次，查找的方向反向，從左向右找比3大的，5符合，對調(diào) 2 3 2 6 5 再從右往左找比3小的，2符合，對調(diào) 2 2 3 6 5 一輪結(jié)束
第二輪
對 [2 2] 采用同上的方式進行，得到 2 2 3 6 5
第三輪
對 [6 5] 采用同上的方式進行，得到 2 2 3 5 6
最終結(jié)果
2 2 3 5 6代碼實現(xiàn)(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;
// 找到符合的，對調(diào)
System.out.println("對調(diào)" + 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 + "輪分隔，區(qū)域：" + 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;
}
/**
* 對數(shù)組進行快速排序，遞歸調(diào)用
*
* @param array
* @param low
* @param heigh
* @return
*/
private static int[] quickSort(int[] array, int low, int high) {
if (low < high) {
int division = partition(array, low, high);
quickSort(array, low, division - 1);
quickSort(array, division + 1, high);
}
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("最終結(jié)果");
for (int i : sorted) {
System.out.print(i + " ");
}
}
}
測試輸出結(jié)果：
正在進行第1輪分隔，區(qū)域：0-4 對調(diào)2與3,得到 2 5 2 6 3 從左往右找比3大的，指針變動：1-4 對調(diào)3與5,得到 2 3 2 6 5 從右往左找比3小的，指針變動：1-3 從右往左找比3小的，指針變動：1-2 對調(diào)2與3,得到 2 2 3 6 5 從左往右找比3大的，指針變動：2-2 正在進行第2輪分隔，區(qū)域：0-1 從右往左找比2小的，指針變動：0-0 正在進行第3輪分隔，區(qū)域：3-4 對調(diào)5與6,得到 2 2 3 5 6 從左往右找比6大的，指針變動：4-4 最終結(jié)果 2 2 3 5 6
經(jīng)測試，與實例中結(jié)果一致。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/65414.html
摘要：今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法快速排序法平均時間復雜度為?？焖倥判蚍ǖ脑砜焖倥判蚴且环N劃分交換排序，它采用分治的策略，通常稱其為分治法。 HTML5學堂-碼匠：前幾期算法之旅跟大家分享了冒泡排序法和選擇排序法，它們都屬于時間復雜度為O(n^2)的慢排序。今天跟大家分享多種排序算法里使用較廣泛，速度快的排序算法—— 快速排序法 [ 平均時間復雜度為O (n l...
摘要：實現(xiàn)快速排序介紹通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列。 冒泡排序 介紹 重復遍歷要排序的元素列，依次比較兩個相鄰的元素，前一個元素若比后一個元素大則互換位置。以升序排序為例，最大的元素會在第一次遍歷后冒泡到數(shù)組的末端。假如數(shù)組...
標準庫中的sort函數(shù)，是快速排序算法的典型實現(xiàn)。算法將含有n個元素的序列排序，平均需要 O(n log n) 時間。 上周，我提出了測試一個程序的性能比測試其功能更難這個觀點。確認程序的性能達到標準以及確定標準的含義都十分困難。 接下來，我會繼續(xù)討論標準庫中的sort(排序)函數(shù)。sort函數(shù)實現(xiàn)了快速排序算法，快速排序算法平均可以在 O(n log n) 時間內(nèi)對含有n個元素的序列進行排序...
閱讀 2084·2021-11-16 11:45
閱讀 582·2021-11-04 16:12
閱讀 1386·2021-10-08 10:22
閱讀 861·2021-09-23 11:52
閱讀 4146·2021-09-22 15:47
閱讀 3523·2021-09-22 15:07
閱讀 494·2021-09-03 10:28
閱讀 1742·2021-09-02 15:21
