1. 简介
快速排序，用分治法提高了效率，简直就是“方法得当，效率提高”的典范之作。
基本思路就是每次都把当前数据化为两部分，每次排序保证前面部分都小于后面部分，然后在对两部分分别快速排序。
那么怎么划分两部分呢，以从小到大排序为例，第一个数为基准，然后从尾到头找小于基准的数，从头到尾找大于基准的数，找到就换位。
则首尾相遇时，必然相遇点左侧的都小等于基准，右侧的都大于等于基准，然后把基准放到中间合适位置，则实现了右边全部大于左边。
2. 代码
#include<stdio.h> //打印数组 void printArray(int *p, int length) { printf("打印数组:"); int i; for (i = 0; i<length; i++) { printf("%d ", p[i]); } printf("\n"); } //交换 void swap(int* a, int* b) { int temp = *b; *b = *a; *a = temp; } //快速排序 void fastSort(int* p, int start, int end) { if (start < end)//只要没碰到，就继续排序 { int mid = findMid(p, start, end); fastSort(p, start, mid - 1);//对左侧快速排序 fastSort(p, mid + 1, end);//对右侧侧快速排序 } } //寻找快速排序划分位置 int findMid(int *p,int start,int end) { int base = p[start];//第一个数当做比较基准 while (start < end)//没碰头就一直走 { while (start < end && p[end] >= base)//从尾部往前找比基准小的 { end--; } swap(&p[start], &p[end]);//找到就换位 while (start < end && p[start] <= base)//从头部往后找比基准大的 { start++; } swap(&p[start], &p[end]);//找到就换位 } return start; } //入口 int main() { int a[10] = { 1,3,5,7,2,4,8,6,10,9 }; printArray(a, 10); fastSort(a, 0, 9); printArray(a, 10); return 1; }
