Leo 發問時間: 電腦與網際網路程式設計 · 1 0 年前

C++ Heap sort

麻煩會的大大幫寫一個 heap sort 的程式

輸入數值,第一個數為 n ,輸入幾個數,n就有幾個,但不包括自己 ( n-1 )

輸入的第二個數值開始做 heap sort 排序....

輸出結果如 : 5,7,8,9,10,11 ( 5為共排序幾個數值 )

好心解答的大大,解答完麻煩告知一下,是用c++哪種平台寫的..感恩

ps...如果你只是進來看看,也非常謝謝你

已更新項目:

先謝謝dava和無憂大大的解答

我問題表達的不太好~sorry....抱歉各位

不好意思,我說的題目有錯,輸出那個是輸入才對

回但願大大.....老師說我也搞不太懂....

如 : 輸入5個數為5,7,8,9,10,11

第一個輸入的數為共有幾個要排序的數,5就代表7~11有5個數要排序

7~11做 heap sort 排序,輸出只須輸出7~11的 heap sort 而已

老師也只是口頭說題目,課本也沒有題目,原文我更是霧煞煞

so~抱歉沒有輸出的例子...

3 個解答

評分
  • Dave
    Lv 7
    1 0 年前
    最佳解答

    // 下面的 code 來自 http://linux.wku.edu/~lamonml/algor/sort/heap.html

    //=============================

    void siftDown(int numbers[], int root, int bottom)

    {

    int done, maxChild, temp;

    done = 0;

    while ((root*2 <= bottom) && (!done))

    {

    if (root*2 == bottom)

    maxChild = root * 2;

    else if (numbers[root * 2] > numbers[root * 2 + 1])

    maxChild = root * 2;

    else

    maxChild = root * 2 + 1;

    if (numbers[root] < numbers[maxChild])

    {

    temp = numbers[root];

    numbers[root] = numbers[maxChild];

    numbers[maxChild] = temp;

    root = maxChild;

    }

    else

    done = 1;

    }

    }

    void heapSort(int numbers[], int array_size)

    {

    int i, temp;

    for (i = (array_size / 2)-1; i >= 0; i--)

    siftDown(numbers, i, array_size);

    for (i = array_size-1; i >= 1; i--)

    {

    temp = numbers[0];

    numbers[0] = numbers[i];

    numbers[i] = temp;

    siftDown(numbers, 0, i-1);

    }

    }

    // 結束來自 http://linux.wku.edu/~lamonml/algor/sort/heap.html 的 code

    //===========================================================

    void main()

    {

    int n;

    cin >> n;

    int* intArray = new int[ n ]; // 看使用者要 sort多少個int,就建立多大的array

    for( int i =0; i<n ; i++)

    cin >> intArray[ i ]; // 把要被 sort 的數字讀進 array

    heapSort( intArray, n ); // 叫網站上的 heapsort

    cout << "Sorted (" << n << " elements)\n" ; // 輸出答案

    for( int i=0; i<n; i++)

    cout << intArray[ i ] << " ";

    delete intArray; // 釋放記憶體

    system("pause");

    }

    2006-08-14 19:37:37 補充:

    真的啊?有沒有test-case啊?我來trace-看看

    2006-08-15 13:44:08 補充:

    嗯,無憂,你是怎樣測試數字是否有在sort 前跟 sort 後的陣列中的呢?有無你那時出錯的 test code? 我剛跑了一下,好像沒什麼問題

    2006-08-15 13:52:50 補充:

    我的 test code,sort 1000次結果沒問題…

    int countArray(int arr[], int n, int t)

    {

    int cnt = 0;

    for(int i=0;i<n; i++)

    if(arr[i] == t) cnt++;

    return cnt;

    }

    int copies[NUM_ITEMS];

    int comp[NUM_ITEMS];

    2006-08-15 13:53:13 補充:

    int main()

    {

    int i;

    //seed random number generator

    srand( time(0) );

    //fill array with random integers

    for(int j=0;j<1000;)

    {

    printf("pass %d\n", ++j);

    for (i = 0; i < NUM_ITEMS; i++)

    {

    numbers[i] = rand();

    copies[i] = numbers[i];

    }

    2006-08-15 13:53:37 補充:

    for (i = 0; i < NUM_ITEMS; i++)

    {

    comp[i] = countArray(numbers,NUM_ITEMS,copies[i]);

    }

    heapSort(numbers, NUM_ITEMS);

    2006-08-15 13:53:43 補充:

    for (i = 0; i < NUM_ITEMS; i++)

    {

    if( comp[i] != countArray(numbers, NUM_ITEMS,copies[i]) )

    {

    printf("Failed\n");

    exit(0);

    }

    }

    }

    system("pause");

    }

  • 無憂
    Lv 4
    1 0 年前

    dave 兄:http://linux.wku.edu/~lamonml/algor/sort/heap.html 的 code

    似乎有些問題,有時候會出現不屬於陣列中的數值。不然其實我也想用那個code來回答的說><

    2006-08-14 18:57:11 補充:

    其實知識+裡面有其他的寫法,但我想還是PO一下好了。參考資料的程式版><

    PS.請不要移除阿QQ

    -------------------------------------------------

    以下原始碼請用Dev-C++編譯

    #include<iostream>

    using namespace std;

    void Max_Heapify(int numbers[],int i,int size)

    {

    int l,r,largest,temp;

    l=2*i+1;

    r=2*i+2;

    if(l<size&&numbers[l]>numbers[i])

    largest=l;

    else

    largest=i;

    if(r<size&&numbers[r]>numbers[largest])

    largest=r;

    if(largest!=i)

    {

    temp=numbers[i];

    numbers[i]=numbers[largest];

    numbers[largest]=temp;

    Max_Heapify(numbers,largest,size);

    }

    return;

    }

    void Build_Max_Heap(int numbers[],int size)

    {

    int i;

    for(i=(size-1)/2;i>=0;i--)

    Max_Heapify(numbers,i,size);

    }

    void HeapSort(int numbers[],int length)

    {

    int i,temp,size;

    Build_Max_Heap(numbers,size=length);

    for(i=length-1;i>0;i--)

    {

    temp=numbers[i];

    numbers[i]=numbers[0];

    numbers[0]=temp;

    Max_Heapify(numbers,0,--size);

    }

    }

    int main()

    {

    int n;

    cout<<"請輸入要排序的數量:";

    cin >> n;

    int* Numbers = new int[n];

    for( int i =0; i<n ; i++)

    {

    cout<<"第"<<i+1<<"個數字:";

    cin >> Numbers[ i ];

    }

    HeapSort( Numbers, n );

    cout << "共有" << n << "個數字做排序\n排序結果為:" ;

    for( int i=0; i<n; i++)

    cout << Numbers[ i ] << ",";

    cout<<"\b \n";

    delete Numbers;

    system("pause");

    }

    2006-08-15 08:58:56 補充:

    test-case的話看一下

    http://tw.knowledge.yahoo.com/question/?qid=130603...

    雖然他用C寫的,但我想應該不至於因為這樣出錯,除非我的編譯器有錯@@

    我測了後發現有不只一次出現就不用這個code了。

    2006-08-15 16:18:23 補充:

    這樣喔@@

    那看來不是我的編譯器有錯就是ram有問題了,用了你的test code平均不到10次就fail ...

    2006-08-15 17:03:36 補充:

    剛剛debug了一下(其實我最不想做這件事><)

    發現那網址的heapSort這函數的第三行要改才會對

    改成

    siftDown(numbers, i, array_size-1);

    參考資料: www.nctu.edu.tw/~claven/course/Algorithm/unit06.ppt
  • 1 0 年前

    能說明的更詳細點嗎?尤其是範例

    輸入數值,第一個數為 n ,輸入幾個數,n就有幾個,但不包括自己 ( n-1 )

    輸入的第二個數值開始做 heap sort 排序....

    輸出結果如 : 5,7,8,9,10,11 ( 5為共排序幾個數值 )

    2006-08-15 11:48:04 補充:

    如 : 輸入5個數為5,7,8,9,10,11??

    第一個應該不算在5個數字內吧?

    題目應該是輸入數字n,接著才輸入n個數字做排列,所以

    輸入數值,第一個數為 n ,輸入幾個數,n就有幾個,但不包括自己 ( n-1 ) 應該是(n+1)才對吧

還有問題?馬上發問,尋求解答。