经典排序（八种）

快速排序--QuickSort

基本思想：

一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后分别对左右两边进行这样的操作，直到只有一个数据。最后的得到的数据就是排序好的数据

算法设计：

方法一：

1.初始化，数组长度为N，设置i=0,j-N-1

2.以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3.从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将值为key的项与A[j]交换；
4.从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将值为key的项与A[i]交换；
5.重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[j]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。（这种方法来自《数据结构C语言版》）

演示：

核心代码：

 1 int partition(int a[],int l,int r)
 2 {
 3     int key = a[l];
 4     while(l<r)
 5     {
 6         while(l<r&&a[r]>=key)
 7             r--;
 8         a[l]=a[r];
 9         
10         while(l<r&&a[l]<=key)
11             l++;
12         a[r]=a[l];
13     }
14     a[l]=key;
15     return l;
16 }

方法二：

过程：

数组a[]：4 2 1 6 3 5 初始主元：a[5]=5 i=-1 j=1

第一趟： j=1,a[j]=4 < 5,所以i++,a[i]与a[j]交换（即a[1]与本身交换），原数组不变 i=1

　　　　 4 2 1 6 3 5

第二躺： j=2,a[j]=2 <5,所以i++,a[i]与a[j]交换（即a[2]与本身交换），原数组不变 i=2

　　　　　4 2 1 6 3 5

第三躺： j=3,a[j]=1 <5,所以i++,a[i]与a[j]交换（即a[3]与本身交换），原数组不变 i=3

　　　　　4 2 1 6 3 5

第四躺： j=4,a[j]=6 >5,继续扫描下一个值，i=3

　　　　4 2 1 6 3 5

第五躺： j=5,a[j]=3 <5,所以i++(i=4),a[4]与a[5]交换,i=4

　　　　4 2 1 3 6 5

第六躺： j=6,因为没有数据了，a[6]就是主元，所以停止，i++，a[5]与 a[6]交换；

　　　　4 2 1 3 6 5

 1 int partition(int a[],int l,int r)
 2 {
 3     int i=l-1,j,temp;
 4     for(j=l; j<r; j++)
 5     {
 6         if(a[j]<a[r])
 7             {
 8                 i++;
 9                 temp=a[i];
10                 a[i]=a[j];
11                 a[j]=a[i];                
12             }
13         
14     }
15     temp=a[i+1];
16     a[i+1]=a[r];
17     a[r]=a[i+1];
18 }