什么是快速排序
快速排序（Quicksort）雇盖，計算機科學詞匯睛廊，適用領(lǐng)域Pascal藐不，c++等語言莉兰，是對冒泡排序算法的一種改進浅乔。
快速排序的思想
快速排序算法通過多次比較和交換來實現(xiàn)排序倔喂，其排序流程如下：
首先設(shè)定一個分界值铝条，通過該分界值將數(shù)組分成左右兩部分。
將大于或等于分界值的數(shù)據(jù)集中到數(shù)組右邊席噩，小于分界值的數(shù)據(jù)集中到數(shù)組的左邊班缰。此時，左邊部分中各元素都小于分界值悼枢，而右邊部分中各元素都大于或等于分界值埠忘。
然后，左邊和右邊的數(shù)據(jù)可以獨立排序馒索。對于左側(cè)的數(shù)組數(shù)據(jù)莹妒，又可以取一個分界值，將該部分數(shù)據(jù)分成左右兩部分绰上，同樣在左邊放置較小值旨怠，右邊放置較大值。右側(cè)的數(shù)組數(shù)據(jù)也可以做類似處理蜈块。
重復上述過程鉴腻，可以看出，這是一個遞歸定義百揭。通過遞歸將左側(cè)部分排好序后爽哎，再遞歸排好右側(cè)部分的順序。當左信峻、右兩個部分各數(shù)據(jù)排序完成后倦青，整個數(shù)組的排序也就完成了瓮床。
圖解快速排序
快速排序的步驟
-
交換函數(shù)
這個函數(shù)就不多說了盹舞，就是交換兩個元素位置的函數(shù)。
/** * 交換某兩個位置元素的函數(shù) * @param arr * @param i * @param j */ public static void swap(int[] arr, int i, int j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } -
選取基準值的函數(shù)
選取一個基準值隘庄，然后把比基準值大的移動到基準值的右邊踢步，比基準值小的移動到基準值的左邊，最后返回基準值的位置丑掺。示例方法中是使用默認去第一個获印，這種方法是有缺陷的，基準值不夠隨機街州，對于部分場景可能會效率低兼丰，文章最后會做分析和提出解決方案。
/** * 數(shù)組的最低位和最高位 * @param arr * @param lo * @param hi *///partition public static int partition(int[] arr, int lo, int hi){ //低位給i,高位加一給 j ,為什么這里高位要 +1 因為下面的用法是 --j , 為什么地位不需要 -1 ,下面用的是 --i, //因為已經(jīng)提前把低位的值給拿出來了,第一個比較的就是 arr[++i] 元素 int i = lo, j = hi + 1; //這里是直接取了第一個作為基準值,如果是已經(jīng)有序的數(shù)組,會導致時間復雜度很高 int v = arr[lo]; //從小到大排序 while(true){ //左邊的指針找到一個比自己大的,然后停止循環(huán) while(v >= arr[++i]){ if(i >= hi) break; } //右邊的指針找到一個比自己小的,然后停止循環(huán) while(v <= arr[--j]){ if(j <= lo) break; } //如果左指針 大于等于 右指針,則跳出循環(huán) if(i >= j){ break; } //交換左指針指向的比自己大的和右指針指向的比自己小的元素的位置 swap(arr,i,j); } //交換最低位元素和i,j位置元素 swap(arr,lo,j); //范圍基準值的位置 return j; }
-
排序函數(shù)
整個排序方法的入口唆缴，根據(jù)調(diào)整后的基準值來作為界限鳍征，分別排序基準值兩側(cè)的子序列
//排序函數(shù) /** * 方法是遞歸調(diào)用,每次都是按照基準值調(diào)整完元素后,把基準值兩次的元素繼續(xù)按照此方法來排序 * @param arr * @param lo * @param hi */ public static void sort(int[] arr, int lo, int hi){ //低位不大于等于高位 if(lo >= hi) return; //獲取基準值 int partition= partition(arr,lo,hi); //把基準值兩側(cè)的元素繼續(xù)按照快速排序的方法排序 sort(arr, lo, partition - 1); sort(arr, partition+1,hi); }
完整的代碼
package demo.off;
import javax.sound.midi.Soundbank;
import java.util.Arrays;
public class kuaisupaixu {
public static void main(String[] args) {
int[] arr ={7,5,32,1,4,5,6,7,8,9,8,77,66,55,22,10};
sort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));
}
//排序函數(shù)
/**
* 測方法是遞歸調(diào)用,每次都是按照基準值調(diào)整完元素后,把基準值兩次的元素繼續(xù)按照此方法來排序
* @param arr
* @param lo
* @param hi
*/
public static void sort(int[] arr, int lo, int hi){
//低位不大于等于高位
if(lo >= hi) return;
//獲取基準值
int partition= partition(arr,lo,hi);
//把基準值兩側(cè)的元素繼續(xù)按照快速排序的方法排序
sort(arr, lo, partition - 1);
sort(arr, partition+1,hi);
}
//swap
/**
* 交換某兩個位置元素的函數(shù)
* @param arr
* @param i
* @param j
*/
public static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/**
* 數(shù)組的最低位和最高位
* @param arr
* @param lo
* @param hi
*///partition
public static int partition(int[] arr, int lo, int hi){
//低位給i,高位加一給 j ,為什么這里高位要 +1 因為下面的用法是 --j , 為什么地位不需要 -1 ,下面用的是 --i,
//因為已經(jīng)提前把低位的值給拿出來了,第一個計較的就是 arr[++i] 元素
int i = lo, j = hi + 1;
//這里是直接取了第一個作為基準值,如果是已經(jīng)有序的數(shù)組,會導致時間復雜度很高
int v = arr[lo];
//從小到大排序
while(true){
//左邊的指針找到一個比自己大的,然后停止循環(huán)
while(v >= arr[++i]){
if(i >= hi) break;
}
//右邊的指針找到一個比自己小的,然后停止循環(huán)
while(v <= arr[--j]){
if(j <= lo) break;
}
//如果左指針 大于等于 右指針,則跳出循環(huán)
if(i >= j){
break;
}
//交換左指針指向的比自己大的和右指針指向的比自己小的元素的位置
swap(arr,i,j);
}
//交換最低位元素和i,j位置元素
swap(arr,lo,j);
//范圍基準值的位置
return j;
}
}
排序結(jié)果
排序前
int[] arr ={7,5,32,1,4,5,6,7,8,9,8,77,66,55,22,10};
排序后
[1, 4, 5, 5, 6, 7, 7, 8, 8, 9, 10, 22, 32, 55, 66, 77]
快速排序的缺點
盡管快速排序有很多優(yōu)點，它的基本實現(xiàn)仍有一個潛在的缺點：在切分不平衡時這個程序可能會極為低效面徽。例如艳丛，如果第一次從最小的元素切分匣掸，第二次從第二小的元素切分，如此這般氮双，每次調(diào)用只會移除一個元素碰酝。這會導致一個大子數(shù)組需要切分很多次。我們要在快速排序前將數(shù)組隨機排序的主要原因就是要避免這種情況戴差。它能夠使產(chǎn)生糟糕的切分的可能性降到極低送爸，我們就無需為此擔心了。[1]
快速排序的改進方案
為了讓基準值更加的隨機暖释，可以取高位碱璃，低位，中位中間的中位數(shù)饭入，來增加基準值的隨機性嵌器。
//計算中位數(shù)并且交換位置
if(arr[hi] > arr[mid] && arr[i] < arr[mid]){
//mid 位置是三個數(shù)中的中位數(shù)
swap(arr,i,mid);
}else if(arr[i] > arr[hi] && arr[i] < arr[mid]){
//i就是中位數(shù),不需要交換
//mid = i;
}else{
//j位置是中位數(shù),需要交換位置
swap(arr,i,hi);
}
完整的partition代碼：
/**
* 數(shù)組的最低位和最高位
* @param arr
* @param lo
* @param hi
*///partition
public static int partition(int[] arr, int lo, int hi){
//低位給i,高位加一給 j ,為什么這里高位要 +1 因為下面的用法是 --j , 為什么地位不需要 -1 ,下面用的是 --i,
//因為已經(jīng)提前把低位的值給拿出來了,第一個計較的就是 arr[++i] 元素
int i = lo, j = hi + 1 ,mid = (lo + hi)/2;
//計算中位數(shù)并且交換位置
if(arr[hi] > arr[mid] && arr[i] < arr[mid]){
//mid 位置是三個數(shù)中的中位數(shù)
swap(arr,i,mid);
}else if(arr[i] > arr[hi] && arr[i] < arr[mid]){
//i就是中位數(shù),不需要交換
//mid = i;
}else{
//j位置是中位數(shù),需要交換位置
swap(arr,i,hi);
}
//這里是直接取了第一個作為基準值,如果是已經(jīng)有序的數(shù)組,會導致時間復雜度很高
int v = arr[lo];
//從小到大排序
while(true){
//左邊的指針找到一個比自己大的,然后停止循環(huán)
while(v >= arr[++i]){
if(i == hi) break;
}
//右邊的指針找到一個比自己小的,然后停止循環(huán)
while(v <= arr[--j]){
if(j == lo) break;
}
//如果左指針 大于等于 右指針,則跳出循環(huán)
if(i >= j){
break;
}
//交換左指針指向的比自己大的和右指針指向的比自己小的元素的位置
swap(arr,i,j);
}
System.out.println(i);
System.out.println(j);
//交換最低位元素和i,j位置元素
swap(arr,lo,j);
//范圍基準值的位置
return j;
}
快速排序和歸并排序
快速排序是一種分治的排序算法。它將一個數(shù)組分成兩個子數(shù)組谐丢，將兩部分獨立地排序爽航。快速排序和歸并排序是互補的：歸并排序?qū)?shù)組分成兩個子數(shù)組分別排序乾忱，并將有序的子數(shù)組歸并以將整個數(shù)組排序讥珍；而快速排序?qū)?shù)組排序的方式則是當兩個子數(shù)組都有序時整個數(shù)組也就自然有序了。在第一種情況中窄瘟，遞歸調(diào)用發(fā)生在處理整個數(shù)組之前衷佃；在第二種情況中，遞歸調(diào)用發(fā)生在處理整個數(shù)組之后蹄葱。在歸并排序中氏义，一個數(shù)組被等分為兩半；在快速排序中图云，切分（partition）的位置取決于數(shù)組的內(nèi)容惯悠。[1]
