|
目錄 1.基本思想 1.1 基本思想 1.2 使用分治策略的三個步驟分析快速排序 1.3 歸并排序與快速排序比較 2.圖解原理 3.代碼實現(xiàn) 3.1 實現(xiàn)方式1：選取中間值作為基準值 3.2 實現(xiàn)方式2：選取最右邊的值作為基準值 4.性能分析
1.基本思想1.1 基本思想快速排序是基于分治策略的一種排序 基本思想 1．基準：先從數(shù)列中取出一個數(shù)作為基準數(shù)。 2．分區(qū)過程：將比這個數(shù)大的數(shù)全放到它的右邊，小于或等于它的數(shù)全放到它的左邊。 3．再對左右區(qū)間重復(fù)第一、二步，直到各區(qū)間只有一個數(shù)。
注意：快速排序在分的時候，就進行了“排序”處理
1.2 使用分治策略的三個步驟分析快速排序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)有序
1.3 歸并排序與快速排序比較歸并排序?qū)?shù)組分成連個子數(shù)組分別排序，并將有序的子數(shù)組歸并以將整個數(shù)組排序；而快速排序是當(dāng)兩個子數(shù)組都有序時，整個數(shù)組也就自然有序了 歸并排序在分的時候不進行任何處理，而快速排序在分的時候，要進行元素交換，保正左邊元素小于基準值，右邊元素大于基準值 歸并排序遞歸調(diào)用發(fā)生在處理整個數(shù)組之前，快速排序遞歸調(diào)用發(fā)生在處理整個數(shù)組之后 歸并排序在合并的時候完成排序，快速排序在分的時候完成排序，合并時，什么都不做 在歸并排序中，一個數(shù)組被等分為兩半，在快速排序中，切分的位置取決于數(shù)組的內(nèi)容
2.圖解原理
3.代碼實現(xiàn)關(guān)鍵詞解釋 pivot：基準元素 partition：將整個數(shù)組進行切分
3.1 實現(xiàn)方式1：選取中間值作為基準值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)過切分后基準值最終索引
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 返回中間基準值pivot的索引值
*/
private int partition(Comparable[] arr,int left,int right){
//我們這里取中間值基準值，
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 ;
}
}
/**
* 最終我們需要返回用于切分的基準值的最終索引
*
* 循環(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));
}
}
3.2 實現(xiàn)方式2：選取最右邊的值作為基準值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)過切分后基準值最終索引
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 返回中間基準值pivot的索引值
*/
private int partition(Comparable[] arr, int left, int right) {
//我們這里取最后一個值作為基準值，
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)前遍歷元素小于等于基準值
//交換小于等于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));
}
}
4.性能分析快速排序是一種最壞時間復(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");
}
}
來源：https://www./content-1-442251.html
|
