前言

快速排序是一種常用的基于比較的排序算法，其時間復(fù)雜度為 O(nlogn)，并且具有穩(wěn)定性和廣泛的應(yīng)用場景。本文將全面詳細的講解一下 Java 中快速排序算法的原理、實現(xiàn)以及時間復(fù)雜度等問題。

一、快速排序的原理

快速排序是一種分治思想的排序算法，其基本原理可以概括為以下三步：

• 選取一個基準(zhǔn)元素，將待排序數(shù)組劃分為左右兩個子數(shù)組；

• 將比基準(zhǔn)元素小的數(shù)都移到左子數(shù)組中，將比基準(zhǔn)元素大的數(shù)都移到右子數(shù)組中；

• 對左右兩個子數(shù)組遞歸執(zhí)行上述操作，直到每個子數(shù)組只剩下一個元素為止。

具體來說，快速排序的過程如下：

• 首先選取待排序數(shù)組中一個元素作為基準(zhǔn)元素，通常選擇第一個元素或最后一個元素作為基準(zhǔn)元素。

• 遍歷數(shù)組，將小于基準(zhǔn)元素的元素放到左邊，大于等于基準(zhǔn)元素的元素放到右邊，此時數(shù)組被劃分成了兩個部分。

• 對左半部分和右半部分分別遞歸執(zhí)行上述操作，直到排序完成。

需要注意的是，在遍歷數(shù)組時，一般采用雙指針法來實現(xiàn)。具體來說，我們使用一個左指針指向數(shù)組的第一個元素，用一個右指針指向數(shù)組的最后一個元素，然后從左到右依次遍歷數(shù)組中的元素，如果當(dāng)前元素小于基準(zhǔn)元素，就將它和左指針?biāo)傅脑亟粨Q，然后將左指針向右移動一位；如果當(dāng)前元素大于等于基準(zhǔn)元素，就將它和右指針?biāo)傅脑亟粨Q，然后將右指針向左移動一位。重復(fù)上述操作直到左指針和右指針相遇為止。

二、快速排序的實現(xiàn)

在 Java 中，我們可以使用以下代碼來實現(xiàn)快速排序算法：

public static void quickSort(int[] arr, int left, int right) {
    if (left < right) { // 當(dāng)數(shù)組只有一個元素時結(jié)束遞歸
        int partitionIndex = partition(arr, left, right); // 對數(shù)組進行劃分，獲取基準(zhǔn)元素位置
        quickSort(arr, left, partitionIndex - 1); // 對左子數(shù)組遞歸執(zhí)行快速排序
        quickSort(arr, partitionIndex + 1, right); // 對右子數(shù)組遞歸執(zhí)行快速排序
    }
}

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[left]; // 將數(shù)組的第一個元素設(shè)置為基準(zhǔn)元素
    int i = left; // 初始化左指針
    int j = right; // 初始化右指針
    while (i < j) { // 當(dāng)左指針和右指針沒有相遇時循環(huán)
        while (i < j && arr[j] >= pivot) { // 右指針從右向左遍歷，找到第一個小于基準(zhǔn)元素的元素
            j--;
        }
        if (i < j) { // 如果左指針和右指針沒有相遇，將右指針?biāo)傅脑刭x值給左指針?biāo)傅奈恢?
            arr[i] = arr[j];
            i++;
        }
        while (i < j && arr[i] < pivot) { // 左指針從左向右遍歷，找到第一個大于等于基準(zhǔn)元素的元素
            i++;
        }
        if (i < j) { // 如果左指針和右指針沒有相遇，將左指針?biāo)傅脑刭x值給右指針?biāo)傅奈恢?
            arr[j] = arr[i];
            j--;
        }
    }
    arr[i] = pivot; // 將基準(zhǔn)元素放到最終位置
    return i; // 返回基準(zhǔn)元素的位置
}

在上述代碼中，quickSort() 方法是快速排序算法的入口，它采用遞歸的方式對左右兩個子數(shù)組進行排序。partition() 方法則是用來對數(shù)組進行劃分的，它使用雙指針法來實現(xiàn)。

具體來說，我們首先將數(shù)組的第一個元素作為基準(zhǔn)元素 pivot，然后初始化左指針 i 和右指針 j。接著，我們先讓右指針 j 從右向左遍歷數(shù)組，找到第一個小于基準(zhǔn)元素的元素，并將其賦值給左指針?biāo)傅奈恢?；然后讓左指?i 從左向右遍歷數(shù)組，找到第一個大于等于基準(zhǔn)元素的元素，并將其賦值給右指針?biāo)傅奈恢?。重?fù)上述操作直到左指針和右指針相遇。

最后，將基準(zhǔn)元素 pivot 放到最終位置，即左指針?biāo)傅奈恢?，這樣就完成了對數(shù)組的一次劃分。在 partition() 方法中，返回的是基準(zhǔn)元素的位置，這個位置將用于快速排序算法的遞歸操作。

三、快速排序的時間復(fù)雜度

快速排序算法的時間復(fù)雜度主要取決于對數(shù)組進行劃分的過程。在最壞情況下，如果每次劃分都只能規(guī)模減少 1，那么快速排序的時間復(fù)雜度為 O(n^2)，這種情況發(fā)生在數(shù)組已經(jīng)排好序或基本排好序的情況下。

在平均情況下，假設(shè)每次劃分可以將數(shù)組分成大小分別為 k 和 (n-k-1) 的兩個子數(shù)組，那么快速排序的時間復(fù)雜度為 O(nlogn)。這是因為快速排序算法的遞歸深度為 logn，每一層的比較次數(shù)為 n，因此總體比較次數(shù)為 nlogn。

需要注意的是，快速排序算法的時間復(fù)雜度并不穩(wěn)定，因為基準(zhǔn)元素的選擇對算法的效率有很大的影響。如果每次都選取最大或最小的元素作為基準(zhǔn)元素，那么算法的時間復(fù)雜度將退化到 O(n^2)。因此，在實際應(yīng)用中，我們通常會采用一些優(yōu)化技巧來提高快速排序算法的效率，如隨機選擇基準(zhǔn)元素、三數(shù)取中法等。

補充：快速排序的另一種實現(xiàn)

我認為這種寫法更容易理解

public static void QuickSort(int []arr,int low,int high) {
		if(low<high) {
			int pivotpos=partition(arr,low,high);
			QuickSort(arr,low,pivotpos-1);
			QuickSort(arr,pivotpos+1,high);
		}
	}
 
	private static int partition(int[] arr, int low, int high) {
		 int pivot=arr[low];
		 while(low<high) {
			 //起初，一定要從右邊指針開始，因為arr[low]的值已經(jīng)扔給了pivot，arr[low]
			 //想象成無數(shù)字的空位
			 while(low<high&&pivot<=arr[high]) {
				 --high;
			 }
			 
			 //把比pivot的小的數(shù)扔到左邊指針
			 //把arr[high]扔到arr[low]這個空位上
			 //然后，high位置可以想象成無數(shù)字的空位
			 arr[low]=arr[high];
			 
			 while(low<high&&arr[low]<=pivot) {
				 ++low;
			 }
			 //把比pivot大的數(shù)扔到右邊
			//把arr[low]扔到arr[high]這個空位上
			//然后，low位置可以想象成是無數(shù)字的空位
			 arr[high]=arr[low];
		 }
		 //此時low==high,return high也一樣
		 arr[low]=pivot;
		return low;
	}
}

總結(jié)

到此這篇關(guān)于Java快速排序?qū)崿F(xiàn)方法的文章就介紹到這了,更多相關(guān)Java快速排序內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論