快速排序基本思想——分治 怎样将一个无序序列排成有序的呢？我们可以把问题分成两：对大于某个数k的那部分进行排序和对小于k的部分进行排序。当两个部分排完后就实现了整个序列的排序。显然这是一个递归求解的问题。那么最重要的是怎样把序列以某个数为分界点分成两部分呢？可以首先随意找一个数当做分界点，然后使用两个指针分别从序列左右两端进行扫描，扫描的过程中进行交换，当两个指针相遇时，数组就被分成了两部分。注意在这个过程中基准值一定是个定值！！！
基本步骤 （1）找基准数：在数组中找一个数k作为基准数 ！！一定是个定值！！（规则：可选左右端点、中间点、随机点，但要注意边界问题：l不与i，r不与j，（l+r)/2不与r，(r+l+1)/2不与l） （2）调整区间：使区间分界点（i或j) 左边区间小于等于基准数，区间分界点右边大于等于基准数。 （3）递归处理：对两个区间重复（2）、（3）操作
应用例题 例1： 给定你一个长度为n的整数数列。 请你使用快速排序对这个数列按照从小到大进行排序。 并将排好序的数列按顺序输出。
输入格式 输入共两行，第一行包含整数 n。 第二行包含 n 个整数（所有整数均在1~10^9范围内），表示整 个数列。
输出格式 输出共一行，包含 n 个整数，表示排好序的数列。 数据范围
1≤n≤100000 输入样例： 5 3 1 2 4 5 输出样例： 1 2 3 4 5
#include<stdio.h> #include<stdlib.h> #define N 100000 void quick_sort(int q[], int l, int r); int main(void) { int n, q[N], i; scanf("%d", &n); for(i=0; i<n; i++) scanf("%d", &q[i]); quick_sort(q, 0, n-1); for(i=0; i<n; i++) printf("%d ", q[i]); return 0; } void quick_sort(int q[], int l, int r) { if(l>=r) return; //递归终止条件：最终数组被分为单个元素 int k=q[(l+r)/2], i=l-1, j=r+1; //把数组中间的一个数作为基准数k，因为循环为do-while型，所以把“指针”向左右各先移动一个单位 while(i<j) //此循环结构的目的：调整区间 { do i++; while(q[i]<k); //让i从左端点开始直到指向大于等于k的值 do j--; while(q[j]>k); //让j从右端点开始直到指向小于等于k的值 if(i<j) swap(q[i], q[j]); } quick_sort(q, l, j); //对小于k的区间递归 quick_sort(q, j+1, r); //对大于k的区间递归 }再次强调：k = i+j >> 1 这种错法很常见！！！
例2：第k个数 给定一个长度为n的整数数列，以及一个整数k，请用快速选择算法求出数列的第k小的数是多少。
输入格式 第一行包含两个整数 n 和 k。 第二行包含 n 个整数（所有整数均在1~109范围内），表示整数数列。 输出格式 输出一个整数，表示数列的第k小数。 数据范围 1≤n≤100000 1≤k≤n
输入样例： 5 3 2 4 1 5 3
输出样例： 3 一般解法：全部排序，找到第k个数。 时间复杂度：O(nlogn)
#include<stdio.h> #define N 100000 void quick_sort(int q[], int l, int r); void swap(int *a, int *b); int main(void) { int q[N], i, n, k; scanf("%d %d", &n, &k); for(i=0; i<n; i++) scanf("%d", &q[i]); quick_sort(q, 0, n-1); printf("%d", q[k-1]); return 0; } void swap(int *a, int *b) { int temp; temp = *a; *a = *b; *b = temp; } void quick_sort(int q[], int l, int r) { if(l>=r) return; int k=q[(l+r)/2], i=l-1, j=r+1; while(i<j) { do i++; while(q[i]<k); do j--; while(q[j]>k); if(i<j) swap(&q[i], &q[j]); } quick_sort(q, l, j); quick_sort(q, j+1, r); }修改快速排序写法：根据分界点右边数都小于分界点左边数的性质，不断舍弃多余的区间 时间复杂度：O(n)
#include<iostream> #define N 100000 using namespace std; int q[N]; int llen; //保存左区间的长度 int quick_search(int l, int r, int k) { if (l >= r) return q[r]; //返回第k个数 int t = q[l], i = l - 1, j = r + 1; while(i<j) { do i++; while(q[i] < t); do j--; while(q[j] > t); if(i<j) swap(q[i], q[j]); } llen = j - l + 1; if(k <= llen) quick_search(l, j, k); //k小于左区间长度，在左区间中继续递归，舍弃右区间 else quick_search(j+1, r, k - llen); //k大于左区间长度，在右区间中继续递归，舍弃左区间 } int main() { int i, n, k; scanf("%d %d", &n, &k); for(i = 0; i<n; i++) scanf("%d", &q[i]); printf("%d", quick_search(0, n-1, k)); return 0; }