目錄
3.1 實現(xiàn)方式1：選取中間值作為基準(zhǔn)值
3.2 實現(xiàn)方式2：選取最右邊的值作為基準(zhǔn)值
快速排序是基于分治策略的一種排序
基本思想
1．基準(zhǔn)：先從數(shù)列中取出一個數(shù)作為基準(zhǔn)數(shù)。
2．分區(qū)過程：將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。
3．再對左右區(qū)間重復(fù)第一、二步，直到各區(qū)間只有一個數(shù)。
注意：快速排序在分的時候，就進行了“排序”處理
1.分解：將數(shù)組A[p..r]劃分為兩個（可能為空）子數(shù)組A[p...q-1]和A[q 1...r]，使得A[p...q-1]中的每一個元素都小于等于A[q]，而A[q]也小于等于A[q 1...r]中的每個元素
2.解決：通過遞歸調(diào)用快速排序，對子數(shù)組A[p...q-1]和A[q 1...r]進行排序
3.合并：因為子數(shù)組都是原址排序的，所以不需要合并操作：數(shù)組A[p...r]已經(jīng)有序
歸并排序?qū)?shù)組分成連個子數(shù)組分別排序，并將有序的子數(shù)組歸并以將整個數(shù)組排序；而快速排序是當(dāng)兩個子數(shù)組都有序時，整個數(shù)組也就自然有序了
歸并排序在分的時候不進行任何處理，而快速排序在分的時候，要進行元素交換，保正左邊元素小于基準(zhǔn)值，右邊元素大于基準(zhǔn)值
歸并排序遞歸調(diào)用發(fā)生在處理整個數(shù)組之前，快速排序遞歸調(diào)用發(fā)生在處理整個數(shù)組之后
歸并排序在合并的時候完成排序，快速排序在分的時候完成排序，合并時，什么都不做
在歸并排序中，一個數(shù)組被等分為兩半，在快速排序中，切分的位置取決于數(shù)組的內(nèi)容
關(guān)鍵詞解釋
pivot：基準(zhǔn)元素
partition：將整個數(shù)組進行切分
public class QuickSort extends Sort { /** * sort方法為外界提供了統(tǒng)一的調(diào)用“接口” * @param arr */ @Override public void sort(Comparable[] arr) { quickSort(arr,0,arr.length-1); } private void quickSort(Comparable[] arr,int left,int right){ if(left >= right){ return; } //經(jīng)過切分后基準(zhǔn)值最終索引 int pivot = partition(arr,left,right); //對pivot左邊進行遞歸切分 quickSort(arr,left,pivot-1); //對pivot右邊進行遞歸切分 quickSort(arr,pivot 1,right); } /** * 切分數(shù)組，切分為左邊小于pivot，右邊大于pivot * @param arr * @param left * @param right * @return 返回中間基準(zhǔn)值pivot的索引值 */ private int partition(Comparable[] arr,int left,int right){ //我們這里取中間值基準(zhǔn)值， Comparable pivot = arr[(left right)/2]; //定義兩個指針指向兩邊 int move_right = left; int move_left = right; /** * 當(dāng)兩個指針相等或向右移動的指針大于向左移動的指針的時候，代表遍歷完所有的元素 * * while循環(huán)的目的是讓比pivot小的元素在pivot的左邊，比pivot大的元素在右邊 */ while(move_right < move_left){ /** * 右移指針尋找大于等于pivot的值， * * * 最后的情況就是pivot左邊全部是小于pivot的，這時，找到的是pivot值 * 然后右邊找到的是非pivot的話，就發(fā)生交換，等于pivot的話，move_right不一定等于move_left * * 因為有可能有多個重復(fù)的與pivot本身相同的值，所以交換后，我們也要讓指針繼續(xù)移動， * 確保通過指針的相對大小判斷循環(huán)結(jié)束，否則，在交換后，不移動指針，可能會形成死循環(huán)（兩個指針同時指向兩個相鄰的pivot） * */ while(arr[move_right].compareTo(pivot) < 0){ //右移指針指向的值小于pivot的值，不用交換，指針繼續(xù)右移 move_right ; } /** * 左移指針尋找小于等于pivot的值 * * 同上，最后的情況就是找到pivot */ while (arr[move_left].compareTo(pivot) > 0){ //左移指針指向的值大于pivot的值，不用交換，指針繼續(xù)左移 move_left--; } //兩個指針遍歷完所有元素，結(jié)束循環(huán) if(move_right >= move_left) break; //交換兩個指針指向的值 swap(arr,move_right,move_left); /** * 迭代，讓指針移動 * * 指針指向的值為pivot的時候，讓另一個指針靠近自己，以最終結(jié)束循環(huán) */ //如果右移指針指向pivot，左移指針-- if(arr[move_right].compareTo(pivot) == 0){ move_left--; } //如果左移指針指向pivot，右移指針-- if(arr[move_left].compareTo(pivot) == 0){ move_right ; } } /** * 最終我們需要返回用于切分的基準(zhǔn)值的最終索引 * * 循環(huán)過后，兩個指針總有一個是指向pivot的，通過以下判斷，最終返回pivot的索引 */ int pivotIndex; if(arr[move_right] == pivot){ pivotIndex = move_right; }else{ pivotIndex = move_left; } return pivotIndex; }}import java.util.Arrays;public class SortTest { public static void main(String[] args) { Integer[] arr = new Integer[]{8,9,1,7,2,3,5,5,4,4,5,6,0}; System.out.println("未排序的數(shù)組為:"); System.out.println(Arrays.toString(arr)); QuickSort quickSort = new QuickSort(); quickSort.sort(arr); System.out.println("排序后的數(shù)組為:"); System.out.println(Arrays.toString(arr)); }}
public class QuickSort extends Sort { /** * sort方法為外界提供了統(tǒng)一的調(diào)用“接口” * * @param arr */ @Override public void sort(Comparable[] arr) { quickSort(arr, 0, arr.length - 1); } private void quickSort(Comparable[] arr, int left, int right) { if (left >= right) { return; } //經(jīng)過切分后基準(zhǔn)值最終索引 int pivot = partition(arr, left, right); //對pivot左邊進行遞歸切分 quickSort(arr, left, pivot - 1); //對pivot右邊進行遞歸切分 quickSort(arr, pivot 1, right); } /** * 切分數(shù)組，切分為左邊小于pivot，右邊大于pivot * * @param arr * @param left * @param right * @return 返回中間基準(zhǔn)值pivot的索引值 */ private int partition(Comparable[] arr, int left, int right) { //我們這里取最后一個值作為基準(zhǔn)值， Comparable pivot = arr[right]; //定義一個指針,右移記錄，i指向小于等于pivot的最后一個值的下一個位置 int i = left; //初始化為起始位置 //遍歷left到right-1之間的元素 for (int j = left; j <= right - 1; j ) { if (arr[j].compareTo(pivot) <= 0) { //當(dāng)前遍歷元素小于等于基準(zhǔn)值 //交換小于等于pivot的最后一個值的下一個位置的值（無所謂它的大?。┡c當(dāng)前遍歷元素 swap(arr, i, j); //此時小于等于pivot的最后一個值為交換后的值，所以i 1,在i前面的表示都小于等于pivot i ; } } //這樣遍歷完，小于等于pivot的值都被交換到了i位置的前面，最終i位置本身指向的是大于pivot的 //這時，交換i位置處的值和pivot，最終pivot左邊是小于等于它的值，pivot右邊是大于它的值 swap(arr, i, right); //最終返回pivot最終的索引值，即i return i; }}import java.util.Arrays;public class SortTest { public static void main(String[] args) { Integer[] arr = new Integer[]{8,9,1,7,2,3,5,5,4,4,5,6,0,0,343,6789}; System.out.println("未排序的數(shù)組為:"); System.out.println(Arrays.toString(arr)); QuickSort quickSort = new QuickSort(); quickSort.sort(arr); System.out.println("排序后的數(shù)組為:"); System.out.println(Arrays.toString(arr)); }}
快速排序是一種最壞時間復(fù)雜度為O(n^2)的排序算法，
但是快速排序通常是實際排序應(yīng)用中最好的選擇，因為它的平均性能非常好——它期望的時間復(fù)雜度為O(nlgn)，而且O(nlgn)中隱含的常數(shù)因子非常小
快速排序是原址排序的，所以空間復(fù)雜度為O(1)
快速排序再虛存環(huán)境中也能很好地工作
代碼演示示例：
public class SortPerformanceTest { public static void main(String[] args) { //創(chuàng)建100000個隨機數(shù)據(jù) Double[] arr1 = new Double[100000]; for (int i = 0; i < arr1.length; i ) { arr1[i] = (Double) (Math.random() * 10000000); //這里使用10000000是為了讓數(shù)據(jù)更分散 } //創(chuàng)建排序類的對象 QuickSort quickSort = new QuickSort(); //使用希爾排序?qū)rr1進行排序 long quickSort_start = System.currentTimeMillis(); quickSort.sort(arr1); long quickSort_end = System.currentTimeMillis(); System.out.println("快速排序所用的時間為：" (quickSort_end - quickSort_start) "ms"); }}
