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