題目要求
快速排序
題目解析
思路一：
- 分析
首先選擇一個樞軸值脱篙，和兩個下標值分別為low和high还惠。
首先比較是否樞紐值與low下標所代表的值的大小，如果大于奈懒，那么檢查low+1的值芍躏。
如果小于的話將low的值移動至數(shù)組右側(cè)邪乍。
然后比較是否樞紐值與high下標所代表的值的大小，如果小于对竣，那么檢查high-1的值庇楞。
如果小于的話將low的值移動至數(shù)組左側(cè)。
再分別在分開的兩個區(qū)間進行快速排序
- 代碼段
public static int[] order(int[] data) {
if(data == null || data.length == 0) {
return null ;
}
//確定中間值為樞軸值
int tempId = (data.length - 1 + 0 ) / 2 ;
int temp = data[(data.length - 1 + 0 ) / 2] ;
int low = 0 ;
int high = data.length-1 ;
//移動元素完成一波快速排序
while(low < high) {
while(low < tempId && data[low] <= temp) {
low ++ ;}
data[tempId] = data[low] ;
tempId = low ;
low++ ;
while(tempId < high && data[high] >= temp) {
high -- ;}
data[tempId] = data[high] ;
tempId = high ;
high-- ;
}
data[tempId] = temp ;
//處理樞軸左邊的數(shù)組區(qū)間
if(tempId > 0) {
int[] leftData = order(Arrays.copyOfRange(data, 0 , tempId)) ;
for(int i = 0 ; i < tempId ; i++ ) {
data[i] = leftData[i] ;
}
}
//處理樞軸右邊的數(shù)組區(qū)間
if(tempId+1 < data.length ) {
int[] rightData = order(Arrays.copyOfRange(data, tempId+1 , data.length)) ;
for(int i = tempId+1 ; i < data.length ; i++) {
data[i] = rightData[i - (tempId+1)] ;
}
}
return data ;
}
測試代碼
public static void main(String[] args) {
int[] data = {46,68,12,25,33,80,19,33} ;
data = order(data) ;
if(data != null)
for(int i = 0 ; i < data.length ; i++) {
System.out.print( data[i] + ((i==data.length-1) ? "":",") );
}
}
運行結果
t排序前
46,68,12,25,33,80,19,33>>>>>>>>>>>>>>>>>>>>>>>>>>
排序后
12,19,25,33,33,46,68,80
