[每日C] QuickSort 演算法速覽
完整原始碼:
#include <stdio.h> #include <stdlib.h> #include <time.h> #define SIZE 10 void quickSort(int* array, int size); void quickStep(int* array, int start, int stop); int quickSortElement(int* array, int start, int stop); void swapNode(int* array, int index1, int index2); void printArray(int* array, int size); void genRandArray(int* array, int size); int main() { int arrayToSort[SIZE] = {0}; genRandArray(arrayToSort, SIZE); printf("Before Sort:\n"); printArray(arrayToSort, SIZE); quickSort(arrayToSort, SIZE); printf("After Sort:\n"); printArray(arrayToSort, SIZE); } void quickSort(int* array, int size) { quickStep(array, 0, size-1); } void quickStep(int* array, int start, int stop) { if (stop-start > 0) { printf(" quickStep(array, %d, %d)\n", start, stop); int middle = quickSortElement(array, start, stop); { printf(" "); printArray(array, SIZE); } quickStep(array, start, middle-1); quickStep(array, middle+1, stop); } } int quickSortElement(int* array, int start, int stop) { int middle = (stop - start)/2+start; int pivotValue = array[middle]; swapNode(array, middle, stop); // move pivot point to end int storeIntex = start; for (int i=start; i<=stop; i++) { if (array[i] >= pivotValue) { swapNode(array, i, storeIntex); storeIntex++; } } return storeIntex-1; } void swapNode(int* array, int index1, int index2) { int temp = array[index1]; array[index1] = array[index2]; array[index2] = temp; } void printArray(int* array, int size) { printf("["); for(int i=0; i<size; i++) { printf(" %d", array[i]); } printf(" ]\n"); } void genRandArray(int* array, int size) { srand(time(NULL)); bool isDup = false; for (int i=0; i<size; i++) { do { isDup = false; array[i] = rand()%20+1; for (int j=0; j<i; j++) { if (array[j] == array[i]) { isDup = true; } } } while (isDup); } }
執行結果(範例):
Before Sort: [ 18 17 19 12 10 6 13 1 5 7 ] quickStep(array, 0, 9) [ 18 17 19 12 13 10 7 1 5 6 ] quickStep(array, 0, 4) [ 19 17 13 12 18 10 7 1 5 6 ] quickStep(array, 1, 4) [ 19 17 18 13 12 10 7 1 5 6 ] quickStep(array, 1, 2) [ 19 18 17 13 12 10 7 1 5 6 ] quickStep(array, 6, 9) [ 19 18 17 13 12 10 7 6 5 1 ] quickStep(array, 6, 8) [ 19 18 17 13 12 10 7 6 5 1 ] After Sort: [ 19 18 17 13 12 10 7 6 5 1 ]