今天看剑指offer突然发现下学期都要去面试了，还没自己实现过快排非递归和归并非递归，这怎么能行呢，于是就写了一下。 （虽然有点卡壳，又回去翻了下算导，还是顺利写出来了） 先放图： 一亿数据量：
#pragma warning(disable:4996) #include <iostream> #include <string> #include <cctype> #include<vector> #include<list> #include<cstring> #include<typeinfo> #include<set> #include<map> #include<deque> #include<regex> #include<sstream> #include<cstdlib> #include<queue> #include<stdlib.h> #include<stdio.h> #include<stack> #include<algorithm> #include<thread> #include<mutex> #include<assert.h> using namespace std; void MergeSort(vector<int>& nums) { if (nums.empty()) { return; } int len = nums.size(); vector<int> temp(len, 0); //临时数组，下面会用 for (int merge_step = 1; merge_step < len; merge_step <<= 1)//当merge_step为k，表示merge两个长度k的有序序列成一个长度2k的序列 { for (int begin = 0; begin < len - merge_step; begin += (merge_step << 1)) { int le = begin, ri = begin + merge_step; //左右区间起点 int le_end = ri, ri_end = min(ri + merge_step, len); //左右区间终点（半闭半开区间） int i = 0; while (le < le_end and ri < ri_end) { if (nums[le] < nums[ri]) { temp[i] = nums[le]; ++le; } else { temp[i] = nums[ri]; ++ri; } ++i; } while (le < le_end) { temp[i] = nums[le]; ++i; ++le; } while (ri < ri_end) { temp[i] = nums[ri]; ++i; ++ri; } for (int j = 0; j < i; ++j) //写回原数组 { nums[begin + j] = temp[j]; } } } } void InitiateRandomVector(vector<int>& nums) { srand(0); for (auto& num : nums) { num = rand(); } } int partition(vector<int>&nums,int le,int ri) //划分区间函数 { srand(0); int rand_num=le+rand()%(ri-le); //随机生成一个索引 swap(nums[ri],nums[rand_num]); //换到结尾 int stable=nums[ri]; int i=le-1,j=le; while(j<ri) { if(nums[j]<stable) { int temp=nums[j]; nums[j]=nums[++i]; nums[i]=temp; //i存的都是小于基准数的值 } ++j; } swap(nums[i+1],nums[ri]); return i+1; //返回基准数的索引 } void quick_sort(vector<int>& nums,int le,int ri) //[le,ri]闭区间 { if(le>=ri) { return; } int mi=partition(nums,le,ri); quick_sort(nums,le,mi-1); quick_sort(nums,mi+1,ri); } void QuickSort_Recursion(vector<int>& nums) //递归版 { quick_sort(nums,0,nums.size()-1); } void QuickSort_Iteration(vector<int>&nums) //迭代版 { if(nums.empty()) { return; } stack<int> sta; sta.push(0); sta.push(nums.size()-1); int le,ri,mi; while(!sta.empty()) { ri=sta.top(); //后push的右边界故先pop sta.pop(); le=sta.top(); sta.pop(); mi=partition(nums,le,ri); if(mi-1>le) { sta.push(le); sta.push(mi-1); } if(mi+1<ri) { sta.push(mi+1); sta.push(ri); } } } int main(int argc, char** argv) { cout<<"Input data size:"; int siz; cin>>siz; vector<int>nums(siz); cout<<"Data size:"<<siz<<endl; InitiateRandomVector(nums); int t1=time(0); MergeSort(nums); cout<<"My merge sort time:"<<time(0)-t1<<"s"<<endl; InitiateRandomVector(nums); t1=time(0); QuickSort_Recursion(nums); cout<<"My quick sort(recursion) time:"<<time(0)-t1<<"s"<<endl; InitiateRandomVector(nums); t1=time(0); sort(nums.begin(),nums.end()); cout<<"STL sort time:"<<time(0)-t1<<"s"<<endl; InitiateRandomVector(nums); t1=time(0); QuickSort_Iteration(nums); cout<<"My quick sort(iteration) time:"<<time(0)-t1<<"s"<<endl; getchar(); return 0; }