常見排序演算法——快速排序

来源:https://www.cnblogs.com/sdx-BK/archive/2019/12/10/12019085.html

快速排序: 它的基本思想是:通過一躺排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一不部分的所有數據都要小, 然後再按次方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。最壞情況的時 間複雜度為O(n2),最好情況時間複雜度為O(nlog ...


快速排序:

它的基本思想是:通過一躺排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一不部分的所有數據都要小,

然後再按次方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。最壞情況的時

間複雜度為O(n2),最好情況時間複雜度為O(nlog2n)。

圖解:

 

 

我已經將代碼的關鍵步驟都大了註釋,希望可以幫助理解。

//瞎打快排
package sdx;

import java.util.Arrays;

public class Main6 {
public static void quickSort(int[] arr,int left,int right){
int i,j,JiShu;
if(left>right){
return;//當左邊大於右邊時,方法不合法,所以return結束這個方法
}
//定義哨兵
i=left;
j=right;
//JiShu就是基準位
JiShu = arr[left];
//當i和j不相遇時,再迴圈中進行檢索。
while (i!=j) {
//先看右邊,依次往左遞減S
while (JiShu<=arr[j]&&i<j) {//i<j是為了是為了不讓在i和j相遇時錯過。
j--;//哨兵j向左繼續移動。
}
//再看左邊,依次往右遞增
while (JiShu>=arr[i]&&i<j) {
i++;//哨兵i向右繼續移動。
}
//如果滿足條件則交換
if (i<j) {
int t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}

}
//最後將基準為與i和j相等位置的數字交換(遞歸大法)
//定義時左邊第一個為 “基數”。將重合時的數與基數交換。將重合後的數放在左邊第一個。
arr[left] = arr[i]; //a[i]與a[j]都可以,因為i,j重合,位置相同。
arr[i] = JiShu; //將新數列的基數設置為最左邊那個數。
//遞歸調用左半數組
quickSort(arr, left, j-1);//調用自身
//遞歸調用右半數組
quickSort(arr, i+1, right);
}
public static void main(String[] args) {
int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
System.out.println("排序前的數組:"+Arrays.toString(arr));
quickSort(arr, 0, arr.length-1);
System.out.print("排序後的數組:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
}

}

運行截圖:

 


您的分享是我們最大的動力!

更多相關文章
  • 有個需求,從某個介面下載的一個zip壓縮包,往裡面添加一個說明文件。搜索了一下,沒有找到往zip直接添加文件的方法,最終解決方法是先解壓、再壓縮。具體過程如下: ...
  • 屬性 語法格式:修飾符 類型 屬性名 = 初值; 說明: 修飾符:public、protected、private:用於表示成員變數的訪問許可權。static:表示該成員變數為類變數,也稱為靜態變數。final:表示將該成員變數聲明為常量,其值無法更改。 類型:表示變數的類型。 屬性名:表示變數名稱。 ...
  • Java類的初始化順序 多說無益,以下是本人親自試驗的代碼,一目瞭然: 1 package test1; 2 3 public class Test { 4 public static void main(String[] argc) { 5 new Child(); 6 System.out.pr ...
  • composer install thinkphp6 報錯 Parse error: syntax error, unexpected ':', expecting '{' in vendor\topthink\think-helper\src\helper.php on line 233 ...
  • 前言本文的文字及圖片來源於網路,僅供學習、交流使用,不具有任何商業用途,版權歸原作者所有,如有問題請及時聯繫我們以作處理。作者:萬能搜吧 都是copy的百度SDK文檔,簡單說說怎麼用。 1、沒安裝Python的參見此文:Python學習筆記系列 1 ——安裝調試Python開發軟體 2、win+r輸 ...
  • import org.apache.spark.rdd.RDDimport org.apache.spark.{Partitioner, SparkConf, SparkContext} object Transformation { def main(args: Array[String]): U ...
  • AQS是JUC包中許多類的實現根基,這篇文章只是個人理解的產物,不免有誤,若閱讀過程中有發現不對的,希望幫忙指出[贊]! 1 AQS內臟圖 ​ 在開始瞭解 之前,我們先從上帝視角看看 是由幾個部分組成的。 ​ 內部維護了一個 修飾的 資源變數 ,裡面的所有操作都可以說跟這個變數有關係,因為它代表的就 ...
  • 出現如下錯誤: 解決辦法: DATABASES = { 'default': { 'ENGINE': 'django.db.backends.mysql', 'NAME': 'mxshop', 'HOST': '127.0.0.1', 'PORT': '3306', 'USER': 'mxshop' ...
一周排行
  • " 返回《C 併發編程》" "1. 概念介紹" "2. 非同步編程" "2.1. async運行過程" "2.2. async運行中同步上下文簡介" "2.3. 創建Task實例" "2.4. 捕獲非同步異常類型" "3. 並行編程" "3.1. Parallel" "3.2. 異常處理" "3.3. ...
  • 我們先看看兩個特效,感受一下,有沒有學習的動力? 核心API:Texture2D.SetPixel(int x, int y, Color color),Texture2D.Apply() 實現原理:對象池 思路: 第一幀繪製前:遍歷瓦片上所有活著的粒子對象並且進行數據操作(或運動,死亡),發生運動 ...
  • 原來的導出方式比較適用於比較簡單的導出,每一條數據在一行,數據列雖然自定義程度比較高,如果要一條數據對應多行就做不到了,於是就想支持根據模板導出,在 1.8.0 版本中引入了根據模板導出的功能 ...
  • 創建一個bat腳本, 裡面寫上: reg delete HKEY_CURRENT_USER\Software\JetBrains\dotMemory /freg delete HKEY_CURRENT_USER\Software\Microsoft\Windows\CurrentVersion\Ex ...
  • Linux下有vsyscall來優化一些例如time(NULL), gettimeofday這種調用的消耗; 但是Windows下, 沒有類似的東西, 但是思路還是有的 1. 程式啟動的時候, 獲取一下準確的時間戳 2. 然後每次需要獲取時間的時候, 獲取一下流逝的時間, 可以通過獲取CPU的tic ...
  • 當用戶按下鍵盤上的一個鍵時,就會發生一系列事件。下表根據他們的發生順序列出了這些事件: 表 所有元素的鍵盤事件(按順序) 鍵盤處理永遠不會像上面看到的這麼簡單。一些控制項可能會掛起這些事件中的某些事件,從而可執行自己更特殊的鍵盤處理。最明顯的例子是TextBox控制項,它掛起了TextInput事件。對 ...
  • static void LocalMethod() { Cube(100); void Cube(int x) => Console.WriteLine($"The cube of {x} is {x * x * x}"); } static void GoToDemo() { int i = 1; ...
  • 滑鼠事件執行幾個關聯的任務。當滑鼠移到某個元素上時,可通過最基本的滑鼠事件進行響應。這些事件是MouseEnter(當滑鼠指針移到元素上時引發該事件)和MouseLeave(當滑鼠指針離開元素時引發該事件)。這兩個事件都是直接事件,這意味著他們不使用冒泡和隧道過程,而是源自一個元素並且只被該元素引發 ...
  • 反射這個詞聽起來就很牛逼是吧? 嗯的確,反射是比較高級的特性,只有語言基礎很扎實的Dev們才應該使用它。 搞點反射,可以提高程式的靈活性、可擴展性、耦合度。 反射這東西,是為了動態地運行時載入,相比於靜態代碼。編譯的時候就是板上釘釘了。 就是說,如果你的程式需要在運行時搞一些晚綁定,動態載入或檢查對 ...
  • 眾所周知,微服務架構是由一眾微服務組成,項目中調用其他微服務介面更是常見的操作。為了便於調用外部介面,我們的常用思路一般都是封裝一個外部介面的客戶端,使用時候直接調用相應的方法。webservice或WCF的做法就是引用服務,自動生成客戶端。在webapi2.0里,我們都會手動封裝一個靜態類。那麼在 ...
x