史上最容易理解的《十大經(jīng)典算法（動(dòng)態(tài)圖展示）》

好漢勃士 2020-01-18

展開(kāi)全文

十大經(jīng)典排序算法

部分內(nèi)容引用自：https://www.cnblogs.com/onepixel/articles/7674659.html

感謝作者貢獻(xiàn),，如需刪除請(qǐng)聯(lián)系本人,！

0,、排序算法說(shuō)明

0.1 排序分類(lèi)

非線性時(shí)間比較類(lèi)排序：通過(guò)比較來(lái)決定元素間的相對(duì)次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn),，因此稱(chēng)為非線性時(shí)間比較類(lèi)排序。

線性時(shí)間非比較類(lèi)排序：不通過(guò)比較來(lái)決定元素間的相對(duì)次序，它可以突破基于比較排序的時(shí)間下界,，以線性時(shí)間運(yùn)行，因此稱(chēng)為線性時(shí)間非比較類(lèi)排序,。

0.2 術(shù)語(yǔ)說(shuō)明

穩(wěn)定：如果a原本在b前面,，而a=b，排序之后a仍然在b的前面,；
不穩(wěn)定：如果a原本在b的前面,，而a=b,，排序之后a可能會(huì)出現(xiàn)在b的后面；
內(nèi)排序：所有排序操作都在內(nèi)存中完成,；
外排序：由于數(shù)據(jù)太大,，因此把數(shù)據(jù)放在磁盤(pán)中，而排序通過(guò)磁盤(pán)和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行,；
時(shí)間復(fù)雜度：一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間,。
空間復(fù)雜度：運(yùn)行完一個(gè)程序所需內(nèi)存的大小。

0.3 算法總結(jié)

圖片名詞解釋?zhuān)?/p>

n: 數(shù)據(jù)規(guī)模
k: “桶”的個(gè)數(shù)
In-place: 占用常數(shù)內(nèi)存,，不占用額外內(nèi)存
Out-place: 占用額外內(nèi)存

1,、冒泡排序（Bubble Sort）

冒泡排序是一種簡(jiǎn)單的排序算法。它重復(fù)地走訪過(guò)要排序的數(shù)列,，一次比較兩個(gè)元素,，如果它們的順序錯(cuò)誤就把它們交換過(guò)來(lái)。走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,，也就是說(shuō)該數(shù)列已經(jīng)排序完成,。這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端。

1.1 算法描述

比較相鄰的元素,。如果第一個(gè)比第二個(gè)大,，就交換它們兩個(gè)；
對(duì)每一對(duì)相鄰元素作同樣的工作,，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì),，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
針對(duì)所有的元素重復(fù)以上的步驟,，除了最后一個(gè),；
重復(fù)步驟1~3，直到排序完成,。

1.2 動(dòng)圖演示

1.3 代碼實(shí)現(xiàn)


package cn.fuqiang.arithmetic;
import java.util.Comparator;
/**
* 冒泡排序
* @author 王福強(qiáng)
* @Title: BubbleSort.java
* @Package cn.fuqiang.arithmetic
* @Description 冒泡排序  實(shí)現(xiàn)
* @date 2018年6月8日 下午4:18:37
*/
public class BubbleSort<T> {
	public static void main(String[] args) {
		int[] arr = {4,1,5,3,8,10,28,2};
		sort(arr);
		so(arr);
		Integer[] arr2 = {4,1,5,3,8,10,28,2};
		sort(arr2,(a,b)-> b.compareTo(a));
		so(arr2);
	}
	/**
	* 冒泡排序       (特點(diǎn)：從后往前)
	* 原理：前后元素兩兩之間進(jìn)行比較    把大的往后扔
	* 升序      (從后往前,，從大到小)
	* 外層循環(huán)是控制內(nèi)層循環(huán)的次數(shù)，也就是說(shuō)外層循環(huán)每循環(huán)一遍,，讓內(nèi)層循環(huán)每次循環(huán)的次數(shù)減一次
	* 這樣就保證內(nèi)層循環(huán)每次循環(huán)結(jié)束后最后面一個(gè)都是最大
	* 例如 ： 3 6 4 1
	* 外循環(huán)第一次 結(jié)束后,，內(nèi)循環(huán)   會(huì)把6放到最后面   3  4  1  6
	* 外循環(huán)第二次開(kāi)始時(shí)，內(nèi)循環(huán)的循環(huán)次數(shù)會(huì)減一  也就是說(shuō) 6 不會(huì)在參與比較
	* 外循環(huán)第二次結(jié)束時(shí),， 內(nèi)循環(huán)   會(huì)把4放到最后面  3 1 4
	* 以此類(lèi)推,。。,。,。
	* 外循環(huán)第三次結(jié)束時(shí)   內(nèi)循環(huán)    1 3 4
	* .。。,。,。     1  3
	* .。,。,。。    1
	* 最終結(jié)果   1 3 4 6
	* @param t
	*/
	public static void sort(int[] t) {
		for(int i=0;i<t.length;i++) {
			int temp;
			for(int j = 0;j<t.length-1-i;j++) {
				if(t[j]>t[j+1]) {
					temp = t[j];
					t[j]=t[j+1];
					t[j+1]=temp;
				}
			}
		}
	}
	/**
	* 冒泡排序  對(duì)象類(lèi)型排序
	* 對(duì)象必須實(shí)現(xiàn)Comparator接口
	* @param t  要遍歷的數(shù)組
	* @param comparator  定制的遍歷規(guī)則
	*/
	public static <T>void sort(T[] t,Comparator<? super T> comparator) {	
		for(int i = 0;i<t.length-1;i++) {
			T temp;
			for(int j = 1;j<t.length-i;j++) {
				if(comparator.compare(t[j-1], t[j])<0) {
					temp = t[j-1];
					t[j-1]=t[j];
					t[j]=temp;
				}
			}
		}
	}
	/**
	* 傳入任意數(shù)組或?qū)ο?  輸出到控制臺(tái)
	* @author 王福強(qiáng)
	* @Description  前提是傳入的對(duì)象必須重寫(xiě) toString()方法
	* @date 2018年6月8日 下午4:26:06
	* @param obj
	*/
	public static void so(Object obj) {
		String str = '';
		if(obj instanceof int[]) {
			int[] arr = (int[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (int i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof long[]) {
			long[] arr = (long[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (long i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof char[]) {
			char[] arr = (char[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (char i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof short[]) {
			short[] arr = (short[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (short i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof double[]) {
			double[] arr = (double[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (double i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof float[]) {
			float[] arr = (float[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (float i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof Object[]) {
			Object[] arr = (Object[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (Object i : arr) {
				sb.append(i.toString()+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else {
			str=obj.toString();
		}
		System.out.println(str);;
	}
}

最佳情況：T(n) = O(n) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

2,、選擇排序（Selection Sort）

表現(xiàn)最穩(wěn)定的排序算法之一,，因?yàn)闊o(wú)論什么數(shù)據(jù)進(jìn)去都是O(n2)的時(shí)間復(fù)雜度，所以用到它的時(shí)候,，數(shù)據(jù)規(guī)模越小越好,。唯一的好處可能就是不占用額外的內(nèi)存空間了吧。理論上講,，選擇排序可能也是平時(shí)排序一般人想到的最多的排序方法了吧,。

選擇排序(Selection-sort)是一種簡(jiǎn)單直觀的排序算法。它的工作原理：首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后,，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾,。以此類(lèi)推，直到所有元素均排序完畢,。

2.1 算法描述

n個(gè)記錄的直接選擇排序可經(jīng)過(guò)n-1趟直接選擇排序得到有序結(jié)果,。具體算法描述如下：

初始狀態(tài)：無(wú)序區(qū)為R[1..n]，有序區(qū)為空,；
第i趟排序(i=1,2,3…n-1)開(kāi)始時(shí),，當(dāng)前有序區(qū)和無(wú)序區(qū)分別為R[1..i-1]和R(i..n）。該趟排序從當(dāng)前無(wú)序區(qū)中-選出關(guān)鍵字最小的記錄 R[k],，將它與無(wú)序區(qū)的第1個(gè)記錄R交換,，使R[1..i]和R[i+1..n)分別變?yōu)橛涗泜€(gè)數(shù)增加1個(gè)的新有序區(qū)和記錄個(gè)數(shù)減少1個(gè)的新無(wú)序區(qū)；
n-1趟結(jié)束,，數(shù)組有序化了,。

2.2 動(dòng)圖演示

2.3 代碼實(shí)現(xiàn)


package cn.fuqiang.arithmetic;
import java.util.Comparator;
/**
* 選擇排序  的兩種實(shí)現(xiàn)方式
* (在這里要注意，因?yàn)樽詈笠粋€(gè)位置的數(shù)絕對(duì)是最后循環(huán)后最大的值,，
* 所以外層循環(huán)的循環(huán)次數(shù) 最好是arr.length-1).
* @author 王福強(qiáng)
* @Title: SelectionSort.java
* @Package cn.fuqiang.arithmetic
* @Description
* @date 2018年6月8日 下午5:30:59
*/
public class SelectionSort {
	public static void main(String[] args) {
		int[] arr = {4,1,5,3,8,10,28,2};
		sort(arr);
		so(arr);
		Integer[] arr2 = {4,1,5,3,8,10,28,2};
		sort(arr2,(a,b)-> b.compareTo(a));
		so(arr2);
	}
	/**
	* 選擇排序   第一種實(shí)現(xiàn)方式  (賦值)    升序   （特點(diǎn) ：從小到大）
	* 原理: 每次把最小的都放在前面,，
	* 外層循環(huán)控制每次遍歷的次數(shù)，內(nèi)層循環(huán)替換每次找出來(lái)的最小值，放在  arr[i]的位置
	* 這樣當(dāng)內(nèi)層比較和替換的時(shí)候,，就保證每次最小的都在最前面
	* 例如：3 2 6 1
	* 第一次外層循環(huán)為  i 為  0    第一個(gè)就是最小的值放最小的值
	* 內(nèi)層循換會(huì)把每次找出的最小值放在arr[0] 的位置
	* 第二次外層循環(huán)為 i 為 1
	* 內(nèi)層循環(huán)會(huì)把每次找出最小的值放在 arr[1] 的位置
	*
	* 外循環(huán)    第一次   i=0
	* 內(nèi)部循環(huán)
	* 第一次  2 3 6 1
	* 第二次  2 3 6 1
	* 第三次  1 3  6 2
	*
	* 外循環(huán)    第二次   i=1
 	* 內(nèi)部循環(huán)
 	* 第一次  3 6 1
	* 第二次  1 6 3
	*
	* 外循環(huán)    第三次   i=2
 	* 內(nèi)部循環(huán)
 	* 第一次  3  6
	*
	*
	* @author 王福強(qiáng)
	* @Description
	* @date 2018年6月8日 下午6:36:42
	* @param arr int類(lèi)型數(shù)組
	*/
	public static void sort(int[] arr) {
		for(int i = 0;i<arr.length-1;i++) {
			int temp;
			for(int j = i+1 ; j <arr.length ; j++) {
				if(arr[i]>arr[j]) {
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
	}
	/**
	* 選擇排序  第二種實(shí)現(xiàn)(記錄下標(biāo))  升序   （特點(diǎn) ：從小到大）
	* 每次循環(huán)記錄最小的下標(biāo) min 最后跟 arr[i] 位置的下標(biāo)交換位置
	* 這樣當(dāng)外層循環(huán)每次循環(huán)一次 會(huì)先記下  arr[i] 的下標(biāo),，
	* 然后讓內(nèi)層循環(huán)從 i+1 開(kāi)始比較去比較  arr[min] 與 arr[j]
	* 如果 min下表對(duì)應(yīng)的值 比  j下標(biāo)對(duì)應(yīng)的值大， 則記錄 j的下標(biāo)    min  = j
	* 然后拿新的 min下標(biāo)去跟后面比較,，依此類(lèi)推,。
	* 當(dāng)內(nèi)層循環(huán)循環(huán)結(jié)束后記錄的下標(biāo)是剩余數(shù)中最小的呢個(gè)值的下標(biāo)
	* 然后用一個(gè)零時(shí)變量將他們的值交換過(guò)來(lái)，就算本身是最小的,，也是替換自己
	* 例如  1 3 6 2
	*
	* 第一次外層循環(huán)結(jié)束后
	*  1 3 6 2
	* 第二次外循開(kāi)始時(shí),，會(huì)記錄i的下標(biāo)
	* 然后開(kāi)始內(nèi)層循環(huán)，會(huì)記錄2的下標(biāo)
	* 內(nèi)層循環(huán)結(jié)束后,，會(huì)把  3 與 2的位置調(diào)換
	* 2 6 3
	* ,。。,。,。。
	* ,。,。。,。
	* 3 6
	*
	* @author 王福強(qiáng)
	* @Description
	* @date 2018年6月9日 下午2:13:42
	* @param arr
	* @param comparator
	*/
	public static <T>void sort(T[] arr,Comparator<T> comparator) {
		for(int i = 0;i<arr.length-1;i++) {
			int min=i;
			T temp=null;
			for(int j = i+1 ; j <arr.length ; j++) {
				if(comparator.compare(arr[min], arr[j])<0) {
					min = j;
				}
			}
			temp = arr[i];
			arr[i] = arr[min];
			arr[min] = temp;
		}
	}
	/**
	* 傳入任意數(shù)組或?qū)ο?  輸出到控制臺(tái)
	* @author 王福強(qiáng)
	* @Description  前提是傳入的對(duì)象必須重寫(xiě) toString()方法
	* @date 2018年6月8日 下午4:26:06
	* @param obj
	*/
	public static void so(Object obj) {
		String str = '';
		if(obj instanceof int[]) {
			int[] arr = (int[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (int i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof long[]) {
			long[] arr = (long[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (long i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof char[]) {
			char[] arr = (char[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (char i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof short[]) {
			short[] arr = (short[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (short i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof double[]) {
			double[] arr = (double[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (double i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof float[]) {
			float[] arr = (float[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (float i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof Object[]) {
			Object[] arr = (Object[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (Object i : arr) {
				sb.append(i.toString()+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else {
			str=obj.toString();
		}
		System.out.println(str);;
	}
}

2.4 算法分析

最佳情況：T(n) = O(n2) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

3,、插入排序（Insertion Sort）

插入排序（Insertion-Sort）的算法描述是一種簡(jiǎn)單直觀的排序算法。它的工作原理是通過(guò)構(gòu)建有序序列,，對(duì)于未排序數(shù)據(jù),，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入,。插入排序在實(shí)現(xiàn)上,，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過(guò)程中,，需要反復(fù)把已排序元素逐步向后挪位,，為最新元素提供插入空間。

3.1 算法描述

一般來(lái)說(shuō),，插入排序都采用in-place在數(shù)組上實(shí)現(xiàn),。具體算法描述如下：

從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序,；
取出下一個(gè)元素,，在已經(jīng)排序的元素序列中從后向前掃描；
如果該元素（已排序）大于新元素,，將該元素移到下一位置,；
重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置,；
將新元素插入到該位置后,；
重復(fù)步驟2~5。

3.2 動(dòng)圖演示

3.2 代碼實(shí)現(xiàn)


package cn.fuqiang.arithmetic;
import java.util.Comparator;
/**
* 插入排序
* @author 王福強(qiáng)
* @Title: InsertionSort.java
* @Package cn.fuqiang.arithmetic
* @Description
* @date 2018年6月11日 下午2:19:55
*/
public class InsertionSort {
	public static void main(String[] args) {
		int[] arr = {4,1,5,3,8,10,28,2};
		sort(arr);
		so(arr);
		Integer[] arr2 = {4,1,5,3,8,10,28,2};
		sort(arr2,(a,b)-> b.compareTo(a));
		so(arr2);
	}
	/**
	* 插入排序   升序(特點(diǎn):拿當(dāng)前下標(biāo)值與前面的值比較,，將小的值排在對(duì)應(yīng)的位置,，把大的往后移)
	* 循環(huán)從 i=1  開(kāi)始      用temp記錄當(dāng)前位置的值arr[i]，
	* 然后設(shè)置內(nèi)部循環(huán)控制下標(biāo),，通過(guò)循環(huán)將下標(biāo)每次減一,。
	* 然后判斷temp與arr[index]的大小， 如果temp小于arr[index]則將arr[index-1]值移動(dòng)到下一個(gè)位置,，
	* 然后將下標(biāo)往前挪一位 也就是 index-1 (因?yàn)榈谝淮伪容^時(shí)記錄了 temp = arr[i] 所以不用擔(dān)心會(huì)將值覆蓋)
	* 如果不進(jìn)入內(nèi)循環(huán)則說(shuō)明,，下標(biāo)已經(jīng)移動(dòng)到最前面了沒(méi)有比該值更小的了，
	* 這時(shí)候就把記錄的 temp 賦值給  index+1 的位置上(因?yàn)閕ndex已經(jīng)減到前一個(gè)了)
	* 比較第一個(gè)位置 和第二個(gè)位置的
	* 例如  3 1 6 2
	* 外循環(huán)第一次  i=1
	* 外層循環(huán)直接從  下標(biāo)為一的開(kāi)始
	* 比較1 與3的大小,，然后把3的位置移動(dòng)到后面一位,，
	* 應(yīng)為內(nèi)層循環(huán)index--后小于0了，所以不在循環(huán),，
	* 然后因?yàn)榘?移動(dòng)到后面一位的時(shí)候前面空了一個(gè)位置,，所以就把1插入
	* 1 3 6  2
	* 。,。,。。
	* 外循環(huán)第三次  i=3
	* 比較  2 與 6 然后把6往后移
	* 比較  2與3把三往后移
	* 然后比較2與1    把 2 插入到空缺位置
	*
	* @author 王福強(qiáng)
	* @Description
	* @date 2018年6月11日 下午4:22:41
	* @param arr
	*/
	public static void sort(int[] arr) {
		for(int i = 1 ; i < arr.length ; i ++) {
			int index = i-1;
			int temp = arr[i];
			while(index>=0 && arr[index]>temp) {
				arr[index+1] = arr[index--];
			}
			arr[index+1] = temp;
		}
	}
	/**
	* 對(duì)任意對(duì)象排序
	* @author 王福強(qiáng)
	* @Description
	* @date 2018年6月13日 上午10:52:31
	* @param arr
	* @param comparator
	*/
	public static <T>void sort(T[] arr,Comparator<T> comparator) {
		for(int i = 1;i<arr.length;i++) {
			T temp=arr[i];
			int index;
			for(index = i-1;index>=0 && comparator.compare(arr[index], temp)<0;index--) {
				arr[index+1]=arr[index];
			}
			arr[index+1] =temp;
		}
	}
	/**
	* 傳入任意數(shù)組或?qū)ο?  輸出到控制臺(tái)
	* @author 王福強(qiáng)
	* @Description  前提是傳入的對(duì)象必須重寫(xiě) toString()方法
	* @date 2018年6月8日 下午4:26:06
	* @param obj
	*/
	public static void so(Object obj) {
		String str = obj.toString();
		if(obj instanceof int[]) {
			int[] arr = (int[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (int i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof long[]) {
			long[] arr = (long[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (long i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof char[]) {
			char[] arr = (char[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (char i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof short[]) {
			short[] arr = (short[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (short i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof double[]) {
			double[] arr = (double[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (double i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof float[]) {
			float[] arr = (float[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (float i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof Object[]) {
			Object[] arr = (Object[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (Object i : arr) {
				sb.append(i.toString()+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else {
			str=obj.toString();
		}
		System.out.println(str);;
	}
}

3.4 算法分析

最佳情況：T(n) = O(n) 最壞情況：T(n) = O(n2) 平均情況：T(n) = O(n2)

4,、希爾排序（Shell Sort）

1959年Shell發(fā)明,，第一個(gè)突破O(n^2)的排序算法，是簡(jiǎn)單插入排序的改進(jìn)版,。它與插入排序的不同之處在于,，它會(huì)優(yōu)先比較距離較遠(yuǎn)的元素,。希爾排序又叫縮小增量排序,。

希爾排序的核心在于間隔序列的設(shè)定。既可以提前設(shè)定好間隔序列,，也可以動(dòng)態(tài)的定義間隔序列,。動(dòng)態(tài)定義間隔序列的算法是《算法（第4版》的合著者Robert Sedgewick提出的?！?/p>

4.1 算法描述

先將整個(gè)待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序,，具體算法描述：

選擇一個(gè)增量序列t1，t2,，…,，tk，其中ti>tj，tk=1,；
按增量序列個(gè)數(shù)k,，對(duì)序列進(jìn)行k 趟排序；
每趟排序,，根據(jù)對(duì)應(yīng)的增量ti,，將待排序列分割成若干長(zhǎng)度為m 的子序列，分別對(duì)各子表進(jìn)行直接插入排序,。僅增量因子為1 時(shí),，整個(gè)序列作為一個(gè)表來(lái)處理，表長(zhǎng)度即為整個(gè)序列的長(zhǎng)度,。

4.2 過(guò)程演示

4.3 代碼實(shí)現(xiàn)


package cn.fuqiang.arithmetic;
import java.util.Comparator;
/**
* 希爾排序
* (建議：研究希爾排序前先理解插入排序)
* @author 王福強(qiáng)
* @Title: ShellSort.java
* @Package cn.fuqiang.arithmetic
* @Description
* @date 2018年6月11日 下午7:23:24
*/
public class ShellSort {
	public static void main(String[] args) {
		int[] arr = {4,1,5,3,8,10,28,2};
	sort(arr);
		so(arr);
		Integer[] arr2 = {4,1,5,3,8,10,28,2};
		sort(arr2,(a,b)-> a.compareTo(b));
		so(arr2);
	}
	/**
	* 希爾排序      升序(特點(diǎn)：縮小增量排序  ,，是插入排序的改進(jìn)版)
	* increment是用來(lái)記錄增量的
	*講解：
	* while(increment > 1)
	* 最外層的  while循環(huán)是用來(lái)控制增量的。增量要從大到小
	* increment =increment/3+1;
	* 當(dāng)每次循環(huán)后都吧增量除以一個(gè)數(shù)(改數(shù)不能是2和1 否則會(huì)死循環(huán))加一
	* 保證最后除盡后不能小于一,，應(yīng)為最后增量縮小為一后需要兩兩之間進(jìn)行比較(此處也就是縮小增量)
	*
	* for (int i = increment; i < arr.length; i++) {
	* 中間for循環(huán),，控制每次要取出的比較的元素，從增量開(kāi)始,，每次加一
	* int temp = arr[i];
	* 用一個(gè)零是變量接受要比較的值
	* arr[j+increment] = temp;
	* 因?yàn)樵趦?nèi)層循環(huán)中已將前面的值移動(dòng)到后面了,，在最后一次 循環(huán)結(jié)束后 j -= increment 已經(jīng)少了一個(gè)增量
	* 所以j+increment 正好是移動(dòng)后最后空出來(lái)的一個(gè) 所以把temp替換給該值，完成交換
	* 就算沒(méi)有進(jìn)入內(nèi)層循環(huán),，呢j=i-incement后再+incement就還是 i本身temp也就是arr[i]本身
	*
	* for (j = i-increment; j >= 0 && arr[j]> temp ; j-=increment) {
	* 最內(nèi)層的for循環(huán)是用來(lái)控制temp 與每個(gè)j-increment個(gè)值比較,，從 j=i-increment開(kāi)始 也就是中層循中  i減去一個(gè)增量后的下標(biāo)(與插入排序相同，只不過(guò)是每次跟前increment個(gè)值比較)
	* j >= 0 && arr[j]> temp
	* 該判斷是防止j減到負(fù)下標(biāo)并且每次替換的實(shí)話 只有temp小于arr[j]才可以進(jìn)入
	* arr[j+increment] = arr[j];
	* 如果arr[j]> temp  呢么與將 arr[j]的值移動(dòng)道后面
	*
	* 例如
	* 4,1,5,3,8,10,28,2   長(zhǎng)度為 8
	* while循環(huán)第一次
	*  	 increment = 3
	*   中層for循環(huán) i從 3開(kāi)始
	*        temp = arr[3]
	* 		    內(nèi)層for循環(huán)從j=i-increment  也就是從前increment個(gè)值開(kāi)始
	* 		    就會(huì)拿出arr[3-3]>temp 比較
	* 		    如果temp小則 把 arr[3-3] 的值與 的值賦給arr[0+3]  也就是 arr[j+increment] = arr[j]
	* 		    因?yàn)閍rr[3]已經(jīng)記錄,，所以當(dāng) j-=increment時(shí) j=-3此時(shí)已經(jīng)不滿(mǎn)足 j >= 0 所以?xún)?nèi)層循環(huán)結(jié)束
	* 		    內(nèi)層循環(huán)結(jié)束后  arr的值就從4,1,5,3,8,10,28,2  變?yōu)榱?   4,1,5,4,8,10,28,2
	* 		    因?yàn)樵趦?nèi)層循環(huán)中只是把   0下標(biāo)的值賦給了3下標(biāo) 所以說(shuō) 0位置的值還是4
	*     此時(shí)中層循環(huán)中的 arr[j+increment] = temp; 就是把原來(lái)記錄的 arr[3]----3  賦給0下標(biāo),，
	*     因?yàn)閖已經(jīng)被減了increment 變成了-3所以此時(shí)加上increment正好等于0下標(biāo)
	*     所以arr就變成了  3,1,5,4,8,10,28,2
	*
	*   中層for循環(huán) i變?yōu)榱?
	*      temp = arr[4]
	* 		內(nèi)層for循環(huán)從j=i-increment  也就是從前increment個(gè)值開(kāi)始
	* 		就會(huì)拿出arr[4-3]>temp 比較
	* 		因?yàn)閍rr[1]小于temp所以 而且j也已經(jīng)=-1所以循環(huán)結(jié)束
	* 	。,。,。。,。,。。,。,。 以此類(lèi)推
	*	
	*
	* @author 王福強(qiáng)
	* @Description
	* @date 2018年6月14日 下午5:33:04
	* @param arr
	*/
	public static void sort(int[] arr) {
		int  increment = arr.length;
	while(increment > 1) {    //動(dòng)態(tài)定義間隔序列
	    	increment =increment/3+1;
 	    	for (int i = increment; i < arr.length; i++) {
 	int temp = arr[i];
 	int j ;
	for (j = i-increment; j >= 0 && arr[j]> temp ; j-=increment) {
	            	arr[j+increment] = arr[j];
	}
	arr[j+increment] = temp;
 	}
	}
	}
	/**
	* 任意對(duì)象排序，將上面排序中 內(nèi)部的循環(huán)替換為了while循環(huán)
	* @author 王福強(qiáng)
	* @Description
	* @date 2018年6月15日 下午3:45:06
	* @param arr
	* @param comparator
	*/
	public static <T>void sort(T[] arr,Comparator<T> comparator){
		int  increment = arr.length;
	while(increment > 1) {    //動(dòng)態(tài)定義間隔序列
	    	increment =increment/3+1;
 	    	for (int i = increment; i < arr.length; i++) {
 	T temp = arr[i];
 	int j = i-increment;
	while ( j >= 0 && comparator.compare(arr[j], temp)>0  ) {
	            	arr[j+increment] = arr[j];
	            	j-=increment;
	}
	arr[j+increment] = temp;
 	}
	}
	}
	/**
	* 傳入任意數(shù)組或?qū)ο?  輸出到控制臺(tái)
	* @author 王福強(qiáng)
	* @Description  前提是傳入的對(duì)象必須重寫(xiě) toString()方法
	* @date 2018年6月8日 下午4:26:06
	* @param obj
	*/
	public static void so(Object obj) {
		String str = obj.toString();
		if(obj instanceof int[]) {
			int[] arr = (int[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (int i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof long[]) {
			long[] arr = (long[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (long i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof char[]) {
			char[] arr = (char[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (char i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof short[]) {
			short[] arr = (short[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (short i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof double[]) {
			double[] arr = (double[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (double i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof float[]) {
			float[] arr = (float[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (float i : arr) {
				sb.append(i+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else if(obj instanceof Object[]) {
			Object[] arr = (Object[])obj;
			StringBuilder sb = new StringBuilder();
			sb.append('[');
			for (Object i : arr) {
				sb.append(i.toString()+',');
			}
			str = sb.substring(0,sb.lastIndexOf(','))+']' ;
		}else {
			str=obj.toString();
		}
		System.out.println(str);
	}
}

4.4 算法分析

最佳情況：T(n) = O(nlog2 n) 最壞情況：T(n) = O(nlog2 n) 平均情況：T(n) =O(nlog n)　

5,、歸并排序（Merge Sort）

和選擇排序一樣,，歸并排序的性能不受輸入數(shù)據(jù)的影響，但表現(xiàn)比選擇排序好的多,，因?yàn)槭冀K都是O(n log n）的時(shí)間復(fù)雜度,。代價(jià)是需要額外的內(nèi)存空間,。

歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用,。歸并排序是一種穩(wěn)定的排序方法,。將已有序的子序列合并，得到完全有序的序列,；即先使每個(gè)子序列有序,，再使子序列段間有序。若將兩個(gè)有序表合并成一個(gè)有序表,，稱(chēng)為2-路歸并,。

5.1 算法描述

把長(zhǎng)度為n的輸入序列分成兩個(gè)長(zhǎng)度為n/2的子序列；
對(duì)這兩個(gè)子序列分別采用歸并排序,；
將兩個(gè)排序好的子序列合并成一個(gè)最終的排序序列,。

5.2 動(dòng)圖演示

5.3 代碼實(shí)現(xiàn)

function mergeSort(arr) { //采用自上而下的遞歸方法

var len = arr.length;

if(len < 2) {

return arr;

}

var middle = Math.floor(len / 2),

left = arr.slice(0, middle),

right = arr.slice(middle);

return merge(mergeSort(left), mergeSort(right));

}

function merge(left, right)

{

var result = [];

while (left.length>0 && right.length>0) {

if (left[0] <= right[0]) {

result.push(left.shift());

}else {

result.push(right.shift());

}

while (left.length)

result.push(left.shift());

while (right.length)

result.push(right.shift());

return result;

}

5. 4 算法分析

最佳情況：T(n) = O(n) 最差情況：T(n) = O(nlogn) 平均情況：T(n) = O(nlogn)

6、快速排序（Quick Sort）

快速排序的基本思想：通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分,，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小,，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序,。

6.1 算法描述

快速排序使用分治法來(lái)把一個(gè)串（list）分為兩個(gè)子串（sub-lists）,。具體算法描述如下：

從數(shù)列中挑出一個(gè)元素，稱(chēng)為 “基準(zhǔn)”（pivot）,；
重新排序數(shù)列,，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）,。在這個(gè)分區(qū)退出之后,，該基準(zhǔn)就處于數(shù)列的中間位置。這個(gè)稱(chēng)為分區(qū)（partition）操作,；
遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序,。

5.2 動(dòng)圖演示

5.3 代碼實(shí)現(xiàn)

function quickSort(arr, left, right) {

var len = arr.length,

partitionIndex,

left =typeof left !='number' ? 0 : left,

right =typeof right !='number' ? len - 1 : right;

if (left < right) {

partitionIndex = partition(arr, left, right);

quickSort(arr, left, partitionIndex-1);

quickSort(arr, partitionIndex+1, right);

}

return arr;

}

function partition(arr, left ,right) { //分區(qū)操作

var pivot = left, //設(shè)定基準(zhǔn)值（pivot）

index = pivot + 1;

for (var i = index; i <= right; i++) {

if (arr[i] < arr[pivot]) {

swap(arr, i, index);

index++;

}

swap(arr, pivot, index - 1);

return index-1;

}

function swap(arr, i, j) {

var temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

5.4 算法分析

最佳情況：T(n) = O(nlogn) 最差情況：T(n) = O(n2) 平均情況：T(n) = O(nlogn)　

7、堆排序（Heap Sort）

堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法,。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu),，并同時(shí)滿(mǎn)足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

7.1 算法描述

將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆,，此堆為初始的無(wú)序區(qū),；
將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無(wú)序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿(mǎn)足R[1,2…n-1]<=R[n],；
由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆,，然后再次將R[1]與無(wú)序區(qū)最后一個(gè)元素交換,，得到新的無(wú)序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn),。不斷重復(fù)此過(guò)程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過(guò)程完成,。

7.2 動(dòng)圖演示

7.3 代碼實(shí)現(xiàn)

var len; //因?yàn)槁暶鞯亩鄠€(gè)函數(shù)都需要數(shù)據(jù)長(zhǎng)度,，所以把len設(shè)置成為全局變量

function buildMaxHeap(arr) { //建立大頂堆

len = arr.length;

for (var i = Math.floor(len/2); i >= 0; i--) {

heapify(arr, i);

}

function heapify(arr, i) { //堆調(diào)整

var left = 2 * i + 1,

right = 2 * i + 2,

largest = i;

if (left < len && arr[left] > arr[largest]) {

largest = left;

}

if (right < len && arr[right] > arr[largest]) {

largest = right;

}

if (largest != i) {

swap(arr, i, largest);

heapify(arr, largest);

}

function swap(arr, i, j) {

var temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

function heapSort(arr) {

buildMaxHeap(arr);

for (var i = arr.length-1; i > 0; i--) {

swap(arr, 0, i);

len--;

heapify(arr, 0);

}

return arr;

}

7.4 算法分析

最佳情況：T(n) = O(nlogn) 最差情況：T(n) = O(nlogn) 平均情況：T(n) = O(nlogn)

8、計(jì)數(shù)排序（Counting Sort）

計(jì)數(shù)排序的核心在于將輸入的數(shù)據(jù)值轉(zhuǎn)化為鍵存儲(chǔ)在額外開(kāi)辟的數(shù)組空間中,。作為一種線性時(shí)間復(fù)雜度的排序,，計(jì)數(shù)排序要求輸入的數(shù)據(jù)必須是有確定范圍的整數(shù)。

計(jì)數(shù)排序(Counting sort)是一種穩(wěn)定的排序算法,。計(jì)數(shù)排序使用一個(gè)額外的數(shù)組C,，其中第i個(gè)元素是待排序數(shù)組A中值等于i的元素的個(gè)數(shù)。然后根據(jù)數(shù)組C來(lái)將A中的元素排到正確的位置,。它只能對(duì)整數(shù)進(jìn)行排序,。

8.1 算法描述

找出待排序的數(shù)組中最大和最小的元素；
統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù),，存入數(shù)組C的第i項(xiàng),；
對(duì)所有的計(jì)數(shù)累加（從C中的第一個(gè)元素開(kāi)始，每一項(xiàng)和前一項(xiàng)相加）,；
反向填充目標(biāo)數(shù)組：將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng),，每放一個(gè)元素就將C(i)減去1。

8.2 動(dòng)圖演示

8.3 代碼實(shí)現(xiàn)

function countingSort(arr, maxValue) {

var bucket =new Array(maxValue+1),

sortedIndex = 0;

arrLen = arr.length,

bucketLen = maxValue + 1;

for (var i = 0; i < arrLen; i++) {

if (!bucket[arr[i]]) {

bucket[arr[i]] = 0;

}

bucket[arr[i]]++;

}

for (var j = 0; j < bucketLen; j++) {

while(bucket[j] > 0) {

arr[sortedIndex++] = j;

bucket[j]--;

}

return arr;

}

8.4 算法分析

當(dāng)輸入的元素是n 個(gè)0到k之間的整數(shù)時(shí),，它的運(yùn)行時(shí)間是 O(n + k),。計(jì)數(shù)排序不是比較排序，排序的速度快于任何比較排序算法,。由于用來(lái)計(jì)數(shù)的數(shù)組C的長(zhǎng)度取決于待排序數(shù)組中數(shù)據(jù)的范圍（等于待排序數(shù)組的最大值與最小值的差加上1）,，這使得計(jì)數(shù)排序?qū)τ跀?shù)據(jù)范圍很大的數(shù)組，需要大量時(shí)間和內(nèi)存,。

最佳情況：T(n) = O(n+k) 最差情況：T(n) = O(n+k) 平均情況：T(n) = O(n+k)

9,、桶排序（Bucket Sort）

桶排序是計(jì)數(shù)排序的升級(jí)版。它利用了函數(shù)的映射關(guān)系,，高效與否的關(guān)鍵就在于這個(gè)映射函數(shù)的確定,。

桶排序 (Bucket sort)的工作的原理：假設(shè)輸入數(shù)據(jù)服從均勻分布，將數(shù)據(jù)分到有限數(shù)量的桶里,，每個(gè)桶再分別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進(jìn)行排

9.1 算法描述

設(shè)置一個(gè)定量的數(shù)組當(dāng)作空桶,；
遍歷輸入數(shù)據(jù)，并且把數(shù)據(jù)一個(gè)一個(gè)放到對(duì)應(yīng)的桶里去,；
對(duì)每個(gè)不是空的桶進(jìn)行排序,；
從不是空的桶里把排好序的數(shù)據(jù)拼接起來(lái)。

9.2 圖片演示

9.3 代碼實(shí)現(xiàn)

function bucketSort(arr, bucketSize) {

if (arr.length === 0) {

return arr;

}

var i;

var minValue = arr[0];

var maxValue = arr[0];

for (i = 1; i < arr.length; i++) {

if (arr[i] < minValue) {

minValue = arr[i]; //輸入數(shù)據(jù)的最小值

}else if (arr[i] > maxValue) {

maxValue = arr[i]; //輸入數(shù)據(jù)的最大值

}

//桶的初始化

var DEFAULT_BUCKET_SIZE = 5; //設(shè)置桶的默認(rèn)數(shù)量為5

bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;

var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;

var buckets =new Array(bucketCount);

for (i = 0; i < buckets.length; i++) {

buckets[i] = [];

}

//利用映射函數(shù)將數(shù)據(jù)分配到各個(gè)桶中

for (i = 0; i < arr.length; i++) {

buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);

}

arr.length = 0;

for (i = 0; i < buckets.length; i++) {

insertionSort(buckets[i]); //對(duì)每個(gè)桶進(jìn)行排序,，這里使用了插入排序

for (var j = 0; j < buckets[i].length; j++) {

arr.push(buckets[i][j]);

}

return arr;

}

9.4 算法分析

桶排序最好情況下使用線性時(shí)間O(n),，桶排序的時(shí)間復(fù)雜度,，取決與對(duì)各個(gè)桶之間數(shù)據(jù)進(jìn)行排序的時(shí)間復(fù)雜度，因?yàn)槠渌糠值臅r(shí)間復(fù)雜度都為O(n),。很顯然,，桶劃分的越小，各個(gè)桶之間的數(shù)據(jù)越少,，排序所用的時(shí)間也會(huì)越少,。但相應(yīng)的空間消耗就會(huì)增大。

最佳情況：T(n) = O(n+k) 最差情況：T(n) = O(n+k) 平均情況：T(n) = O(n2)　　

10,、基數(shù)排序（Radix Sort）

基數(shù)排序也是非比較的排序算法,，對(duì)每一位進(jìn)行排序，從最低位開(kāi)始排序,，復(fù)雜度為O(kn),為數(shù)組長(zhǎng)度,，k為數(shù)組中的數(shù)的最大的位數(shù)；

基數(shù)排序是按照低位先排序,，然后收集,；再按照高位排序，然后再收集,；依次類(lèi)推,，直到最高位。有時(shí)候有些屬性是有優(yōu)先級(jí)順序的,，先按低優(yōu)先級(jí)排序,，再按高優(yōu)先級(jí)排序。最后的次序就是高優(yōu)先級(jí)高的在前,，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的在前,。基數(shù)排序基于分別排序,，分別收集,，所以是穩(wěn)定的。

10.1 算法描述

取得數(shù)組中的最大數(shù),，并取得位數(shù),；
arr為原始數(shù)組，從最低位開(kāi)始取每個(gè)位組成radix數(shù)組,；
對(duì)radix進(jìn)行計(jì)數(shù)排序（利用計(jì)數(shù)排序適用于小范圍數(shù)的特點(diǎn)）,；

10.2 動(dòng)圖演示

10.3 代碼實(shí)現(xiàn)

//LSD Radix Sort

var counter = [];

function radixSort(arr, maxDigit) {

var mod = 10;

var dev = 1;

for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {

for(var j = 0; j < arr.length; j++) {

var bucket = parseInt((arr[j] % mod) / dev);

if(counter[bucket]==null) {

counter[bucket] = [];

}

counter[bucket].push(arr[j]);

}

var pos = 0;

for(var j = 0; j < counter.length; j++) {

var value =null;

if(counter[j]!=null) {

while ((value = counter[j].shift()) !=null) {

arr[pos++] = value;

}

return arr;

}

10.4 算法分析

最佳情況：T(n) = O(n * k) 最差情況：T(n) = O(n * k) 平均情況：T(n) = O(n * k)

基數(shù)排序有兩種方法：

MSD 從高位開(kāi)始進(jìn)行排序 LSD 從低位開(kāi)始進(jìn)行排序

基數(shù)排序 vs 計(jì)數(shù)排序 vs 桶排序

這三種排序算法都利用了桶的概念，但對(duì)桶的使用方法上有明顯差異：

基數(shù)排序：根據(jù)鍵值的每位數(shù)字來(lái)分配桶
計(jì)數(shù)排序：每個(gè)桶只存儲(chǔ)單一鍵值
桶排序：每個(gè)桶存儲(chǔ)一定范圍的數(shù)值

參考資料：

http://blog.csdn.net/fengyinchao/article/details/52667625

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間,，所有內(nèi)容均由用戶(hù)發(fā)布,，不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購(gòu)買(mǎi)等信息,，謹(jǐn)防詐騙,。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,，請(qǐng)點(diǎn)擊一鍵舉報(bào),。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自：好漢勃士 > 《操作系統(tǒng)綜述》

舉報(bào)/認(rèn)領(lǐng)