c++ - 带堆栈的非递归快速排序

Question

我正在尝试用堆栈实现快速排序，这里是代码

#include <iostream>
#include <cstdlib>
using namespace std;
template<class Item>
class STACK{
private:
    Item *a;int n;
public:
    STACK(int maxN){

        a=new Item[maxN];n=0;

    }
    int empty()const {
        return n==0;

    }
    void push(Item item){
        a[n++]=item;
        }
   Item pop() {
        return a[--n];

   }


};
template<class Item>
int partition (Item a[],int l,int r){

    int i=l-1;
    int j=r;
    Item v=a[r];
     for (;;){

          while (a[++i]<v);
          while (v<a[--j])  if (j==i) break;
           if (i>=j) break;
            Item t=a[i];
            a[i]=a[j];
            a[j]=t;
     }

      Item s=a[i];
       a[i]=a[r];
       a[r]=s;
       return i;
       }
inline void push2(STACK<int>&s,int a,int b){
    s.push(b);
    s.push(a);
    }

template<class Item>
  void quicksort(Item a[],int l,int r){

       STACK<int> s(50);
       push2(a,l,r);
       while (!s.empty()){
           int l=s.pop();
           int r=s.pop();
              if (r<=l) continue;
              int i=partition(a,l,r);
               if(i-1>r-1)
               { push2(a,l,i-1);  push2(a,i+1,r);
               }
               else{
                   push2(a,i+1,r);
                   push2(a,l,i-1);



               }

       }



  }

int main(){

    int a[]={45,12,30,67,11,17,50,78};
    int n=sizeof(a)/sizeof(a[0]);
    quicksort(a,0,n-1);
     for (int i=0;i<n;i++)
         cout<<a[i]<< "  ";




     return 0;

}

但是这里有错误

------ Build started: Project: sort_stack, Configuration: Debug Win32 ------
1>  sort_stack.cpp
1>c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(65): error C2664: 'push2' : cannot convert parameter 1 from 'int []' to 'STACK<Item> &'
1>          with
1>          [
1>              Item=int
1>          ]
1>          c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(92) : see reference to function template instantiation 'void quicksort<int>(Item [],int,int)' being compiled
1>          with
1>          [
1>              Item=int
1>          ]
1>c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(72): error C2664: 'push2' : cannot convert parameter 1 from 'int []' to 'STACK<Item> &'
1>          with
1>          [
1>              Item=int
1>          ]
1>c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(72): error C2664: 'push2' : cannot convert parameter 1 from 'int []' to 'STACK<Item> &'
1>          with
1>          [
1>              Item=int
1>          ]
1>c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(75): error C2664: 'push2' : cannot convert parameter 1 from 'int []' to 'STACK<Item> &'
1>          with
1>          [
1>              Item=int
1>          ]
1>c:\users\david\documents\visual studio 2010\projects\sort_stack\sort_stack.cpp(76): error C2664: 'push2' : cannot convert parameter 1 from 'int []' to 'STACK<Item> &'
1>          with
1>          [
1>              Item=int
1>          ]
========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped ==========

请帮忙

Answer 1

  void quicksort(Item a[],int l,int r){

       STACK<int> s(50);
       push2(a,l,r);

push2 接受STACK，你给了数组a。

不要自己实现堆栈，使用std::stack .