快速排序的簡單理解

pythonxxoo 2022-06-23 15:03:26 阅读数:401

快速排序理解

優質資源分享

學習路線指引(點擊解鎖)知識定比特人群定比特
🧡 Python實戰微信訂餐小程序 🧡進階級本課程是python flask+微信小程序的完美結合,從項目搭建到騰訊雲部署上線,打造一個全棧訂餐系統。
Python量化交易實戰入門級手把手帶你打造一個易擴展、更安全、效率更高的量化交易系統

詳細描述

快速排序通過一趟排序將待排序列分割成獨立的兩部分,其中一部分序列的關鍵字均比另一部分序列的關鍵字小,則可分別對這兩部分序列繼續進行排序,以達到整個序列有序的目的。

快速排序詳細的執行步驟如下:

  1. 從序列中挑出一個元素,稱為 “基准”(pivot);
  2. 重新排序序列,所有比基准值小的元素擺放在基准前面,所有比基准值大的元素擺在基准的後面(相同的數可以到任一邊)。在這個分區退出之後,該基准就處於序列的中間比特置。這個稱為分區(partition)操作;
  3. 遞歸地(recursive)把小於基准值元素的子序列和大於基准值元素的子序列排序。

算法圖解

快速排序

問題解疑

快速排序可以怎樣選擇基准值?

第一種方式:固定比特置選擇基准值;在整個序列已經趨於有序的情况下,效率很低。

第二種方式:隨機選取待排序列中任意一個數作為基准值;當該序列趨於有序時,能够讓效率提高,但在整個序列數全部相等的時候,隨機快排的效率依然很低。

第三種方式:從區間的首、尾、中間,分別取出一個數,然後對比大小,取這 3 個數的中間值作為基准值;這種方式解决了很多特殊的問題,但對於有很多重複值的序列,效果依然不好。

快速排序有什麼好的優化方法?

首先,合理選擇基准值,將固定比特置選擇基准值改成三點取中法,可以解决很多特殊的情况,實現更快地分區。

其次,當待排序序列的長度分割到一定大小後,使用插入排序。對於待排序的序列長度很小或基本趨於有序時,插入排序的效率更好。

在排序後,可以將與基准值相等的數放在一起,在下次分割時可以不考慮這些數。對於解决重複數據較多的情况非常有用。

在實現上,遞歸實現的快速排序在函數尾部有兩次遞歸操作,可以對其使用尾遞歸優化(簡單地說,就是尾比特置調用自身)。

代碼實現


| | package cn.fatedeity.algorithm.sort; |
| | |
| | import java.util.Random; |
| | |
| | /** |
| | * 快速排序算法 |
| | */ |
| | public class QuickSort { |
| | private static void swap(int[] numbers, int src, int target) { |
| | int temp = numbers[src]; |
| | numbers[src] = numbers[target]; |
| | numbers[target] = temp; |
| | } |
| | |
| | private static int[] sort(int[] numbers, int low, int high) { |
| | if (low > high) { |
| | return numbers; |
| | } |
| | // 隨機數取基准值 |
| | Random random = new Random(); |
| | int pivotIndex = random.nextInt(low, high + 1); |
| | int pivot = numbers[pivotIndex]; |
| | swap(numbers, pivotIndex, low); |
| | |
| | int mid = low + 1; |
| | for (int i = low + 1; i <= high; i++) { |
| | if (numbers[i] < pivot) { |
| | swap(numbers, i, mid); |
| | mid++; |
| | } |
| | } |
| | swap(numbers, low, --mid); |
| | sort(numbers, low, mid - 1); |
| | sort(numbers, mid + 1, high); |
| | return numbers; |
| | } |
| | |
| | public static int[] sort(int[] numbers) { |
| | return sort(numbers, 0, numbers.length - 1); |
| | } |
| | } |
版权声明:本文为[pythonxxoo]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/174/202206231422018354.html