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


動機:
對於 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 i = left;
        int j = right + 1;

        while( 1 )
        {
            // 向右找 ++i, 直到找到大於 number[left]=s 的數
            while( (i + 1 < MAX) && (number[left] > number[++i]) ) ;  // number[left] = s = 左側的軸

            // 向左找 --j, 直到找到小於 number[left]=s 的數
            while( (j - 1 > -1) && (number[left] < number[--j]) ) ;

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

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

        SWAP( number[left], number[j] );  // 交換 左側的軸s 與 j 兩處的值

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

        quickSort( number, i, right );  // 對軸s右邊進行遞迴
    }
}

// 將陣列元素輸出
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_4eUrknq7N1ZTdmOTY3NmQtMDIxMS00ODViLTk4MTEtZjYwNTRlZGIyMmMy

留言

張貼留言