本文共 1428 字,大约阅读时间需要 4 分钟。
快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。
1 算法描述
快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:
2 动图演示
3.代码实现
#includevoid swap(int *i, int *j){ int temp = *i; *i = *j; *j = temp;}int partition(int array[], int start, int end){ int pivot = array[start]; int j; j = start; for(int i = start + 1; i <= end; ++i) { if(array[i] < pivot) { swap(&array[j + 1], &array[i]);//还有没有更好的数据交换方式? ++j; } } swap(&array[start], &array[j]); return j;}void quickSort(int array[], int start, int end){ if(start >= end) { return; } int smallIndex = partition(array, start, end); if(smallIndex > start) quickSort(array, start, smallIndex - 1); if(smallIndex < end) quickSort(array, smallIndex + 1, end);}void print(int arr[], int len){ for(int i = 0; i < len; ++i) { printf("%d ", arr[i]); }}int main(){ int array[10] = {43, 49, 57, 12, 9, 32, 83, 28, 5, 51}; printf("quick快速排序前\n"); print(array, 10); printf("\n"); quickSort(array, 0, 9); printf("quik快速排序后\n"); print(array, 10); printf("\n"); printf("Hello World!\n"); return 0;}
快速排序是高效不稳定的排序
参考:
转载地址:http://qziub.baihongyu.com/