快速排序非递归版的空间复杂度疑惑
快速排序如果用递归版的写，排序数组一大，就Stack Overflow
所以我参照网上的，写了非递归的（C++代码）：
template<class T>int Partition(T* a,int left,int right){ T pivot = *(a+right); while(left<right) { while(*(a+left)<pivot && left<right) left++; if(left<right) *(a+right--) = *(a+left); while(*(a+right)>pivot && left<right) right--; if(left<right) *(a+left++) = *(a+right); } *(a+left) = pivot; return left;}template<class T>void QSort(T *arr, int len){ if(len == 1) return; int left = 0; int right = len - 1; int *stack = new int[right-left+2]; int top = 0; int mid; stack[top++] = left; stack[top++] = right; while(top>0) { right = stack[--top]; left = stack[--top]; if(left<right) { mid = Partition(arr,left,right); if(mid-left > right-mid) { stack[top++] = left; stack[top++] = mid-1; if (right > mid) { stack[top++] = mid + 1; stack[top++] = right; } } else { stack[top++] = mid + 1; stack[top++] = right; if(mid > left) { stack[top++] = left; stack[top++] = mid - 1; } } } } delete[] stack; stack = NULL;}// 123.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#include <vector>#include <windows.h>#include <ctime>#include <algorithm>using namespace std;//typedef std::vector<int>& VT;typedef int* VT;//递归调用次数太多 栈溢出！void quick_sort_rec(int *a,int low,int high);//非递归版 --迭代void quick_sort(int *base,int start,int end);//int _t;inline void _swap_kn(int & a,int & b){ int _t; _t = a; a = b; b = _t;}inline void _insert_sort_kn(VT v,unsigned int org_beg,unsigned int org_nd){//插入排序 if(org_nd <= org_beg) return ; int *p; p = new int[org_nd - org_beg]; //p[0] = v[org_beg]; for(unsigned int x = 0;x < org_nd - org_beg;++x){ p[x] = v[org_beg + x]; for(unsigned int i = x;i;--i) if(p[i] < p[i - 1]) _swap_kn(p[i],p[i-1]); } for(unsigned int x = 0;x < org_nd - org_beg;++x) v[org_beg + x] = p[x]; delete [] p;}inline void _selet_sort_kn(VT v,unsigned int org_beg,unsigned int org_nd){//选择排序 for(unsigned int beg = org_beg,nd = org_nd;;++ beg,-- nd){ if(nd <= beg + 1 ){//数据长度不大于1 ,则返回 break; } if(nd - beg == 2){ if(v[nd - 1] < v[beg]) _swap_kn(v[beg],v[nd - 1]); break; } if(nd - beg == 3){ if(v[beg + 1] < v[beg])//前面两个排序 _swap_kn(v[beg],v[beg + 1]); if(v[beg + 2] < v[beg + 1])//前后两个排序/确定 v[beg + 2] 最大 _swap_kn(v[beg +1],v[beg + 2]); if(v[beg + 1] < v[beg])//确定剩下两个 _swap_kn(v[beg],v[beg + 1]); break ; } //beg,beg + 1,nd -2,nd -1 四个数中取极大极小值//beg,beg + x ,nd - 1 - x,nd -1 if(v[nd - 1] < v[beg]) _swap_kn(v[beg],v[nd - 1]); for(unsigned int x =1;;++x){ if(beg + x < nd - 1 - x){ //cout<<v[beg]<<" "<<v[beg + x]<<" "<<v[nd - 1 - x]<<" "<<v[nd -1]<<endl; if(v[nd - 1 - x] < v[beg + x]) _swap_kn(v[beg + x],v[nd - 1 - x]); if(v[beg + x] < v[beg]) _swap_kn(v[beg],v[beg + x]); if(v[nd - 1] < v[nd -1 - x]) _swap_kn(v[nd - 1 - x],v[nd - 1]); //cout<<v[beg]<<" "<<v[beg + x]<<" "<<v[nd - 1 - x]<<" "<<v[nd -1]<<endl; //cout<<endl; } else { if(beg + x == nd - 1 - x){ //cout<<v[beg]<<" "<<v[nd - 1 - x]<<" "<<v[nd -1]<<endl; if(v[beg + x] < v[beg]) _swap_kn(v[beg],v[beg + x]); if(v[nd - 1] < v[nd - 1 - x]) _swap_kn(v[nd - 1 - x],v[nd -1]); if(v[beg + x] < v[beg]) _swap_kn(v[beg],v[beg + x]); //cout<<v[beg]<<" "<<v[nd - 1 - x]<<" "<<v[nd -1]<<endl; } break; } } }}inline void _sort_kn(VT v,unsigned int org_beg,unsigned int org_nd){ if(org_nd <= org_beg) return; //无效数据,直接返回 if(org_nd - org_beg <= 32){ //insert_sort_kn(v,org_beg,org_nd); _selet_sort_kn(v,org_beg,org_nd); return ; } int iVal = v[rand()%(org_nd - org_beg) + org_beg]; unsigned int min_top,max_beg; //min_top = 0; for(unsigned int x = org_beg,y = org_nd;;){ while(x < y)//x 不可能大于org_nd,不需要这个边界 if(v[x] < iVal) ++x; else break; //这里返回相等,说明x左边的数都是小于iVal的 while(x < y)//y - 1 不可能小于org_beg,不需要这个边界,y - 1 == x 是有可能的的. if(!(v[y -1] < iVal)) -- y; else break; //这里返回相等,则说明剩余的数都不小于iVal的,这时末端迭代器y - 1之后的应该都是不小于iVal的 //y - 1指向的应该是x的前一个,即 y-1 == x - 1即x== y //即当x == y时, x 是min的末端迭代器,y - 1是不小于的末端迭代器,即y是指向最开始一个不小于iVal的数 if(x == y){//如果是由于在剩余范围内没有了不小于iVal的数据,即确定min_top边界为此时的x min_top = x; break; } // x y-1 不可能取等值,一个数步可能同时小于又不小于一个数. // if(x < y - 1 && 1 < y){//1<y 即 y - 1 > 0 ,保证y - 1 是有效值 ,x < y - 1 即不小于值在左边,不小于值在右边,该数据有效 //前面已经保证了迭代器指向是必然有效的,因此 条件判断取消 _swap_kn(v[x],v[y-1]); } //max_beg = org_nd; for(unsigned int x = min_top,y = org_nd;x != org_nd;){ while(x < y) if(v[x] == iVal) ++ x;//查找最开始一个不等于iVal的数. else break; //(x == y)说明剩余的都是相等 //x返回的是第一个不相等的数,如果后面没有了数据,则返回末端迭代器 while (x < y) if(v[y -1] != iVal) -- y;//查找最后一个等于iVal的数 else break; if(x == y){//如果返回相等的末端迭代器,则确定max_beg边界. max_beg = x; break; } _swap_kn(v[x],v[y-1]); } _sort_kn(v,org_beg,min_top);//这里判断下两者的次序,则可以实现尾递归. _sort_kn(v,max_beg,org_nd);}void sort_kn(VT v,unsigned int n){ _sort_kn(v,0,n);}int _tmain(int argc, _TCHAR* argv[]){ Sleep(10); srand((unsigned int) time(NULL)); const unsigned int n = 10000000; //cin >>n; vector<int> a; a.resize(n); int *b = new int[n]; int *c = new int[n]; int *d = new int[n]; for(unsigned int x = 0;x < n;++x) a[x] = rand(); for(unsigned int x = 0;x < n;++x){ b[x] = a[x]; c[x] = a[x]; d[x] = a[x]; } time_t t; //for(unsigned int x = 0;x < n;++x) // cout<<a[x]<<" "; //cout<<endl; for(unsigned int x = 0;x < n; ++x){ if(b[x] != d[x]){ cout<<"原始数据部正确"<<endl; break; } } t = clock(); //for(unsigned int x = 0;x < 100;++x) sort(b,b + n ); //sort(b.begin(),b.end()); cout<<"STL sort花费时间"<<clock() - t<<endl; //cout<<"STL sort"<<endl; //for(unsigned int x = 0;x < n;++x) // cout<<b[x]<<" "; //cout<<endl; t = clock(); //for(unsigned int x = 0;x < 100;++x) //sort(b,b+n); sort_kn(c,n); cout<<"sort_kn花费时间"<<clock() - t<<endl; // for(unsigned int x = 0;x < n;++x) // cout<<a[x]<<" "; // cout<<endl; t = clock(); //heap_sort(d,n);cout<<"heap_sort花费时间"<<clock() - t<<endl; // for(unsigned int x = 0;x < n;++x) // cout<<a[x]<<" "; // cout<<endl; for(unsigned int x = 0;x < n;++x) if(b[x] !=c[x]){ cout<<"算法不正确"<<endl; /* cout<<"STL sort"<<endl; for(unsigned int x = 0;x < n;++x) cout<<b[x]<<" "; cout<<endl; cout<<"测试程序"<<endl; for(unsigned int x = 0;x < n;++x) cout<<d[x]<<" "; cout<<endl; */ break; } delete [] b; delete [] c; delete [] d; return 0;}