Write a c++ program to Quick Sort Algorithm -- Part II.


動機:
對於 Quick Sort 排序演算法(其加速在於軸的選擇),
再要求你寫個 C++ function,
要如何寫呢?!

說明:
利用 Code::Blocks 10.05 免費軟體,
再撰寫相關的程式即可達成要求, 程式碼如下: 



#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX 10
#define SWAP(x, y) { int t; t = x; x = y; y = t; }

using namespace std;

void quickSort(int[], int, int);
void printArray(int[]);

int main(void)
{
    // 產生一個新的亂數數列
    srand(time(NULL));

    // 宜告10個數字之陣列, 並清空
    int number[MAX] = {0};

    // 產生 1-99 的亂數, 並取 10 個數字
    for(int i = 0; i < MAX; i++)
        number[i] = (rand() % 99) + 1;

    printf("排序前：");
    printArray(number);

    // 執行 Quick Sort 演算法
    quickSort(number, 0, MAX - 1);

    printf("排序後：");
    printArray(number);

    return 0;
}

// Quick Sort algorithm
void quickSort(int number[], int left, int right)
{
    if(left < right)
    {
        int s = number[ (left + right) / 2 ];  // 將軸s設定為中間的元素
        int i = left - 1;
        int j = right + 1;

        while( 1 )
        {
            while( s > number[++i] );  // 向右找比s大的索引 i
            while( s < number[--j] );  // 向左找比s小的索引 j

            if( i >= j )
                break;  // 離開迴圈

            SWAP( number[i], number[j] );  // 交換 索引i 與 j 兩處的值
        }

        quickSort( number, left, i - 1 );   // 對左邊進行遞迴

        quickSort( number, j + 1, right );  // 對右邊進行遞迴
    }
}

// 將陣列元素輸出
void printArray(int number[])
{
    for(int i = 0; i < MAX; i++)
        printf("%02d ", number[i]);  // 表示右切齊最少印2位,不足處補0

    printf("\n");
}

參攷: Algorithm Gossip: 快速排序法（二）

執行檔下載連結: https://docs.google.com/open?id=0B_4eUrknq7N1ZTY1NzMyYTgtODYzMS00NzhiLTk5OTYtMTZlNDA0NGI4OGU3

留言

張貼留言