溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了java數據結構與算法之快速排序。分享給大家供大家參考，具體如下：
交換類排序的另一個方法，即快速排序。
快速排序：改變了冒泡排序中一次交換僅能消除一個逆序的局限性，是冒泡排序的一種改進；實現了一次交換可消除多個逆序。通過一趟排序將要排序的數據分割成獨立的兩部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數據變成有序序列。
步驟:
1、從數列中挑出一個元素，稱為 "基準"（pivot）；
2、重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區退出之后，該基準就處于數列的中間位置。這個稱為分區（partition）操作。
3、遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。
算法實現代碼如下：
package exp_sort;
public class QuickSort {
public static void Qsort(int array[], int left, int right) {
int pos;
if (left < right) {
pos = quickSort(array, left, right);
//遞歸排序
Qsort(array, left, pos - 1);
Qsort(array, pos + 1, right);
}
}
/**
* 一趟快速排序
*
* @param array
* @param left
* @param right
* @return
*/
public static int quickSort(int array[], int left, int right) {
int low, high;
int temp = array[left]; // 選擇基準記錄（樞紐元）
low = left;
high = right;
while (low < high) {
// high從右到左找小于temp的記錄
while (low < high && array[high] >= temp) {
high--;
}
// 找到小于temp的記錄則交換
if (low < high) {
array[low] = array[high];
low++;
}
// low從左到右找到大于temp的記錄
while (low < high && array[low] < temp) {
low++;
}
// 找到大于temp的記錄，則交換
if (low < high) {
array[high] = array[low];
high--;
}
}
//將游標放在當前位置，此時low=high
array[low] = temp;
return low;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
int array[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
Qsort(array, 0, 7);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
System.out.println("\n");
}
}
樞紐元的選取：
1、基本的快速排序：選取地一個元素作為樞紐元。實際中應盡量避免將第一個元素作為樞紐元（極端情況是：初始狀態是已排好序或者反序的）。
2、隨機化快排序 : 隨機的選取樞紐元。
3、平衡快排 : 三數中值分割法：樞紐元的最好選擇是數組中的中值，該中值，即左端、右端和中心位置上的三個元素的中值（推薦）。
算法分析：該算法是在實踐中最快的一種排序算法，它的平均運行時間是O(N log N)，該算法之所以快，主要是由于非常精煉和高度優化的內部循環。它的最壞情況的性能是O(N^2)，但是這種情況可以改變。快速排序是一種分治的遞歸算法。該算法比歸并排序算法排序快。
1、最壞情況的分析
當樞紐元是最小元素時，此時就相當于是對整個數組進行遞歸排序，時間復雜度為：O(N^2)
2、最好情況的分析
樞紐元正好位于中間，此時是對兩個子數組進行遞歸排序，時間復雜度是：O(N log N)，這和歸并排序的分析完全相同。
3、平均情況的分析
時間復雜度是：O( N log N)
更多關于java算法相關內容感興趣的讀者可查看本站專題：《Java數據結構與算法教程》、《Java操作DOM節點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
