题目：
快速排序
排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。
其思想是：先选一个“标尺”，
用它把整个队列过一遍筛子，
以保证：其左边的元素都不大于它，其右边的元素都不小于它。
这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。
下面的代码是一种实现，请分析并填写划线部分缺少的代码。
#include <stdio.h> void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } int partition(int a[], int p, int r) { int i = p; int j = r + 1; int x = a[p]; while(1){ while(i<r && a[++i]<x); while(a[--j]>x); if(i>=j) break; swap(a,i,j); } ______________________; return j; } void quicksort(int a[], int p, int r) { if(p<r){ int q = partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); } } int main() { int i; int a[] = {5,13,6,24,2,8,19,27,6,12,1,17}; int N = 12; quicksort(a, 0, N-1); for(i=0; i<N; i++) printf("%d ", a[i]); printf("\n"); return 0; }
注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。
答案：
#include <stdio.h> void swap(int a[], int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } int partition(int a[], int p, int r) { int i = p; int j = r + 1; int x = a[p]; while(1){ while(i<r && a[++i]<x); while(a[--j]>x); if(i>=j) break; //******************* swap(a,i,j); //******************* } swap(a,p,j); return j; } void quicksort(int a[], int p, int r) { if(p<r){ int q = partition(a,p,r); quicksort(a,p,q-1); quicksort(a,q+1,r); } } int main() { int i; int a[] = {5,13,6,24,2,8,19,27,6,12,1,17}; int N = 12; quicksort(a, 0, N-1); for(i=0; i<N; i++) printf("%d ", a[i]); printf("\n"); return 0; }
——————————————————————————————————————
用递归实现快速排序：
#include <iostream> #include <cstdio> using namespace std; void quick_sort(int arr[],int left,int right) { if(left>=right) return; int i,j,base,temp; i = left,j=right; //i,j作为左右移标，left，right不动 base = arr[left]; //base作为基准值 while(i<j) { while(arr[j]>=base&&i<j) j--; //将j移到后面数比基准值小的数得下标 while(arr[i]<=base&&i<j) i++; //将i移到前面比基准值大的数下标 if(i<j) { temp = arr[i]; //进行相互替换 arr[i] = arr[j]; arr[j] = temp; } } arr[left] = arr[i]; //首先把刚开始作为基准值的位置换上符合比基准值小的就是i的下标 arr[i] = base; //再将基准值给到i位置，作为分界线 quick_sort(arr,left,i-1); //进行递归操作 quick_sort(arr,i+1,right); } int main() { int arr[] = {5,4,9,10,2,1,5}; int len = sizeof(arr)/sizeof(arr[0]); quick_sort(arr,0,len-1); for(int i=0;i<len;i++) printf("%d ",arr[i]); return 0; }
