Zi 字媒體

[C/C++ 演算法]- 快速排序法（一） 剛才找資料時發現一個C/C++的教學網站，趕快發揮(C/P)的長才將它備份來，有需要的同好，歡迎來(C/P)一下^^。 拷貝來源：http://openhome.cc/Gossip/AlgorithmGossip/http://openhome.cc/Gossip/AlgorithmGossip/QuickSort1.htm #include #include #define LEN 10 #define SWAP(x,y) {int t; t = x; x = y; y = t;} void sort(int*, int, int(*)(int, int)); void quickSort(int*, int, int, int(*)(int, int)); void print(int*, int len); int ascending(int, int); int descending(int, int); int main(void) { int number[LEN] = {10, 9, 1, 2, 5, 3, 8, 7, 12, 11}; sort(number, LEN, ascending); print(number, LEN); sort(number, LEN, descending); print(number, LEN); return 0; } void sort(int* number, int len, int(*comp)(int, int)) { quickSort(number, 0, len - 1, comp); } void quickSort(int* number, int left, int right, int(*comp)(int, int)) { if(left < right) { int axis = partition(number, left, right, comp); quickSort(number, left, axis - 1, comp); quickSort(number, axis + 1, right, comp); } } int partition(int* number, int left, int right, int(*comp)(int, int)) { int s = number[left]; int axis = partitionUnprocessed(number, left + 1, right, s, comp); SWAP(number[left], number[axis]); return axis; } int partitionUnprocessed(int* number, int left, int right, int s, int(*comp)(int, int)) { int i = lookRight(number, left, right, s, comp); int j = lookLeft(number, right, i, s, comp); if(i < j) { SWAP(number[i], number[j]); return partitionUnprocessed(number, i + 1, j - 1, s, comp); } return j; } int lookRight(int* number, int from, int to, int s, int(*comp)(int, int)) { int i = from; while(i < to + 1 && comp(number[i], s) <= 0) { i++; } return i; } int lookLeft(int* number, int from, int to, int s, int(*comp)(int, int)) { int j = from; while(j > to - 1 && comp(number[j], s) > 0) { j--; } return j; } void print(int* arr, int len) { int i; for(i = 0; i < len; i++) { printf("%d ", arr[i]); } printf("\n"); } int ascending(int a, int b) { return a - b; } int descending(int a, int b) { return -ascending(a, b); }