轉(zhuǎn)載請標明出處乡翅，謝謝怀吻！
http://www.reibang.com/p/176b0b892591
關(guān)聯(lián)文章
排序 http://www.reibang.com/p/176b0b892591
棧和隊列 http://www.reibang.com/p/8cb602ef4e21
順序表刘陶、單雙鏈表 http://www.reibang.com/p/3aeb5998e79e
二叉樹 http://www.reibang.com/p/de829eab944c
圖論 http://www.reibang.com/p/cf03e51a3ca2
詳細的各種排序
https://www.cnblogs.com/ll409546297/p/10956960.html
冒泡排序和選擇排序榛鼎，適合個位數(shù)的排序
冒泡排序（Bubble Sort）
一種計算機科學領(lǐng)域的較簡單的排序算法鲫惶。
它重復地走訪過要排序的元素列，依次比較兩個相鄰的元素岗憋，如果他們的順序（如從大到小肃晚、首字母從A到Z）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到?jīng)]有相鄰元素需要交換仔戈，也就是說該元素已經(jīng)排序完成关串。
這個算法的名字由來是因為越大的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣监徘，故名“冒泡排序”晋修。
冒泡排序簡單的講就是相鄰的兩個數(shù)字對比，大的數(shù)往后推凰盔。
private void bubbleSort(int[] array){
for (int i = 0; i <array.length-1 ; i++) {
if(array[i]>array[i+1]){
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
print(array);
}
輸出的結(jié)果是：
第一輪下來 已經(jīng)把最大的數(shù)字9往后推到最后一位墓卦。 接下來就要比較1 3 5 2 ->1 3 2 5 然后是1 3 2 所以按照這個思路再最外面加一個for循環(huán)就可以將數(shù)組排序
private void bubbleSort(int[] array){
for (int j = 0; j <array.length - 1 ; j++) {
for (int i = 0; i <array.length-1 - j ; i++) {
if(array[i]>array[i+1]){
int temp = array[i];
array[i] = array[i+1];
array[i+1] = temp;
}
}
}
print(array);
}
我們看下，這是最基本的冒泡排序?qū)懛ɑЬ础Ｄ敲次覀兛聪滤臅r間復雜度是多少落剪？冒泡排序的時間復雜度是O(n2)。這是冒泡排序的最差時間復雜度尿庐。那么他有沒有優(yōu)化的方案呢忠怖？
有！ 我們可以假設(shè)下 如果一開始的數(shù)組數(shù)據(jù)就是從小到大排序好的呢抄瑟？ 那么真正的有效代碼時間復雜度是O(n)凡泣，因為if語句根本就走不進去。 我們看下代碼。
@Test
public void test() {
int[] array = new int[]{1, 2, 3, 4, 5};
bubbleSort(array);
}
private void bubbleSort(int[] array) {
for (int j = 0; j < array.length - 1; j++) {
boolean flag = true;
for (int i = 0; i < array.length - 1 - j; i++) {
if (array[i] > array[i + 1]) {
int temp = array[i];
array[i] = array[i + 1];
array[i + 1] = temp;
flag = false;
}
}
if (flag) {
break;
}
}
print(array);
}
選擇排序
一種簡單直觀的排序算法问麸。它的工作原理很容易理解：初始時在序列中找到最型浴（大）元素，放到序列的起始位置作為已排序序列严卖；然后席舍，再從剩余未排序元素中繼續(xù)尋找最小（大）元素哮笆，放到已排序序列的末尾来颤。以此類推，直到所有元素均排序完畢稠肘。
注意選擇排序與冒泡排序的區(qū)別：冒泡排序通過依次交換相鄰兩個順序不合法的元素位置福铅，從而將當前最小（大）元素放到合適的位置项阴；而選擇排序每遍歷一次都記住了當前最谢（大）元素的位置，最后僅需一次交換操作即可將其放到合適的位置环揽。
先排第一次略荡，首先將第一個數(shù)字固定然后和后面一個數(shù)字3對比 如果4>3就將3的角標賦值給index,然后對換數(shù)字，以此類推歉胶，我們看下結(jié)果：
private void selectionSort() {
int[] array = new int[]{4, 3, 9, 5, 2};
int index = 0;
for (int i = 0 + 1; i < array.length; i++) {
/*如果后者大于第一個數(shù) index重新賦值*/
if (array[index] > array[i]) {
index = i;
}
/*替換兩個數(shù)*/
int temp = array[index];
array[index] = array[0];
array[0] = temp;
}
print(array);
}
按照這樣的思路汛兜，再最外層加上一個循環(huán)進行排序：
private void selectionSort() {
int[] array = new int[]{4, 3, 9, 5, 2};
for (int j = 0; j < array.length - 1; j++) {
int index = j;
for (int i = j + 1; i < array.length; i++) {
/*如果后者大于第一個數(shù) index重新賦值*/
if (array[index] > array[i]) {
index = i;
}
/*替換兩個數(shù)*/
int temp = array[index];
array[index] = array[j];
array[j] = temp;
}
}
print(array);
}
那么這個算法也有優(yōu)化方案嗎？有通今！
private void selectionSort() {
int[] array = new int[]{4, 3, 9, 5, 2};
for (int j = 0; j < array.length - 1; j++) {
int index = j;
for (int i = j + 1; i < array.length; i++) {
/*如果后者大于第一個數(shù) index重新賦值*/
if (array[index] > array[i]) {
index = i;
}
/*替換兩個數(shù)*/
if (index != j) {//如果已經(jīng)是最小的粥谬，就不需要替換
int temp = array[index];
array[index] = array[j];
array[j] = temp;
}
}
}
print(array);
}
插入排序
插入排序類似整理撲克牌，將每一張牌插到其他已經(jīng)有序的牌中適當?shù)奈恢谩?p>
插入排序由N-1趟排序組成辫塌，對于P=1到N-1趟漏策，插入排序保證從位置0到位置P上的元素為已排序狀態(tài)。
簡單的說臼氨，就是插入排序總共需要排序N-1趟哟玷，從index為1開始，講該位置上的元素與之前的元素比較一也，放入合適的位置，這樣循環(huán)下來之后喉脖，即為有序數(shù)組椰苟。
為了看清原理，先模擬三個數(shù)據(jù)
@Test
public void test() {
int[] array = new int[]{2, 4, 1};
insertSort(array);
print(array);
}
//直接插入排序
public void insertSort(int[] array) {
int j = 2;
int target = array[j];
while (j > 0 && target < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
array[j] = target;
}
public void print(int[] array) {
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
}
分析： j=2, target = array[j] = 1;
如果1<4 則替換树叽，然后j = 1, 再替換舆蝴。幾輪下來 1就跑到最前面 輸出的結(jié)果是 1，2，4.
完整代碼：
//直接插入排序
public void insertSort(int[] array) {
for (int i = 0; i <array.length ; i++) {
int j = i;
int target = array[j];
while (j > 0 && target < array[j - 1]) {
array[j] = array[j - 1];
j--;
}
array[j] = target;
}
}
希爾排序
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort）洁仗，是直接插入排序算法的一種更高效的改進版本层皱。希爾排序是非穩(wěn)定排序算法。該方法因D.L.Shell于1959年提出而得名赠潦。
該方法實質(zhì)上是一種分組插入方法
比較相隔較遠距離（稱為增量）的數(shù)叫胖，使得數(shù)移動時能跨過多個元素，則進行一次比較就可能消除多個元素交換她奥。D.L.shell于1959年在以他名字命名的排序算法中實現(xiàn)了這一思想瓮增。算法先將要排序的一組數(shù)按某個增量d分成若干組，每組中記錄的下標相差d.對每組中全部元素進行排序哩俭，然后再用一個較小的增量對它進行绷跑，在每組中再進行排序。當增量減到1時凡资，整個要排序的數(shù)被分成一組砸捏，排序完成。
一般的初次取序列的一半為增量隙赁，以后每次減半垦藏，直到增量為1。
給定實例的shell排序的排序過程
假設(shè)待排序文件有10個記錄鸳谜，其關(guān)鍵字分別是：
49膝藕，38，65咐扭，97芭挽，76，13蝗肪，27袜爪，49，55薛闪，04辛馆。
增量序列的取值依次為：
5，2豁延，1
代碼：
改進剛剛的插入排序
@Test
public void test() {
int[] array = new int[]{2, 4, 1, 44, 3, 22, 7, 8, 9, 444};
//insertSort(array);
shellSort(array, 5);
shellSort(array, 2);
shellSort(array, 1);
print(array);
}
//希爾排序
public void shellSort(int[] array, int step) {
for (int k = 0; k < step; k++) {
for (int i = k + step; i < array.length; i += step) {
int j = i;
int target = array[j];
while (j > step - 1 && target < array[j - step]) {
array[j] = array[j - step];
j -= step;
}
array[j] = target;
}
}
}
堆排序
堆排序（英語：Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法昙篙。堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點诱咏。
堆排序的過程：
1苔可。從最后一個非葉子節(jié)點開始，每三個節(jié)點做一次大小比較袋狞，最小的做根
如果移動過程中如果子樹上的順序被破壞了焚辅，子樹上重新調(diào)整三個節(jié)點的位置
2映屋。取走整個樹的根節(jié)點，把最后一個葉子做為根節(jié)點
3同蜻。重復1和2棚点，直到所有節(jié)點被取走了
舉個例子說明下：有一個數(shù)組 3、6湾蔓、9瘫析、1、2卵蛉、4颁股、5、7傻丝、8
用完全二叉樹表示
根據(jù)堆排序過程
先從1開始
然后從9開始
不用操作甘有。
然后操作6
操作完6 發(fā)現(xiàn) 做左邊的三個節(jié)點需要調(diào)整:
操作3
右小角需要調(diào)整：
上圖就是調(diào)整后的二叉樹。我們發(fā)現(xiàn)9已經(jīng)被推到了最上面葡缰。接著取出9亏掀，將最后一個葉子節(jié)點1作為根節(jié)點
然后重復上面的操作。
代碼：
@Test
public void test(){
int[] array=new int[]{2,3,4,5,6,7,1,8,9};
heapSort(array,array.length);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]+" ");
}
}
/**
* 調(diào)整堆
*/
void maxHeapify(int array[],int start,int end){
//父親的位置
int dad=start;
//兒子的位置
int son=dad*2+1;
while(son<=end){//如果子節(jié)點下標在可以調(diào)整的范圍內(nèi)就一直調(diào)整下去
//如果沒有右孩子就不用比,有的話,比較兩個兒子泛释，選擇最大的出來
if(son+1 <= end && array[son]<array[son+1]){
son++;
}
//和父節(jié)點比大小
if(array[dad]>array[son]){
return;
}else{//父親比兒子小滤愕，就要對整個子樹進行調(diào)整
int temp=array[son];
array[son]=array[dad];
array[dad]=temp;
//遞歸下一層
dad=son;
son=dad*2+1;
}
}
}
void heapSort(int array[],int len){
//建堆 len/2-1最后一個非葉子節(jié)點
for(int i=len/2-1;i>=0;i--){
maxHeapify(array,i,len-1);
}
//排序,根節(jié)點和最后一個節(jié)點交換
//換完以后，取走根怜校，重新建堆
//len-1 最后一個節(jié)點
for(int i=len-1;i>0;i--){
int temp=array[0];
array[0]=array[i];
array[i]=temp;
maxHeapify(array,0,i-1);
}
}
看下八大排序的應用場景
