匯東網


C 程序設計 - 快速排序(以及 字符串比大小)

[編輯] [转简体]
|
作者:huidong | 分類:【編程】NOJ 和 C 程序設計習題
[ 6 瀏覽 0 評論 0 贊 0 踩 ]

概要

正文

第一版(純數字)

#include <stdio.h>

void print_arr(int* arr, int n)
{
    for (int k = 0; k < n; k++)
        printf("%d ", arr[k]);
    printf("\n");
}

inline void swap(int& a, int& b)
{
    int t = a;
    a = b;
    b = t;
}

inline bool cmp(const int& a, const int& b, const bool& greater)
{
    return greater ? a > b : a < b;
}

void Qsort(int* arr, int left, int right, bool greater)
{
    int i = left + 1, j = right;
    if (left >= right)
        return;
    while (i <= j)
    {
        if (cmp(arr[i], arr[left], greater))
            i++;
        else if (!cmp(arr[j], arr[left], greater))
            j--;
        else
            swap(arr[i], arr[j]);

        //print_arr(arr + left, right - left + 1);
    }
    swap(arr[left], arr[j]);
    //print_arr(arr + left, right - left + 1);

    Qsort(arr, left, j - 1, greater);
    Qsort(arr, j + 1, right, greater);
}

int main()
{
    //int A[6] = { 3,2,5,7,8,1 };
    int A[6] = { 3,4,4,4,4,5 };
    Qsort(A, 0, 5, true);

    print_arr(A, 6);
    return 0;
}

第二版(結合字符串比大小)

#include <stdio.h>

// 按字典順序對兩個字符串排序
// A ?> B
bool greater(const char* lpszA, const char* lpszB)
{
    int i = 0;
    while (lpszA[i] && lpszB[i] && lpszA[i] == lpszB[i])
        i++;
    return lpszA[i] > lpszB[i];
}

void swap(const char*& a, const char*& b)
{
    const char* t = a;
    a = b;
    b = t;
}

// 對字符串序列進行快排
void qsort_str(const char** arr, int left, int right)
{
    int i = left + 1, j = right;
    if (left >= right)
        return;
    while (true)
    {
        while (i <= right && !greater(arr[i], arr[left])) i++;        // 出循環時 i 可取到 left + 1 ~ right + 1
        while (j >= i && greater(arr[j], arr[left])) j--;            // 出循環時 j 可取到 left <= i - 1 ~ right

        // 第一個循環中 i 不斷正向搜索,只要 arr[i] 還 <= arr[left],i 就繼續前進。
        // 這個循環結束時,只有兩種可能:
        //        1. i = right + 1,i 來到了沒有數據的荒原
        //        2. arr[i] > left,i 找到了對手
        // 而在 i 的身後,從 left + 1 到 i - 1,全部都是 <= arr[left] 的廣袤土地。
        // 
        // 這個時候,j 就要逆向搜索了。
        // 若是 i 已在荒原,則 j 一開始,便處在了 i 後方,第二個循環未始便終。j 之所處,亦 <= arr[left],故可與基準調之。
        // 若是 i 尚處中原,則 i 之所處,j 必適之,故 j 若不停於 i 之後,則必停於 i - 1。
        //
        // j 既已停,若小於 i,則是冰火錯交,兩級已分,可止矣。
        // j 若大於 i,則是乾坤未定,尚處變中,可以將 i j 之值互換。
        // 
        // 特殊情況:
        //        {3, 1}   i 會搜出界,j 一起便終,與 3 換之爲 {1, 3},可也。
        //                 繼而求子列,從 j 而分,故有傳參 (left = 0, right = 0), (left = 2, right = 1),無怪矣。
        //        {3, 4}   i 停於起點,j 止於 3 處,與 3 換之爲 {3, 4},亦可也。
        //                 繼而求子列,從 j 而分,故有傳參 (left = 0, right = -1), (left = 1, right = 1),無怪矣。
        // 因此,函數之始當檢 left 與 right 之值也。若小大顛倒,則是時當知止也。
        //

        if (j > i)
            swap(arr[i], arr[j]);
        else
            break;
    }
    swap(arr[left], arr[j]);
    qsort_str(arr, left, j - 1);
    qsort_str(arr, j + 1, right);
}

void display(const char** arr, int sum)
{
    printf("******\n");
    for (int i = 0; i < sum; i++)
        printf("%d\t%s\n", i, arr[i]);
    printf("******\n\n");
}

int main()
{
    const int sum = 8;
    const char* strs[sum] = { "add","cos","boy","apple","bottom","application","as","coffee" };

    display(strs, sum);
    qsort_str(strs, 0, sum - 1);
    display(strs, sum);

    return 0;
}


[ 0] [ 0]


 評論區  0 條評論

+ 添加評論