快速排序

                                                                              快速排序

  基本思想：          

              快速排序是冒泡排序的改進版本，它的思想是通過一趟排序講待排序的記錄分隔成獨立的兩部分，其中一不分記錄的關鍵字均小于另一部分關鍵字，則可以分别對這兩部門記錄繼續進行排序 ，以打倒整個虛列的有序

          假設待排序的虛列為{L.r[s],L.r[s+1],.......,L.r[t]]}  ,首先選取一個記錄(通常可一選擇第一個記錄L.r[s])作為樞軸(或支點),然後按照下述原則重新排列其他記錄，講所有關鍵字較它小的記錄都安置在它的位置之前，将所有關鍵字較它大的記錄都安置在它的位置之後。由此可以該 “樞軸” 記錄最後所落的位置i作為分界,将序列{L.r[s],L.r[s+1],.......,L.r[t]]}   分隔成了兩個子序列{L.r[s],L.r[s+1],.......,L.r[i-1]]}  和 {L.r[i+1],L.r[s+1],.......,L.r[t]]}  ，這個過程叫作一趟快速排序(或者一次劃分).

    一趟快速怕序的具體做法是：附設兩個指針low和high,他們的初值分别為low和high,設樞軸記錄的關鍵字為privotkey,則首先從high所指位置向前搜尋找到第一個關鍵字小于pivotkey的記錄和樞軸記錄互相交換,然後從low所指向的位置起向後搜尋,找到第一個關鍵字大于privotkey的記錄和樞軸記錄互相交換，重複這兩步直至low==high位置.

代碼一：

/**

*    采用交換方式 排序

*/

package 排序.交換排序;

import java.util.concurrent.Executor;

import java.util.concurrent.ExecutorService;

import java.util.concurrent.Executors;

* @author liuyi

public class 快速排序 {

public static void main(String[] args) throws InterruptedException {

  int test[] = {15,23,56,7,13,52,20,7};

  new 快速排序().qSort(test, 0, test.length-1);

  for(int k:test) System.out.println(k);

}

public void qSort(int []array,int low,int high){

    if(low<high){

     int privot=partition(array,low,high);

     qSort(array,low,privot-1);

     qSort(array,privot+1,high);

    }    

public int partition(int [] array,int low,int high){

    /**

     * 選擇 low位置 作為曲軸（支點）

     */

    int pivot=array[low];

    int temp=0;

     * 如果 low<high 就進行 循環 進行 該輪排序

    while(low<high){

     /**

        * 先從 high端 開始判斷

        */

     while(low<high&&array[high]>=pivot)    high--;

        * 進行 置換操作

     if(low<high){

        temp=array[low];

        array[low]=array[high];

        array[high]=temp;

        low++;

     }

            /**

        * 從 low 端判斷    

     while(low<high&&array[low]<=pivot)    low++;

        temp=array[high];

        array[high]=array[low];

        array[low]=temp;

             high--;

    }

    return low;

   具體實作上述算法時候，每交換一對記錄需要進行三次記錄的移動(指派)的操作,而實際上，在排序過程中對樞軸記錄的指派是多餘的，因為隻有在一趟排序結束時，即low==high的位置菜市樞軸記錄的最後位置，由此可改寫上述算法，先将記錄暫時存在r[0]的位置上，排序過程中做r[low]或r[high]的單向移動，直至一趟排序後再将樞軸記錄移至正确位置上.

 改寫代碼

代碼二：

* 改進的 快速排序

public class 快速排序_1 {

  new 快速排序_1().qSort(test, 0, test.length-1);

     if(low<high){    

        array[low]=array[high];        

        array[high]=array[low];    

    array[low]=pivot;

}