快速排序（簡稱快排）因為其效率較高（平均o(nlogn)）經常在筆試題中對其考查。
對于快排的第一步是選取一個“基數”，將會用這個“基數”與其它數進行比較交換。而這個“基數”的選擇將影響到快排的效率如何，但如果為了選擇基數而選擇基數則會本末倒置。例如為了找到最佳基數，則需要在整個待排序列中找到中位數，但查找中位數實際上代價又會很高。基數的選擇通常來說就是待排序序列中的第一個對象或者中間的一個對象或者最后一個對象。本文以選取第一個元素為例對快排做一個簡要分析實現。
以待排序列{6, 5, 3, 1, 7, 2, 4}為例，選取第一個元素6為基數。
選擇了基數過后則需要進行和數組元素進行比較交換，如何進行比較和誰進行比較？快排第二步在數組的第一個元素和最后元素各設置一個“哨兵”。
選好基數，設置好哨兵過后，接下來則是開始比較，將基數先與最后一個哨兵j進行比較，如果大于哨兵j則與其進行交換同時哨兵i+1。
此時基數不再與哨兵j進行比較，而是與哨兵i進行比較，如果基數大于哨兵i，則哨兵一直向后移，直到大于基數為止交換同時哨兵j-1。
重復上面的步驟，基數再與哨兵j比較。
最終結果可見哨兵i的位置=哨兵j的位置，此時將基數賦值給這個位置。
這樣就達到了基數6左邊的數字均小于它，右邊的數字均大于它，再利用遞歸對其左右數組進行同樣的步驟選取基數，設置哨兵，最后即可完成排序。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
package com.algorithm.sort.quick;import java.util.arrays;/** * 快速排序 * created by yulinfeng on 2017/6/26. */public class quick { public static void main(string[] args) { int[] nums = {6, 5, 3, 1, 7, 2, 4}; nums = quicksort(nums, 0, nums.length - 1); system.out.println(arrays.tostring(nums)); } /** * 快速排序 * @param nums 待排序數組序列 * @param left 數組第一個元素索引 * @param right 數組最后一個元素索引 * @return 排好序的數組序列 */ private static int[] quicksort(int[] nums, int left, int right) { if (left < right) { int temp = nums[left]; //基數 int i = left; //哨兵i int j = right; //哨兵j while (i < j) { while (i < j && nums[j] >= temp) { j--; } if (i < j) { nums[i] = nums[j]; i++; } while (i < j && nums[i] < temp) { i++; } while (i < j) { nums[j] = nums[i]; j--; } } nums[i] = temp; quicksort(nums, left, i - 1); quicksort(nums, i + 1, right); } return nums; }} |
python3
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#快速排序def quick_sort(nums, left, right): if left < right: temp = nums[left] #基數 i = left #哨兵i j = right #哨兵j while i < j: while i < j and nums[j] >= temp: j -= 1 if i < j: nums[i] = nums[j] i += 1 while i < j and nums[i] < temp: i += 1 if i < j: nums[j] = nums[i] j -= 1 nums[i] = temp quick_sort(nums, left, i - 1) quick_sort(nums, i + 1, right) return numsnums = [6, 5, 3, 1, 7, 2, 4]nums = quick_sort(nums, 0, len(nums) - 1)print(nums) |
以上這篇比較排序之快速排序(實例代碼)就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
