快捷導(dǎo)航

Java快速排序的實(shí)現(xiàn)方法示例

更新時(shí)間：2024年03月07日 10:40:30 作者：大家都說我身材好

快速排序是對(duì)冒泡排序的一種改進(jìn),下面這篇文章主要給大家介紹了關(guān)于Java快速排序的實(shí)現(xiàn)方法,文中通過代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下

前言

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

一、快速排序的原理

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

選取一個(gè)基準(zhǔn)元素，將待排序數(shù)組劃分為左右兩個(gè)子數(shù)組；
將比基準(zhǔn)元素小的數(shù)都移到左子數(shù)組中，將比基準(zhǔn)元素大的數(shù)都移到右子數(shù)組中；
對(duì)左右兩個(gè)子數(shù)組遞歸執(zhí)行上述操作，直到每個(gè)子數(shù)組只剩下一個(gè)元素為止。

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

首先選取待排序數(shù)組中一個(gè)元素作為基準(zhǔn)元素，通常選擇第一個(gè)元素或最后一個(gè)元素作為基準(zhǔn)元素。
遍歷數(shù)組，將小于基準(zhǔn)元素的元素放到左邊，大于等于基準(zhǔn)元素的元素放到右邊，此時(shí)數(shù)組被劃分成了兩個(gè)部分。
對(duì)左半部分和右半部分分別遞歸執(zhí)行上述操作，直到排序完成。

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

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

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

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

public static int partition(int[] arr, int left, int right) {
    int pivot = arr[left]; // 將數(shù)組的第一個(gè)元素設(shè)置為基準(zhǔn)元素
    int i = left; // 初始化左指針
    int j = right; // 初始化右指針
    while (i < j) { // 當(dāng)左指針和右指針沒有相遇時(shí)循環(huán)
        while (i < j && arr[j] >= pivot) { // 右指針從右向左遍歷，找到第一個(gè)小于基準(zhǔn)元素的元素
            j--;
        }
        if (i < j) { // 如果左指針和右指針沒有相遇，將右指針?biāo)傅脑刭x值給左指針?biāo)傅奈恢?
            arr[i] = arr[j];
            i++;
        }
        while (i < j && arr[i] < pivot) { // 左指針從左向右遍歷，找到第一個(gè)大于等于基準(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() 方法是快速排序算法的入口，它采用遞歸的方式對(duì)左右兩個(gè)子數(shù)組進(jìn)行排序。partition() 方法則是用來對(duì)數(shù)組進(jìn)行劃分的，它使用雙指針法來實(shí)現(xiàn)。

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

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

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

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

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

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

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

我認(rè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) {
			 //起初，一定要從右邊指針開始，因?yàn)閍rr[low]的值已經(jīng)扔給了pivot，arr[low]
			 //想象成無數(shù)字的空位
			 while(low<high&&pivot<=arr[high]) {
				 --high;
			 }
			 
			 //把比pivot的小的數(shù)扔到左邊指針
			 //把a(bǔ)rr[high]扔到arr[low]這個(gè)空位上
			 //然后，high位置可以想象成無數(shù)字的空位
			 arr[low]=arr[high];
			 
			 while(low<high&&arr[low]<=pivot) {
				 ++low;
			 }
			 //把比pivot大的數(shù)扔到右邊
			//把a(bǔ)rr[low]扔到arr[high]這個(gè)空位上
			//然后，low位置可以想象成是無數(shù)字的空位
			 arr[high]=arr[low];
		 }
		 //此時(shí)low==high,return high也一樣
		 arr[low]=pivot;
		return low;
	}
}