前幾天被一哥們兒實(shí)力嘲諷玩祟，問我快速排序怎么實(shí)現(xiàn)腹缩，我只是記得自己學(xué)過，但是忘記了具體怎么實(shí)現(xiàn)空扎，原理是什么ORZ藏鹊，然后LL就努力去百度學(xué)習(xí)，汲取转锈，大致將一些自己的感受：
注意盘寡！文檔只是以我的想法來進(jìn)行闡述，只是盡量以我能理解的方式來解釋算法原理黑忱，只是為了將來上了年紀(jì)宴抚，或者忘記了這個原理的時候來學(xué)習(xí)一下。
廢話不多說甫煞，套用之前那哥們講話菇曲，冒泡是最簡單的排序方法
那么接下來
講一下快速排序
情景擬定：
一個數(shù)組array，需要將其從由小到大的順序排列
array = { 4 , 5 , 2 , 22 , 11 , 32 , 2 , 5 }
快速排序的原理是這樣子的：
分治的原理：
首先選定一個元素a抚吠，然后將這個數(shù)組中比這個元素小的元素們放到該元素的左邊常潮，將數(shù)組中比這個元素大的元素放到該元素的右邊。 至此a元素的位置已經(jīng)排好了楷力，剩下的就是由a將數(shù)組劃成兩半進(jìn)行排序
每一半排序方式同上喊式。
這樣子最后肯定能排好序
明顯能夠看出這是**遞歸**的思想
然后問題來了，首先怎么具體的將a放到他應(yīng)該的位置萧朝？
是這樣子的
/(比較方便岔留，確保了只是將除了該a之外的其余數(shù)字只比較一遍)→往下看就能理解我這句話了/
首先我們需要給這個數(shù)組定義一個首、尾index检柬，比如 i=0献联，j=array.length-1=7;
假定我們需要排的元素 a=array[0]=4
那么首先我們從array[j]處向前遍歷比較
array[7]=5>4 正常 j--
array[6]=2<4 應(yīng)該在4左邊，所以將array[0]=2
此時 j = 6 何址；
array現(xiàn)在是這樣子的 array = {2 , 5 , 2 , 22 , 11 , 32 , 空 ,5}
那么現(xiàn)在array[6] (也就是array[j]) 空出來了
我們這時候應(yīng)該看一下i往后了
array[0] < a 正常 i++
array[1] = 5 > a 不對哦 比4大應(yīng)該在右邊
所以將5放到剛才上面缺的地方
array[j] = 5
那么現(xiàn)在是array = {2,空,2,22,11,32,5,5}
i = 1
現(xiàn)在array[1] 也就是array[i] 空了
接下來接著從j的位置向前
array[6] = 5 < 4 okay j--
array[5] = 32 >4 okay j--
array[4] = 11 > 4 okay j--
array[3] = 22 > 4 okay j--
array[2] = 2 < 4 換換換
array[i] = array[1] = 2
那么現(xiàn)在 j 為2了里逆，
array = {2,2,空,22,11,32,5,5}
再從i開始
i=1
array[i] = 2 < 4 okay i++
此時 i=2=j 交頭了說明over了
那么將剛才最開始的a 放到array[i] or array[j]位置上就好了 (反正 i 和 j 相等了)
array = {2,2,4,22,11,32,5,5}
那么接下來需要對array的兩個子串
array1={2,2}
array2={22,11,32,5,5}
然后對子串進(jìn)行像剛才那樣的順序排序
package quickSort;
import java.util.Arrays;
/**
* 遞歸實(shí)現(xiàn)快速排序
* @author mengf
*
*/
public class Qsort {
public static int[] quickSort(int[] array,int start , int end){
int i = start;
int j = end;
int a = array[i];
//好的情況
while (i!=j&&i<j) {
while (j!=i) {
if (array[j]<a) {
array[i]=array[j];
i++;
break;
}else{
j--;
}
}
while (j!=i) {
if (array[i]>a) {
array[j]=array[i];
j--;
break;
}else{
i++;
}
}
}
//然后最后i=j
array[i]=a;
//分成兩半
if (i>start) {
quickSort(array, start, i-1);
}
if (i<end) {
quickSort(array, i+1, end);
}
return array;
}
public static void main(String[] args) {
int[] array = {12,10,22,5,6,8,11,7,3,4,5,33,32,23,34,32,43,34};
quickSort(array, 0, array.length-1);
System.out.println(Arrays.toString(array));
}
}
所以不難看出如果要實(shí)現(xiàn)遞歸實(shí)現(xiàn)是很好理解的
注：如果有大神看到這里肯定會覺得我上面寫的有些問題
我承認(rèn)我順著思路寫完之后其實(shí)有地方需要改進(jìn)的
！就是需要替換的時候用爪，比如j往前跟4對比原押，遇到需要替換的時候，將array[i]替換之后偎血，可以將i++
因為替換到i位置上肯定已經(jīng)滿足這個數(shù)字<4 所以將i++之后
從i這邊開始的時候就不需要重新再將剛替換的位置的數(shù)字和a再比較了诸衔。
下面開始看一下遞歸的java代碼實(shí)現(xiàn)：
然后后來百度了一下百科是這樣寫的，原理是一樣的
package quickSort;
import java.util.Arrays;
public class QuickSort {
/**
* 無邊界檢查
* 完全專注于算法
* @param arrays
* @param start
* @param end
* @return
*/
public int[] quickSort(int[] arrays,int low,int high){
int start = low;
int end = high;
//只有一個元素的時候是排好序的了
if (start==end) {
return arrays;
}
//算法開始
int temp = arrays[start];
while (start<end) {
while (start<end && arrays[end]>=temp) {
end--;
}
arrays[start]=arrays[end];
while (start<end && arrays[start]<=temp) {
start++;
}
arrays[end]=arrays[start];
}
//start = end
arrays[start]=temp;
//迭代兩邊排序
if (start>low) {
quickSort(arrays, 0, start-1);
}
if (end<high) {
quickSort(arrays,start+1,arrays.length-1);
}
return arrays;
}
public static void main(String[] args) {
QuickSort quickSort = new QuickSort();
int[] arrays = {1,11,35,2,3,5,323,213,22,3,1,2,3,4,5,3};
quickSort.quickSort(arrays, 0, arrays.length-1);
System.out.println(Arrays.toString(arrays));
}
}
臭美一下颇玷，我覺得這個大概就是我之前沒有在換位置之后將對應(yīng)的位置的 i++或者 j-- 這樣感覺會多一次判斷署隘，雖然對算法復(fù)雜度沒有影響。
再就是如果加上了的話這個寫法比我寫的好多了亚隙，判斷寫在while里面
而我的是while中又有if磁餐，感覺效率沒有這個高。
算法復(fù)雜度: O(n*logn)
但是寫到這里阿弃，我有問題了
遞歸對伐诊霹，大家都知道浪費(fèi)空間的做法，但是遞歸對于程序的理解有著極大的幫助渣淳，而且我記得數(shù)據(jù)結(jié)構(gòu)老師說過脾还，所有的遞歸都能改為循環(huán)的，這就是對于這個問題的下一步探討了入愧，我先學(xué)習(xí)下鄙漏，等搞懂了再搞一篇優(yōu)化后的快速排序嗤谚。
現(xiàn)在說說我覺得這樣的<u>局限</u>在哪里：
如果排序?qū)ο筝^大，數(shù)目較多怔蚌，內(nèi)存可能不夠巩步，雖然很少有出現(xiàn)這種情況，但是如果能夠改成循環(huán)桦踊，而放棄遞歸
無疑是對能力的提升椅野，像我這種懶人還是覺得遞歸好，起碼理解起來簡單籍胯，至于循環(huán)竟闪，最近看情況找找資料學(xué)學(xué)，要是沒有下一篇了的話杖狼，可能LL已經(jīng)忘記這件事情了炼蛤，大家可以先用著遞歸，畢竟現(xiàn)在普通項目中也不太可能遇到占用很大內(nèi)存來遞歸的情況蝶涩。
