[問題] quicksort程式出錯處

[lavanil (教授不要當我~)]

(程式碼在文章最後)

這是一個用quicksort排列使用者輸入的10個整數的程式

以quickSort遞迴函式呼叫partition函式進行排列

而每呼叫一次partition

會cout出排列以後的結果

我不清楚到底錯在哪邊

如果10個數輸入為
10 9 8 7 6 5 4 3 2 1

執行以後出現的東西將是

10  9  8  7  6  5  4  3  2  1
1  9  8  7  6  5  4  3  2  10
1  9  8  7  6  5  4  3  2  10
1  2  8  7  6  5  4  3  9  10
1  2  8  7  6  5  4  3  9  10
1  2  -842150451  7  6  5  4  3  9  10
1  2  -842150451  7  6  5  4  3  9  10
1  2  -842150451  -842150451  6  5  4  3  9  10
1  2  -842150451  -842150451  6  5  4  3  9  10
1  2  -842150451  -842150451  6  5  4  3  9  10

感覺那個-842150451 是記憶體位置?

那也就是說問題可能是出在b這個pointer囉?

可是還是不知道怎麼改 = =a  因為不知道怎麼錯的

如果輸入值為

37 2 6 4 89 8 10 12 68 45

卻可以順利輸出結果...

請各位神人救救我吧T.T

==============================================================================

#include <iostream>
using namespace std;

void quickSort(int a[], int subOFstart, int subOFend);
int partition(int *a , int arraysize);



int main()
{
        int num1,num2,num3,num4,num5,num6,num7,num8,num9,num10;

        cout<<"\nplaese key in num1"<<endl;
        cin>>num1;
        cout<<"\nplaese key in num2"<<endl;
        cin>>num2;
        cout<<"\nplaese key in num3"<<endl;
        cin>>num3;
        cout<<"\nplaese key in num4"<<endl;
        cin>>num4;
        cout<<"\nplaese key in num5"<<endl;
        cin>>num5;
        cout<<"\nplaese key in num6"<<endl;
        cin>>num6;
        cout<<"\nplaese key in num7"<<endl;
        cin>>num7;
        cout<<"\nplaese key in num8"<<endl;
    cin>>num8;
    cout<<"\nplaese key in num9"<<endl;
        cin>>num9;
        cout<<"\nplaese key in num10"<<endl;
    cin>>num10;
        cout<<endl;

        int a[10]={num1,num2,num3,num4,num5,num6,num7,num8,num9,num10};

    for(int i=0; i<=9; i++)
        cout<<a[i]<<"  ";
    cout<<endl;
        quickSort(a,0,9);
    return 0;
}

void quickSort(int a[], int subOFstart, int subOFend)
{

        if(subOFstart>=subOFend)
                return;

        int k=subOFend-subOFstart+1;
        int *b=new int[k];
    int s=0;
        for(int i=subOFstart; i<=k; i++)
        {
                b[s]=a[i];
                s++;
        }


        int subOFstandard=subOFstart+partition(b,k);


        int j=0;
        for(i=subOFstart; i<=k; i++)
        {
                a[i]=b[j];
                j++;
        }



        for(int h=0; h<10; h++)
        cout<<a[h]<<"  ";
    cout<<endl;




        quickSort(a,subOFstart,subOFstandard-1);
        quickSort(a,subOFstandard+1,subOFend);



}


int partition(int *a , int arraysize)
{
        int b;
        int subOFstandard=0;
        int subOFswap=arraysize;
    int k;

        while(k!=subOFstandard)
        {


                for(int i=subOFswap-1; i>=subOFstandard; i--)
                {
                        if (a[subOFstandard]<a[i])
                                continue;
                        if (a[subOFstandard]>a[i]){
                                subOFswap=subOFstandard;
                                b=a[i];
                                a[i]=a[subOFstandard];
                                a[subOFstandard]=b;
                                subOFstandard=i;
                                break;}
                        if (i==subOFstandard)
                                k=i;
                }




                for(i=subOFswap+1; i<=subOFstandard; i++)
                {
                        if (a[subOFstandard]>a[i])
                                continue;
                        if (a[subOFstandard]<a[i]){
                                subOFswap=subOFstandard;
                                b=a[i];
                                a[i]=a[subOFstandard];
                                a[subOFstandard]=b;
                                subOFstandard=i;
                                break;}
                        if (i==subOFstandard)
                                k=i;
                }



        }


        return k;
}

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.252.170
※ 編輯: lavanil         來自: 140.112.252.170      (01/04 10:44)
→ powerair:k=ubOFend-subOFstart+1 答案不是10嗎? a則是[10]
→ powerair:但你下面的迴圈是i <= k
推 powerair:以初始值(0,9)而言 qs()裡前二個迴圈存取就己超出陣列宣
→ powerair:告的範圍了   (解釋的真爛 = =")