欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間:2024年03月07日 10:40:30   作者:大家都說(shuō)我身材好  
快速排序是對(duì)冒泡排序的一種改進(jìn),下面這篇文章主要給大家介紹了關(guān)于Java快速排序的實(shí)現(xiàn)方法,文中通過(guò)代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下

前言

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

一、快速排序的原理

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

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

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

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

具體來(lái)說(shuō),快速排序的過(guò)程如下:

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

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

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

需要注意的是,在遍歷數(shù)組時(shí),一般采用雙指針?lè)▉?lái)實(shí)現(xiàn)。具體來(lái)說(shuō),我們使用一個(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 中,我們可以使用以下代碼來(lái)實(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)左指針和右指針沒(méi)有相遇時(shí)循環(huán)
        while (i < j && arr[j] >= pivot) { // 右指針從右向左遍歷,找到第一個(gè)小于基準(zhǔn)元素的元素
            j--;
        }
        if (i < j) { // 如果左指針和右指針沒(méi)有相遇,將右指針?biāo)傅脑刭x值給左指針?biāo)傅奈恢?
            arr[i] = arr[j];
            i++;
        }
        while (i < j && arr[i] < pivot) { // 左指針從左向右遍歷,找到第一個(gè)大于等于基準(zhǔn)元素的元素
            i++;
        }
        if (i < j) { // 如果左指針和右指針沒(méi)有相遇,將左指針?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() 方法則是用來(lái)對(duì)數(shù)組進(jìn)行劃分的,它使用雙指針?lè)▉?lái)實(shí)現(xiàn)。

具體來(lái)說(shuō),我們首先將數(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ò)程。在最壞情況下,如果每次劃分都只能規(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)化技巧來(lái)提高快速排序算法的效率,如隨機(jī)選擇基準(zhǔn)元素、三數(shù)取中法等。

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

我認(rèn)為這種寫(xiě)法更容易理解

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

總結(jié)

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

相關(guān)文章

  • Java序列化反序列化原理及漏洞解決方案

    Java序列化反序列化原理及漏洞解決方案

    這篇文章主要介紹了Java序列化反序列化原理及漏洞解決方案,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2020-08-08
  • Java實(shí)現(xiàn)猜數(shù)字小游戲詳解流程

    Java實(shí)現(xiàn)猜數(shù)字小游戲詳解流程

    猜數(shù)字是興起于英國(guó)的益智類小游戲,起源于20世紀(jì)中期,一般由兩個(gè)人或多人玩,也可以由一個(gè)人和電腦玩。游戲規(guī)則為一方出數(shù)字,一方猜,今天我們來(lái)用Java把這個(gè)小游戲?qū)懗鰜?lái)練練手
    2021-10-10
  • MyBatis中XML映射器的實(shí)現(xiàn)

    MyBatis中XML映射器的實(shí)現(xiàn)

    MyBatis的真正強(qiáng)大在于它的語(yǔ)句映射,映射器的XML文件就顯得相對(duì)簡(jiǎn)單,本文主要介紹了MyBatis中XML映射器的實(shí)現(xiàn),具有一定的參考價(jià)值,感興趣的可以了解一下
    2024-01-01
  • SpringBoot集成SpirePDF實(shí)現(xiàn)文本替換功能

    SpringBoot集成SpirePDF實(shí)現(xiàn)文本替換功能

    SpirePDF是一個(gè)用于.NET平臺(tái)的高級(jí)PDF文檔處理庫(kù),它提供了一套完整的API,允許開(kāi)發(fā)者創(chuàng)建、編輯、轉(zhuǎn)換、合并、分割和解析PDF文件本文給大家介紹了SpringBoot集成SpirePDF實(shí)現(xiàn)文本替換功能,需要的朋友可以參考下
    2024-09-09
  • 關(guān)于Java Guava ImmutableMap不可變集合源碼分析

    關(guān)于Java Guava ImmutableMap不可變集合源碼分析

    這篇文章主要介紹Java Guava不可變集合ImmutableMap的源碼分析的相關(guān)資料,需要的朋友可以參考下面具體的文章內(nèi)容
    2021-09-09
  • SpringBoot集成Apache POI實(shí)現(xiàn)Excel的導(dǎo)入導(dǎo)出

    SpringBoot集成Apache POI實(shí)現(xiàn)Excel的導(dǎo)入導(dǎo)出

    Apache POI是一個(gè)流行的Java庫(kù),用于處理Microsoft Office格式文件,包括Excel文件,本文主要介紹了SpringBoot集成Apache POI實(shí)現(xiàn)Excel的導(dǎo)入導(dǎo)出,具有一定的參考價(jià)值,感興趣的可以了解一下
    2024-06-06
  • MyBatis傳入?yún)?shù)的實(shí)例代碼

    MyBatis傳入?yún)?shù)的實(shí)例代碼

    這篇文章主要介紹了MyBatis傳入?yún)?shù)的實(shí)例代碼的相關(guān)資料,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下
    2016-06-06
  • Pattern.compile函數(shù)提取字符串中指定的字符(推薦)

    Pattern.compile函數(shù)提取字符串中指定的字符(推薦)

    這篇文章主要介紹了Pattern.compile函數(shù)提取字符串中指定的字符,使用的是Java中的Pattern.compile函數(shù)來(lái)實(shí)現(xiàn)對(duì)指定字符串的截取,本文給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2022-12-12
  • SpringBoot開(kāi)發(fā)案例 分布式集群共享Session詳解

    SpringBoot開(kāi)發(fā)案例 分布式集群共享Session詳解

    這篇文章主要介紹了SpringBoot開(kāi)發(fā)案例 分布式集群共享Session詳解,在分布式系統(tǒng)中,為了提升系統(tǒng)性能,通常會(huì)對(duì)單體項(xiàng)目進(jìn)行拆分,分解成多個(gè)基于功能的微服務(wù),可能還會(huì)對(duì)單個(gè)微服務(wù)進(jìn)行水平擴(kuò)展,保證服務(wù)高可用,需要的朋友可以參考下
    2019-07-07
  • SWT(JFace)體驗(yàn)之復(fù)制粘貼

    SWT(JFace)體驗(yàn)之復(fù)制粘貼

    SWT(JFace)體驗(yàn)之復(fù)制粘貼
    2009-06-06

最新評(píng)論