快速排序
這里我們直接開始講相對的最優解 帶亂數的三路快排 好了，中間還有很多版本的快排，但是都有一些問題導致在某種極端情況下造成耗費時間極多，
-
基礎快排：在序列本身有序的情況下復雜度為O（n2）
-
帶亂數的快排：在序列本身有序的情況下復雜度為O（nlogn），但是在序列全部元素相同情況下復雜度為O（n2）
-
帶亂數的雙路快排：比前者更快一些為O（n），因為前后同時向中間遍歷，但是在序列全部元素相同情況下的復雜度問題仍舊未解決
-
帶亂數的三路快排： 解決上述各種問題且時間復雜度最快O（n）
作業原理：
將陣列分為三個部分，小于V的，等于V的，大于V的，
-
首先在陣列中選取任意一個下標和最左邊的下標互換（選取一個隨機下標的目的是，將快排結果最后V左邊或右邊沒有東西的極端情況概率降到最小甚至約等于0，如果出現這種情況將會導致復雜度為n2，這里我們不再深入討論）
-
確定需要的變數：因此我們要有2個下標 Lt，Rt 將陣列分割成3部分，還需要一個下標 i 指向當前的元素 e ，除此之外，用 l 和 r 確定陣列的首尾，
-
分配當前元素 e 去哪個區域 這里我們又分為3種情況：
-
e < V 將e和Lt+1處(也就是 ==V 的第一個元素)的位置交換，然后Lt++
-
e == V 將e直接納入該區域（也就是不做處理）然后 i++ 即可
-
e > V 將e和Rt - 1處(也就是 >V 的前一個元素)的位置交換，然后Rt--
無論是哪個情況，無非就是將其和Lt和Rt附近的元素交換位置即可，
-
-
那么當全部都排序完畢時，也就是滑鼠指的那個點處，i 和 Rt 重合時，退出回圈
-
因為按順序應該是 小于V ，V，==V，>V ，所以只要將V和 <V 處的最后一個元素交換位置即可
6.最后反復遞回呼叫 <V 區間以及 >V 的區間，從而讓兩邊的區間也都有序，
實作一下吧：
package com.sort;
import java.util.Random;
?
/**
* @Author: 翰林猿
* @Description: 三路快排
**/
public class Quick {
public Quick() {
}
?
public static <T extends Comparable<T>> void quicksort(T[] arr) {
Random random = new Random();
quicksort3ways(arr, 0, arr.length - 1, random);
}
?
private static <T extends Comparable<T>> void quicksort3ways(T[] arr, int l, int r, Random random) {
if (l >= r)
return;
int randomInt = random.nextInt(r + 1 - l); //生成一個不超過陣列長度的亂數
swap(arr, randomInt, l); //把他和首元素交換位置
//定義需要的變數
int Lt = l;
int Rt = r + 1;
int i = Lt + 1;
while (i < Rt) {
if (arr[i].compareTo(arr[l]) < 0) {
Lt++; //因為應該交換Lt+1處，所以可以直接先++再交換
swap(arr, Lt, i);
i++;
} else if (arr[i].compareTo(arr[l]) == 0) {
i++;
} else if (arr[i].compareTo(arr[l]) > 0) {
Rt--; //因為應該交換Rt-1處，所以可以直接先--再交換
swap(arr, Rt , i);
i++;
}
}
swap(arr,l,Lt); //將V擺到小于V和等于V中間
quicksort3ways(arr,l,Lt-1,random); //反復遞回呼叫 <V 區間以及 >V 的區間，讓這兩區間也都有序
quicksort3ways(arr,Rt,r,random);
}
?
public static <E> void swap(E[] arr, int j, int beforej) {
E t = arr[j];
arr[j] = arr[beforej];
arr[beforej] = t;
}
}
?
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/553385.html
標籤：其他
上一篇：3種分頁串列快取方式，速收藏~
下一篇：返回列表