快速排序算法

本文主要是介绍快速排序算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

快速排序

快速排序的基本思想是在待排序的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  } 

这篇关于快速排序算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！