1. 原理

首先, 在一個待排序序列中, 以第一個元素為基準(zhǔn), 讓序列中所有的基準(zhǔn)小的元素在該元素左邊, 比其大的元素在其右邊. 算法是一種原地算法, 首先把序列里面從基準(zhǔn)開始的下一個元素一直到序列尾, 分成左右部分, 左邊的都是小的, 右邊的都是大的, 最后把基準(zhǔn)跟中點交換一下, 再遞歸對左右部分進(jìn)行同樣的方法排序, 直到所有有序. 那么怎么實現(xiàn)基準(zhǔn)后的元素左小右大呢, 可以用雙指針的方法.

2. 算法實現(xiàn)

2.1 遞歸實現(xiàn)

void quikSort(vector<int>& nums, int start, int end) {if (start >= end)return;int mark = nums[start];int left = start + 1;int right = end;while (left < right) {if (nums[left] <= mark) {left ++;continue;}if (nums[right] >= mark) {right --;continue;}swap(nums[left], nums[right]);}if (nums[left] > mark)left --;swap(nums[start], nums[left]);quikSort(nums, start, left - 1);quikSort(nums, left + 1, end); } vector<int> sortArray(vector<int>& nums) {int n = nums.size();quikSort(nums, 0, n - 1);return nums; }

2.2 迭代實現(xiàn)

vector<int> sortArray(vector<int>& nums) {int n = nums.size();if (n < 2)return nums;queue<pair<int, int>> sort_q;sort_q.push(make_pair(0, n - 1));while (!sort_q.empty()) {int start = sort_q.front().first;int end = sort_q.front().second;sort_q.pop();int left = start + 1;int right = end;while (left < right) {if (nums[left] < nums[start])left ++;else if (nums[right] > nums[start])right --;else {swap(nums[left], nums[right]);}}if (nums[left] > nums[start])left --;swap(nums[start], nums[left]);if (left - 1 > start)sort_q.push(make_pair(start, left - 1));if (left + 1 < end)sort_q.push(make_pair(left + 1, end));}return nums; }

總結(jié)

以上是生活随笔為你收集整理的排序算法 --- 快速排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。