排序算法:快速排序

2021-01-08 萬裡山川

在日常開發中經常會遇到一類問題,就是對一個集合的數據進行排序

掌握一些排序算法,對於日常開發是非常有幫助

今天介紹一下快速排序法

01算法邏輯

02時間複雜度

由上圖邏輯可以得出,參照遞歸表達式漸進複雜度分析

快速排序的時間複雜度遞歸表達式為,其中a=2,b=2,d=1

由算法導論的主定理可以推導出,快速排序的時間複雜度為

03空間複雜度

由上圖邏輯可以得出,參照遞歸表達式漸進複雜度分析

快速排序的空間複雜度遞歸表達式為,其中a=2,b=2,d=1

由算法導論的主定理可以推導出,快速排序的空間複雜度為

04java代碼實現

public int[] sortByQuick(int[] data, int start, int end) {

int i = start;

int j = end;

//Todo: 如果比較後的左側位置和右側位置不等,則繼續執行比較規則

while (i != j) {

//Todo: 執行右側比較規則,返回交換後的下標

j = this.quick_right(data, i, j);

if (j != start) {

//右側比較規則執行交換後,左側下標+1

i++;

}

//Todo: 執行左側比較規則,返回交換後的下標

i = this.quick_left(data, i, j);

}

//Todo: 如果拆分後存在左側數據的話,則繼續從左側遞歸排序

if (i != start && start != i - 1) {

data = this.sortByQuick(data, start, i - 1);

}

//Todo: 如果拆分後存在右側數據的話,則繼續從右側遞歸排序

if (j != end && j + 1 != end) {

data = this.sortByQuick(data, j + 1, end);

}

return data;

}

public int quick_right(int[] data, int start, int end) {

for (int k = end; k > start; k--) {

if (data[start] > data[k]) {

int temp = data[k];

data[k] = data[start];

data[start] = temp;

return k;

}

}

return start;

}

public int quick_left(int[] data, int start, int end) {

for (int k = start; k < end; k++) {

if (data[k] > data[end]) {

int temp = data[k];

data[k] = data[end];

data[end] = temp;

return k;

}

}

return end;

}

05小結

今天主要介紹了單集合排序的一種排序算法——快速排序

小夥伴們都了解了嗎?

下次小Top將繼續介紹單集合排序算法

對於今天的內容有任何疑問或問題,歡迎留言或討論 ^-^

相關焦點

  • 重溫7種排序算法 第一篇,交換排序算法:冒泡排序、快速排序
    排序算法可分為以下幾類:    交換排序算法:冒泡排序、快速排序;    選擇排序算法:簡單選擇排序、堆排序;    插入排序算法:直接插入排序、希爾排序;    歸併排序算法。    主要做了以上7種排序算法的筆記,字數可能較多,所以分為幾篇。
  • 快速排序算法
    而治,也就是合,就是國君只需要管理諸侯,諸侯管理地方首領,匯總到國君那就行了  分治法的精髓:分:將問題分解為規模更小的子問題;治:將這些規模更小的子問題逐個擊破;合:將已解決的子問題合併,最終得出「母」問題的解;快速排序的使用場景是:   數據量大而雜亂的排序,避免出現最壞的情況。
  • 快速排序算法介紹
    它的基本思想是:通過一趟排序將要排序的數據分割成獨立的兩部分,其中一部分的所有數據都比另外一部分的所有數據都要小,然後再按此方法對這兩部分數據分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數據變成有序序列。
  • Java 快速排序算法
    簡介上一章我們學習了 [Java 希爾排序算法],這一章,我們來學習快速排序算法
  • 排序算法 --快速排序
    快排是一種使用比較普遍的排序算法,今天就來介紹這個算法。
  • Python中的快速排序算法,快速排序的優缺點,中級python技術點
    Python中的快速排序算法就像合併排序一樣,快速排序算法採用分治法的原理將輸入數組分為兩個列表,第一個包含小項目,第二個包含大項目。然後,該算法將對兩個列表進行遞歸排序,直到對結果列表進行完全排序為止。劃分輸入列表稱為對列表進行分區。
  • 算法圖解 | 分而治之與快速排序算法
    快速排序例如快速排序問題,一個列表進行排序,如下圖首先選擇列表中的一個元素作為基準元素,其他的元素都與這個元素做比較,找出小於這個基準值的值、大於基準值的值。(O表示法表示)快速排序的性能高度依賴於你選擇的基準值。
  • 排序算法:歸併排序
    在日常開發中經常會遇到一類問題,就是對一個集合的數據進行排序掌握一些排序算法,對於日常開發是非常有幫助今天介紹一下歸併排序法01算法邏輯02時間複雜度由上圖邏輯可以得出,歸併排序的循環次數為由算法導論的主定理可以推導出,可見之前的文章(文末有連結)歸併排序的時間複雜度為03空間複雜度由上圖邏輯可以得出,歸併排序每次分解都是要復一份新的數據片段
  • 算法連載之快速排序
    切分完成後,劃分為兩個待排序數組:左側為空數組,右側是9。<6>索引位置為2-2,開始索引不小於結束索引,返回。<7>切分:數組9隻有一項元素,因此i索引為3。左側索引為3-3,右側索引為4-4。
  • 排序算法問題:穩定排序與不穩定排序
    首先,排序算法的穩定性大家應該都知道,通俗地講就是能保證排序前2個相等的數其在序列的前後位置順序和排序後它們兩個的前後位置順序相同。在簡單形式化一下,如果Ai = Aj,Ai原來在位置前,排序後Ai還是要在Aj位置前。其次,說一下穩定性的好處。排序算法如果是穩定的,那麼從一個鍵上排序,然後再從另一個鍵上排序,第一個鍵排序的結果可以為第二個鍵排序所用。
  • JavaScript算法之快速排序
    如果你在面試軟體工程師的職位,經常被問到的一個問題是快速排序是如何工作的。快速排序最簡單的邏輯步驟如下:選擇一個基準元素,把數組分為兩個子數組。有些算法選擇第一個元素為基準,這樣不是最佳選擇,因為對於已排序的數組來說這樣做的性能是最差的。
  • JS家的排序算法 十大經典算法排序總結
    (Quick Sort)快速排序須知:又是一種分而治之思想在排序算法上的典型應用。本質上來看,快速排序應該算是在冒泡排序基礎上的遞歸分治法。快速排序的名字起的是簡單粗暴,因為一聽到這個名字你就知道它存在的意義,就是快,而且效率高! 它是處理大數據最快的排序算法之一了。雖然Worst Case的時間複雜度達到了O(n²),但是人家就是優秀,在大多數情況下都比平均時間複雜度為O(n log n) 的排序算法表現要更好,可是這是為什麼呢,我也不知道。。。
  • 算法系列: 10大常見排序算法: 快速排序法
    快速排序法(Quick Sort)是劍橋大學教授在讀大學時發明的排序算法,也是當今使用最廣泛的高效排序算法之一。QuickSort思路直觀而精巧,值得我們反覆吟唱快速排序法就是用這個直觀的事實來給數組中的每一個數字排序。我們來看個例子:現在有9個數字 [ 31 2 7 48 4 10 17 52 61 ],  我們任意選取一個數字17,下面來確定17的位置。
  • 排序算法
    數據結構中的幾種排序算法:插入排序分為直接插入排序和希爾排序。
  • 排序算法:選擇排序
    在日常開發中經常會遇到一類問題,就是對一個集合的數據進行排序掌握一些排序算法,對於日常開發是非常有幫助的今天介紹一下選擇排序法01算法邏輯02時間複雜度由上圖邏輯可以得出,選擇排序的循環次數為由循環次數可以得出,選擇排序的時間複雜度為03空間複雜度由上圖邏輯可以得出
  • 深入理解快速排序和 STL 的 sort 算法
    字面上的解釋是"分而治之",這個技巧是很多高效算法的基礎,如排序算法(歸併排序、快速排序)、傅立葉變換(快速傅立葉變換)。分治法中最重要的部分是循環遞歸的過程,每一層遞歸有三個具體步驟:分解:將原問題分解為若干個規模較小,相對獨立,與原問題形式相同的子問題。解決:若子問題規模較小且易於解決時,則直接解。否則,遞歸地解決各子問題。
  • 圖解排序算法:快速排序
    算法首先選一個基準 pivot,然後過一遍數組,把小於 pivot 的都挪到 pivot 的左邊,把大於 pivot 的都挪到 pivot 的右邊。這樣一來,這個 pivot 的位置就確定了,也就是排好了 1 個元素。
  • JavaScript實現排序算法
    一、大O表示法大O表示法:在計算機中採用粗略的度量來描述計算機算法的效率,這種方法被稱為「大O」表示法在數據項個數發生改變時,算法的效率也會跟著改變。所以說算法A比算法B快兩倍,這樣的比較是沒有意義的。因此我們通常使用算法的速度隨著數據量的變化會如何變化的方式來表示算法的效率,大O表示法就是方式之一。
  • 排序算法之插入排序
    排序算法在編程領域中起著舉足輕重的作用,在目標檢索、機器學習、數值計算、圖像處理等領域有著廣泛地應用。為了追本溯源,公眾號特推出常用經典排序算法系列推文,讓小夥伴們深入了解排序算法的實現原理,同時也提升matlab編程能力。
  • 經典排序算法三 選擇排序(JAVA實現)
    選擇排序原理:每一趟從待排序的記錄中選出最小的元素,順序放在已排好序的序列最後,直到全部記錄排序完畢。也就是:每一趟在n-i+1(i=1,2,…n-1)個記錄中選取關鍵字最小的記錄作為有序序列中第i個記錄。基於此思想的算法主要有簡單選擇排序、樹型選擇排序和堆排序。