快速排序
快速排序的基本思想是在待排序的n个元素中任取一个元素(通常取第一个元素)作为基准,把该元素放入适当位置后,数据序列被此元素划分为两部分.所有关键字比该元素关键字小的元素放置在前一部分,所有比它大的元素放置在后一部分,并把该元素排在这两部分的中间,之后对产生的两部分分别重复上述过程,直至每部分内只有一个元素或空为止.
代码如下
1 #include<iostream> 2 using namespace std; 3 #define N 10005 4 int a[N]; //a[N]需要在函数中使用,因此直接定义全局变量 5 6 void quicksort(int left,int right) 7 { 8 int i,j,temp,s; 9 if(left > right) 10 return; 11 i = left; 12 j = right; 13 temp = a[left]; 14 while(i != j) 15 { 16 while(a[j] >= temp&&i < j) 17 j--; 18 while(a[i] <= temp&&i < j) 19 i++; 20 if(i < j) //将a[i]和a[j]交换 21 { 22 s = a[i]; 23 a[i] = a[j]; 24 a[j] = s; 25 } 26 } 27 a[left] = a[i]; //将 temp与a[i]交换,此时a[i]小于temp; 28 a[i] = temp; 29 quicksort(left,i-1); //对左区间递归排序 30 quicksort(i+1,right); //对右区间递归排序 31 } 32 33 int main() 34 { 35 int i,n; 36 cin>>n; 37 for(i = 1;i <= n;i++) 38 { 39 cin>>a[i]; 40 } 41 quicksort(1,n); 42 for(i = 1;i<=n;i++) 43 { 44 cout<<a[i]<<' '; 45 } 46 return 0; 47 }