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; }