基本思想：
快速排序是冒泡排序的改進版本，它的思想是通過一趟排序講待排序的記錄分隔成獨立的兩部分，其中一不分記錄的關(guān)鍵字均小于另一部分關(guān)鍵字，則可以分別對這兩部門記錄繼續(xù)進行排序 ，以*整個虛列的有序。
假設(shè)待排序的虛列為{L.r[s],L.r[s+1],.......,L.r[t]]} ,首先選取一個記錄(通?？梢贿x擇第一個記錄L.r[s])作為樞軸(或支點),然后按照下述原則重新排列其他記錄，講所有關(guān)鍵字較它小的記錄都安置在它的位置之前，將所有關(guān)鍵字較它大的記錄都安置在它的位置之后。由此可以該 “樞軸” 記錄最后所落的位置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]]} ，這個過程叫作一趟快速排序(或者一次劃分).
一趟快速怕序的具體做法是：附設(shè)兩個指針low和high,他們的初值分別為low和high,設(shè)樞軸記錄的關(guān)鍵字為privotkey,則首先從high所指位置向前搜索找到第一個關(guān)鍵字小于pivotkey的記錄和樞軸記錄互相交換,然后從low所指向的位置起向后搜索,找到第一個關(guān)鍵字大于privotkey的記錄和樞軸記錄互相交換，重復(fù)這兩步直至low==high位置.
代碼一：
/**
* 采用交換方式 排序
*/
package 排序.交換排序;
import java.util.concurrent.Executor;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
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
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
*/
while(low
/**
* 先從 high端 開始判斷
*/
while(low=pivot) high--;
/**
* 進行 置換操作
*/
if(low
temp=array[low];
array[low]=array[high];
array[high]=temp;
low++;
}
/**
* 從 low 端判斷
*/
while(low
/**
* 進行 置換操作
*/
if(low
temp=array[high];
array[high]=array[low];
array[low]=temp;
high--;
}
}
return low;
}
}
具體實現(xiàn)上述算法時候，每交換一對記錄需要進行三次記錄的移動(賦值)的操作,而實際上，在排序過程中對樞軸記錄的賦值是多余的，因為只有在一趟排序結(jié)束時，即low==high的位置菜市樞軸記錄的最后位置，由此可改寫上述算法，先將記錄暫時存在r[0]的位置上，排序過程中做r[low]或 r[high]的單向移動，直至一趟排序后再將樞軸記錄移至正確位置上.
快速排序是冒泡排序的改進版本，它的思想是通過一趟排序講待排序的記錄分隔成獨立的兩部分，其中一不分記錄的關(guān)鍵字均小于另一部分關(guān)鍵字，則可以分別對這兩部門記錄繼續(xù)進行排序 ，以*整個虛列的有序。
假設(shè)待排序的虛列為{L.r[s],L.r[s+1],.......,L.r[t]]} ,首先選取一個記錄(通?？梢贿x擇第一個記錄L.r[s])作為樞軸(或支點),然后按照下述原則重新排列其他記錄，講所有關(guān)鍵字較它小的記錄都安置在它的位置之前，將所有關(guān)鍵字較它大的記錄都安置在它的位置之后。由此可以該 “樞軸” 記錄最后所落的位置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]]} ，這個過程叫作一趟快速排序(或者一次劃分).
一趟快速怕序的具體做法是：附設(shè)兩個指針low和high,他們的初值分別為low和high,設(shè)樞軸記錄的關(guān)鍵字為privotkey,則首先從high所指位置向前搜索找到第一個關(guān)鍵字小于pivotkey的記錄和樞軸記錄互相交換,然后從low所指向的位置起向后搜索,找到第一個關(guān)鍵字大于privotkey的記錄和樞軸記錄互相交換，重復(fù)這兩步直至low==high位置.
代碼一：
/**
* 采用交換方式 排序
*/
package 排序.交換排序;
import java.util.concurrent.Executor;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
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
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
*/
while(low
/**
* 先從 high端 開始判斷
*/
while(low=pivot) high--;
/**
* 進行 置換操作
*/
if(low
temp=array[low];
array[low]=array[high];
array[high]=temp;
low++;
}
/**
* 從 low 端判斷
*/
while(low
/**
* 進行 置換操作
*/
if(low
temp=array[high];
array[high]=array[low];
array[low]=temp;
high--;
}
}
return low;
}
}
具體實現(xiàn)上述算法時候，每交換一對記錄需要進行三次記錄的移動(賦值)的操作,而實際上，在排序過程中對樞軸記錄的賦值是多余的，因為只有在一趟排序結(jié)束時，即low==high的位置菜市樞軸記錄的最后位置，由此可改寫上述算法，先將記錄暫時存在r[0]的位置上，排序過程中做r[low]或 r[high]的單向移動，直至一趟排序后再將樞軸記錄移至正確位置上.