十種基本排序算法

文章目錄

• • 十種基本排序算法
  • 一、復雜度分析
  • 二、實現
  • • 插入排序
    • 希爾排序
    • 選擇排序
    • 堆排
    • 冒泡排序
    • 快速排序hoare版本
    • 快速排序挖坑版本
    • 快速排序雙指針版本
    • 快排非遞歸版本
    • 歸并排序
    • 計數排序

一、復雜度分析

二、實現

插入排序

class Solution { public:vector<int> sortArray(vector<int>& nums) {/*插入排序：主要思想：假定一個位置end，end位置之前（包括end位置）的所有元素已經有序，end位置后的元素待判斷；1:如果end之后位置的元素比end位置的元素大，不用往前插2:如果end之后位置的元素比end位置的元素小，需要往前插入到一個合適的位置（斗地主）*///排除特殊情況if(nums.empty()){return {};}//遍歷，每次比較當前元素和下一個元素，所以只需要到size - 1即可for(size_t i = 0;i < nums.size() - 1;i++){//end 為完成排序到最后一個元素下表，即end包括end之前到所有元素已經是有序的int end = i;//temp為end下一個位置的元素，即待判斷的元素（判斷temp元素和有序序列最后一個//位置的元素的大小）int temp = nums[end + 1];//1.temp剛好大于等于end位置的元素，我們求的是升序，滿足情況，不進循環，執行://nums[i + 1] = temp,相當于什么也沒做，因為temp 也等于 nums[i+ 1]//2.temp剛好小于end位置的元素，代表后一個位置的元素小于前一個位置的元素，我們求的//是升序，不滿足情況，進入循化；把當前end位置的元素往end + 1位置進行搬移//，繼續判斷是否滿足情況，直到找到一個temp大于等于end位置元素的情況，即：//nums[?] < 或者 <= temp，直接把nums[end + 1]位置的元素值為temp即可，//（因為走到end這個位置，說明原來nums中end + 1位置的元素是大于等于temp的，//所以原來end + 1位置的元素肯定已經完成拷貝，所以可以直接復制）while(end >= 0 && nums[end] > temp){nums[end + 1] = nums[end];end--;}nums[end + 1] = temp;}return nums;} };

希爾排序

class Solution { public:vector<int> sortArray(vector<int>& nums) {/*希爾排序：主要思想：在插入排序的基礎上加一個組gap，對每個gap進行插入排序。gap的值是動態遞減的，直到gap = 1時就是插入排序*/if(nums.empty()){return {};}//不能直接些gap = nums.size() / 3 - 1int gap = nums.size();//不能寫成大于 0,因為 gap的值始終>=1while(gap > 1){//只有gap 最后為1， 才能保證最后有序//所以這里要加1gap = gap / 3 + 1;//這里只是把插入排序的1 換成gap 即可//但是這里不是排序完一個分組， 再去排序另一個分組， 而是整體只過一遍//這樣每次對于每組數據只排一部分//整個循環結束之后， 所有組的數據排序完成//結束條件由size - 1變為size - gap，因為組的大小就是gap早size - gap時已經完成//size - 1位置元素的判斷for (int i = 0; i < nums.size() - gap;++i){//同樣標記最后一個有序元素的下標int end = i;//同組帶判斷的下一個元素int temp = nums[end +gap]; while (end >= 0 && nums[end] >temp){nums[end + gap] = nums[end];end -= gap;} nums[end + gap] = temp; } }return nums;} };

選擇排序

class Solution { public:vector<int> sortArray(vector<int>& nums) {/*選擇排序（優化版）主要思想：一趟遍歷選擇一個最大的元素和一個最小的元素，并把最小的元素放在該趟排序的開始位置，把最大元素放在該趟排序的結束位置*/if(nums.empty()){return {};}//每趟循環查找的開始和結束位置int begin = 0;int end = nums.size() - 1;while(begin < end){//每趟循化結束后，最大和最小元素的下標int max_data_index = begin;int min_data_index = begin;for(int i = begin;i <= end;i++){//找最大元素下標if(nums[max_data_index] < nums[i]){max_data_index = i;}//找最小元素下標if(nums[min_data_index] > nums[i]){min_data_index = i;}}//把最小元素下標位置的元素放到該趟循化的開始位置swap(nums[begin],nums[min_data_index]);//有一種特殊情況，剛好最大元素的下標在該趟循化的開始位置//經過上面的交換之后，最大元素的下標被交換到min_data_index處，//需要注意if(max_data_index == begin){max_data_index = min_data_index;}//把最大元素下標位置的元素放到該趟循化的結束位置swap(nums[end],nums[max_data_index]);begin++;end--;}return nums;} };

堆排

class Solution { public://堆排的向下調整，beign代表在哪里開始調整void AdjustDown(vector<int>& nums,int begin){//父親下標索引int parent = begin;//孩子下標索引int child = parent * 2 + 1;while(child < nums.size()){//找到左右孩子中最大的一個下標if(child + 1 < nums.size() && nums[child] < nums[child + 1]){child = child + 1;}//判斷孩子是否大于父親//大于就交換if(nums[child] > nums[parent]){swap(nums[child],nums[parent]);parent = child;child = parent * 2 + 1;}//小于說明已經是一個堆了，可以直接return，因為我們在建堆的時候是//從下往上建的else {break;}}}vector<int> sortArray(vector<int>& nums) {/*堆排：主要思想：升序建大堆，每次把大堆的堆頂元素和堆中最后一個位置的元素交換（可以保證堆頂元素一定是所有元素中最大的，但是不能保證最后一個元素是對中最小的，所以才用這種交換方式進行排序）*/if(nums.empty()){return {};}//根據nuns中的元素建大堆//在數組中：//根據孩子索引下標推父親索引下標：parent = (child - 1) / 2;//根據父親索引下標推孩子索引下標：child = parent * 2 + 1 / parent * 2 + 2//建堆是從下往上建造的，即先找到最后一個非葉子結點在數組中的下標，即：//根據子推父：parent = (nums.size() - 1 - 1) / 2;//逐漸往上建，直到nuns[0]for(int i = (nums.size() - 1 - 1) / 2;i >= 0;i--){AdjustDown(nums,i);}//最后一個元素的位置int end = nums.size() - 1;//保存結果vector<int> ret(nums.size());//當nums中還有元素時while(end > 0){//把第一個和最后一個元素進行交換swap(nums[0],nums[end]);//把最大的元素加入結果集ret[end] = nums[end];//不讓最大的元素參加向下調整，因為其已經有序nums.pop_back();AdjustDown(nums,0);end-- ;}ret[0] = nums[0];return ret;} };

冒泡排序

class Solution { public:vector<int> sortArray(vector<int>& nums) {/*冒泡排序：主要思想：冒泡冒泡：顧名思義，一次冒出一個大的元素，其實和選擇排序差不多*/if(nums.empty()){return {};}//避免有序的情況bool flag = true;//i代表每次循化的終點，i即i之后的元素是有序的，每次從前秒找到一個最大的放到i - 1處for(size_t i = nums.size();i > 0;i--){//從0到i - 1中找最大for(size_t j = 1;j < i;j++){if(nums[j - 1] > nums[j]){flag = false;swap(nums[j - 1],nums[j]);}}//如果沒有進行一次交換說明nums本身就是有序的，直接beak掉if(flag){break;}}return nums;} };

快速排序hoare版本

class Solution { public://三數取中，避免有序的情況int GetMidIndex(vector<int>& nums, int begin, int end){int mid = begin + (end - begin) / 2;if(nums[begin] < nums[mid]){if(nums[mid] < nums[end]){return mid;}else if(nums[begin] > nums[end]){return begin;}else {return end;}}else {if(nums[mid] > nums[end]){return mid;}else if(nums[begin] < nums[end]){return begin;}else {return end;}}}//快速排序hoare版本int PartSort(vector<int>& nums, int begin, int end){//找到合適的keyint mid = GetMidIndex(nums,begin,end);swap(nums[mid],nums[begin]);int key = nums[begin];int start = begin;while(begin < end){//從后往前找比key小的while(begin < end && nums[end] >= key){end--;}//從前往后找比key大的while(begin < end && nums[begin] <= key){begin++;}//交換swap(nums[begin],nums[end]);}//交換，將nums[start]放到正確的位置swap(nums[start],nums[begin]);return begin;}//快排void QuickSort(vector<int>& nums, int left, int right){if(left >= right){return ;}//if(right - left + 1 < 10)//{// 插入排序//}//else {int mid = PartSort(nums,left,right);QuickSort(nums,left,mid - 1);QuickSort(nums,mid + 1,right);}}vector<int> sortArray(vector<int>& nums) { if(nums.empty()){return {};}QuickSort(nums,0,nums.size() - 1);return nums; } };

快速排序挖坑版本

class Solution { public://三數取中，避免有序的情況int GetMidIndex(vector<int>& nums, int begin, int end){int mid = begin + (end - begin) / 2;if(nums[begin] < nums[mid]){if(nums[mid] < nums[end]){return mid;}else if(nums[begin] > nums[end]){return begin;}else {return end;}}else {if(nums[mid] > nums[end]){return mid;}else if(nums[begin] < nums[end]){return begin;}else {return end;}}}//快速排序挖坑版本int PartSort(vector<int>& nums, int begin, int end){//找到合適的keyint mid = GetMidIndex(nums,begin,end);swap(nums[mid],nums[begin]);int key = nums[begin];while(begin < end){//從后往前找比key小的while(begin < end && nums[end] >= key){end--;}nums[begin] = nums[end];//從前往后找比key大的while(begin < end && nums[begin] <= key){begin++;}nums[end] = nums[begin];}//將key放到正確的位置nums[begin] = key;return begin;}//快排void QuickSort(vector<int>& nums, int left, int right){if(left >= right){return ;}//if(right - left + 1 < 10)//{// 插入排序//}//else {int mid = PartSort(nums,left,right);QuickSort(nums,left,mid - 1);QuickSort(nums,mid + 1,right);}}vector<int> sortArray(vector<int>& nums) {if(nums.empty()){return {};}QuickSort(nums,0,nums.size() - 1);return nums; } };

快速排序雙指針版本

class Solution { public://三數取中，避免有序的情況int GetMidIndex(vector<int>& nums, int begin, int end){int mid = begin + (end - begin) / 2;if(nums[begin] < nums[mid]){if(nums[mid] < nums[end]){return mid;}else if(nums[begin] > nums[end]){return begin;}else {return end;}}else {if(nums[mid] > nums[end]){return mid;}else if(nums[begin] < nums[end]){return begin;}else {return end;}}}//快速排序雙指針版本int PartSort(vector<int>& nums, int begin, int end){int key = nums[end];//后指針 int prev = begin - 1;//前指針int cur = begin;// 3 2 5 9 8 0 6// 3 2 5 0 6 9 8while(cur < end){//cur如果找到比key小的元素，就將cur和prev的元素互換if(nums[cur] < key){prev++;swap(nums[cur],nums[prev]);}//如果cur 所在下標的元素比key 所在元素大， 就直接后移curcur++;}//最后注意和end 位置的元素交換的是pref 的下一個,不是它自己swap(nums[end],nums[++prev]);return prev;}//快排void QuickSort(vector<int>& nums, int left, int right){if(left >= right){return ;}//if(right - left + 1 < 10)//{// 插入排序//}//else {int mid = PartSort(nums,left,right);QuickSort(nums,left,mid - 1);QuickSort(nums,mid + 1,right);}}vector<int> sortArray(vector<int>& nums) {if(nums.empty()){return {};}QuickSort(nums,0,nums.size() - 1);return nums; } };

快排非遞歸版本

class Solution { public://快速排序雙指針版本int PartSort(vector<int>& nums, int begin, int end){int key = nums[end];//后指針 int prev = begin - 1;//前指針int cur = begin;// 3 2 5 9 8 0 6// 3 2 5 0 6 9 8while(cur < end){//cur如果找到比key小的元素，就將cur和prev的元素互換if(nums[cur] < key){prev++;swap(nums[cur],nums[prev]);}//如果cur 所在下標的元素比key 所在元素大， 就直接后移curcur++;}//最后注意和end 位置的元素交換的是pref 的下一個,不是它自己swap(nums[end],nums[++prev]);return prev;}//快排非遞歸void QuickSortStack(vector<int>& nums, int left, int right){//用棧模擬遞歸stack<int> s;//往棧中放左右邊界if(left < right){s.push(right);s.push(left);}while(!s.empty()){//取左右邊界時要注意邊界的入棧順序left = s.top();s.pop();right = s.top();s.pop();//進行單趟排序獲取新的邊界int mid = PartSort(nums,left,right);//如果mid左邊還有2個元素及以上繼續入棧if(left < mid - 1){s.push(mid - 1);s.push(left);}//右邊同理if(right > mid + 1){s.push(right);s.push(mid + 1);}}}vector<int> sortArray(vector<int>& nums) {if(nums.empty()){return {};}QuickSortStack(nums,0,nums.size() - 1);return nums;} };

歸并排序

class Solution {void mergeSort(vector<int>& nums, int left, int right,vector<int>& tmp) {if (left >= right) return;int mid = (left + right) >> 1;mergeSort(nums, left, mid,tmp);mergeSort(nums, mid + 1, right,tmp);int begin1 = left;int end1 = mid;int begin2 = mid + 1;int end2 = right;int index = left;while (begin1 <= end1 && begin2 <= end2) {if (nums[begin1] < nums[begin2]) {tmp[index++] = nums[begin1++];}else {tmp[index++] = nums[begin2++];}}while (begin1 <= end1){tmp[index++] = nums[begin1++];} while (begin2 <= end2){tmp[index++] = nums[begin2++];} for (int i = 0; i < right - left + 1; ++i) nums[i + left] = tmp[i + left];} public:vector<int> sortArray(vector<int>& nums) {if(nums.empty()){return {};}vector<int> tmp(nums.size());mergeSort(nums, 0, (int)nums.size() - 1,tmp);return nums;} };

計數排序

class Solution { public:vector<int> sortArray(vector<int>& nums) {/*計數排序：主要思想：計數*/if(nums.empty()){return {};}map<int,int> mp;for(size_t i = 0;i < nums.size();i++){mp[nums[i]]++;}nums.clear();for(auto e : mp){for(int i = 0;i < e.second;i++){nums.push_back(e.first);}}return nums;} }; 超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的十种基本排序算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。