数据结构----快速排序

基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，再对两部分记录分别进行继续排序，使得整个记录有序。

首先任选一个记录（通常选第一个记录）作为基准数。

一趟快速排序的做法：

首先从high所指的位置起向前搜索找到第一个关键字小于base的记录，和枢轴记录互换；

然后从low所指的位置起向后搜索找到第一个关键字大于base的记录，和枢轴记录互换；

重复这两步直至low=high为止。

49 38 65 97 76 13 27 49

初始关键字：49 38 65 97 76 13 27 49

high 49 = 49

   27 < 49 互换  27 38 65 97 76 13 49 49

low 38 < 49    65 > 49 互换  27 38 49 97 76 13 65 49

high 13 < 49 互换  27 38 13 97 76 49 65 49

low 97 > 49 互换  27 38 13 49 76 97 65 49

high 76 > 49

low = high   49 = 49 {27 38 13} 49 {76 97 65 49} 完成一趟排序

一次划分结果： {27 38 13} 49 {76 97 65 49}

两边分别进行快速排序：{13} 27 {38}             {49 65} 76 {97}

有序序列**{13 27 38 49 49 65 76 97}**

代码块：

#include<stdio.h> void Swap(int arr[], int low, int high) { int tmp; tmp = arr[low]; arr[low] = arr[high]; arr[high] = tmp; } int Partition(int arr[], int low, int high) { int base = arr[low];// 选取第一个数作为基准数 while (low < high) { while (low < high && arr[high] >= base) { //从high开始，向左遍历，直到找到小于基准数的元素，并将此数放到low位置 high--; } Swap(arr, low, high); while (low < high && arr[low] <= base) { //从low开始，向右遍历，直到找到大于基准数的元素，并将此数放到high位置 low++; } Swap(arr, low, high); } return low; } void QuickSort(int arr[], int low, int high) { int base; if (low < high) { base = Partition(arr, low, high); //调用一趟快速排序，将数组一分为二 QuickSort(arr, low, base - 1); //对左部子表递归排序 QuickSort(arr, base + 1, high); //对高子表递归排序 } } int main() { int arr[] = { 48,62,35,77,55,14,35,98 }; int length = sizeof(arr) / sizeof(arr[0]); int i, j; printf("排序前:\n"); for (i = 0; i < length; i++) { printf("%d ", arr[i]); } printf("\n排序后:\n"); QuickSort(arr, 0, length - 1); for (j = 0; j < length; j++) { printf("%d ", arr[j]); } printf("\n"); return 0; }

运行后：