快速排序(快速排序算法)

今天主要介紹下快速排序算法是如何實(shí)現(xiàn)的，主要的目標(biāo)是：等很久之后忘了快速排序的思想時(shí)，找到這篇文章就可以幫助你很快的理解和回憶起來。

1.執(zhí)行流程1.從序列中選擇一個(gè)軸點(diǎn)元素pivot從最后一個(gè)元素向前遍歷我們的策略是：每次選擇第0位置的元素為軸點(diǎn)元素2.利用pivot將數(shù)組分割成2個(gè)子數(shù)組將小于pivot的元素放在pivot的左側(cè)將大于pivot的元素放在pivot的右側(cè)將等于pivot的元素放在pivot的哪側(cè)都可以，本文選擇左側(cè)3.對子序列進(jìn)行步驟1和步驟2操作直到不能再分割(子序列中只剩下一個(gè)元素)

??先介紹了下快排的執(zhí)行流程，腦海中先有個(gè)大致的思路?？偨Y(jié)一下就是先把一個(gè)大數(shù)組通過第一個(gè)元素將之分割成2個(gè)小的數(shù)組，并且以該軸點(diǎn)為界，小于它的在左邊，大于它的在右邊，然后遞歸對2個(gè)小數(shù)組執(zhí)行步驟1、2操作，直到不能再分割。也許理解了一部分，別擔(dān)心，接下來我會(huì)通過一個(gè)例子來帶你走一遍上述的流程。

2.例子演示

(注：圖片中的單詞start與begin同義)

解釋下調(diào)頭的事情：

開始的時(shí)候是從end往前遍歷大于pivot的值就end++；小于pivot的值時(shí)，end不變，并且將end指向的值替換begin指向的值，begin++從beigin往后遍歷小于pivot的值就begin++；小于pivot的值時(shí)，begin不變，并且將begin指向的值替換end指向的值，end++這樣交替進(jìn)行

??想想這樣做有什么好處？這只是一個(gè)處理值的方式，但是這樣處理很巧妙，而且很有作用。記住即可，不必要糾結(jié)。不這樣做當(dāng)然也是可以的，就是需要一些臨時(shí)變量進(jìn)行存儲，沒這個(gè)既省事又有用。

3.代碼實(shí)現(xiàn)

func quickSort(nums: inout [Int]) -> [Int] { sort(nums: &nums, begin: 0, end: nums.count) return nums } func sort(nums: inout [Int], begin: Int, end: Int) { if end - begin < 2 { return } var rBegin = begin; var rEnd = end let mid = pivotIndex(nums: &nums, begin: &rBegin, end: &rEnd) sort(nums: &nums, begin: begin, end:mid) sort(nums: &nums, begin: mid + 1, end: end) } //【1個(gè)大數(shù)組被分割成了左邊和右邊2個(gè)數(shù)組】 // 將pivot的位置拋出來，作為遞歸的時(shí)候的左邊數(shù)組的end和右邊數(shù)組的begin private func pivotIndex(nums: inout [Int], begin: inout Int, end: inout Int) -> Int { let pivot = nums[begin] end -= 1 while begin < end { while begin < end { if pivot < nums[end] { end -= 1 }el { nums[begin] = nums[end] begin += 1 break } } while begin < end { if pivot > nums[begin] { begin += 1 }el { nums[end] = nums[begin] end -= 1 break } } } //將軸點(diǎn)元素放到最終的位置 nums[begin] = pivot return begin }

結(jié)果：

??對比之前圖和這個(gè)打印圖：第一次打印的遍歷結(jié)果：[5, 4, 1, 2, 3, 6, 8, 7, 9]和我們上圖的流程的結(jié)果是一致的。

3.1 關(guān)于調(diào)頭邏輯的代碼實(shí)現(xiàn)

??這個(gè)真的是很難想到，通過while的break來實(shí)現(xiàn)的；

開始的時(shí)候是從end往前遍歷大于pivot的值就end++；就繼續(xù)在while循環(huán)小于pivot的值時(shí)，end不變，并且將end指向的值替換begin指向的值，begin++時(shí)，就會(huì)走while里面的if el中的break，完成調(diào)頭從begin往后遍歷小于pivot的值就begin++；就繼續(xù)再while循環(huán)小于pivot的值時(shí)，begin不變，并且將begin指向的值替換end指向的值，end++時(shí)，就會(huì)走while里面的if el中的break，完成調(diào)頭3.2 關(guān)于遞歸

前期的推文：leetcode 遞歸編程技巧-鏈表算法題有詳細(xì)介紹過遞歸，遞歸是一種很有用的編程技巧，必須掌握。不懂的同學(xué)可以看下之前的文章。

總結(jié)

??今天主要講解了快速排序的執(zhí)行流程，以及其中的來回交替的替換和調(diào)頭操作，希望能幫助到大家。