快速排序非递归版的空间复杂度疑惑,该怎么解决

快速排序非递归版的空间复杂度疑惑
快速排序如果用递归版的写，排序数组一大，就Stack Overflow
所以我参照网上的，写了非递归的（C++代码）：

C/C++ code



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;
}

本来快速排序的空间复杂度是O（log2n）
可我代码其中这句：int *stack = new int[right-left+2];还要分配一个很大的空间，
特别是当数组很大的时候，比如1亿个数时，
如果我用来排序的数组是char的，而分配的这段内存是int的，大出来的空间是数组本身的好几倍
我要怎么去修改呢？

------解决方案--------------------
int *stack = new int[right-left+2];
这个空间复杂度是o（n）的。
不过实际用到的还是logn级别因为栈的最大深度是logn级别。
------解决方案--------------------
快速排序如果用递归版的写，排序数组一大，就Stack Overflow
================================================================
栈溢出的主要原因不是因为递归，而是因为快速排序没有随机选中间数吧？
如果用递归方法快速排序排到有序的数据，就会占用O(n)的栈空间，确实有可能栈溢出。
但是选用了合适的中间数，则O(lgN)的栈空间，不太可能溢出吧。
lg(1亿) 还不到30，怎么可能溢出呢？
------解决方案--------------------

探讨
如果我排序的数据类型是char（1个字节）
可这个stack是用int（4个字节）来初使的
空间复杂度又怎么看？

------解决方案--------------------
在最坏情况下，比如数组是有序的，数组元素是递增或者递减的，使用传统的选择枢轴的做法，左右两个分区其中之一只有一个元素。这样递归的深度非常大，可导致内存不足。解决方法有：

1. 枢轴去三个元素的中间值，三个元素是最左，最右，和中间的元素。
2. 随机选择枢轴，不过，这种做法可能降低排序的速度。

------解决方案--------------------
如果说纯粹的纯粹非递归实现的快排,大致也就这样了.
当然可以不用把最后一部分不压入栈内.

大体的快速排序结构就是这样的了.

剩余的就是如何优化问题
(虽然说是优化,但是可能平均性能有数量级上的提升)

我了解到的优化方式大致有几个.
1: 短长度的使用更基础的排序,
2: 优化选取中值的算法, 如何选择,我知道的有,通过随机选择(也就是10楼提到的随机快速排序),通过小样品进行选择中值.
或者是这两种的综合.
3:可能的话减少数据交换的次数.

每种方式似乎都是以稍微多点的额外操作,
换取平均性能的提高.如何恰当地使用那些技术似乎得靠自己测试.

------解决方案--------------------
这个是以前学的时候遗留下的代码.
比较纯粹的随机快速排序.
风格还很幼稚.
而且没有使用尾递归,
只是概率上保证堆栈不溢出.
速度似乎比STL的慢5%-10%左右.

C/C++ code


// 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;
}

快速排序非递归版的空间复杂度疑惑,该怎么解决

相关推荐