排序算法三：快速排序

浏览数：26 / 时间：2015年06月08日

一.算法思想

　　1.快速排序基本思想是：分治思想；即将一个大的问题通过：分解--解决--合并，这几步，从而实现排序。一般是将大问题划分成很多个一样的问题，然后递归的解决每个小问题。最后，将每个小问题解决的结果合并起来就解决了问题。

　　2.基本过程：对于一个无序的序列，首先，选择一个关键元素，作为划分元素的分界线；一般选择第一个或者最后一个元素。然后，遍历数组，将小于关键元素的放到它的左边，大于关键元素的放到他的右边，最后将关键元素插入到正确位置。然后，按照相同的处理方法，划分左右两部分的内容。最后，所有的元素被划分成两个有序的元素片段。并且这样之后，整个序列就已经是有序的了。

　　3.快速排序是一种不稳定的内部排序，不需要额外的空间。

　　4.快速排序的平均时间复杂度是：T(n) = O(nlgn);

最坏的情况是：T(n) = O(n^2);

二.代码

class QuickSort{
   //划分序列的类，划分出来的小的序列片段，也需要执行此操作
   public static int partation(int[] A,int p,int r){
       int len =A.length;
       int key = A[r];
       int i = p-1;
       int temp = -1;
       for(int j = p;j<r;j++){
           i+=1;
           if(A[j] <= key){
               temp = A[j];
               A[i] = A[j];
               A[j] = temp;
           }
       }
       temp = A[i+1];
       A[i+1] = A[r];
       A[r] =temp;
       return i+1;    
   }        
   //递归排序处理
   public static void quickSort(int[] A,int p,int r){
       if(p<r){
           int q = partation(A,0,A/length-1);  
           paration(A,0,q-1);
           paration(A,q+1,r);
       }

   }   
}