<h2>前沿：排序算法想必是日常編程中最常用編程技能之一了吧？不知道有多少人和我一樣接觸的第一個(gè)算法就是冒泡排序。筆者將在這里分別介紹選擇排序，插入排序，希爾排序，歸并排序，快速排序。我認(rèn)為這些排序算法都是為了改良前者其時(shí)間復(fù)雜度或空間復(fù)雜度而循序漸進(jìn)的，所以我將用我的理解盡可能通俗易懂的介紹這5種排序算法。</h2>
<h3>開始介紹算法之前還是先把排序模板類的代碼貼一下，里面包括一些簡單的函數(shù),我們后續(xù)排序算法繼承此模板類。</h3>
<pre>
package com.example.sort;
/**
* 插入排序算法
* */
public abstract class SortTamplate {
public abstract void sort(Comparable a[]);
//比較兩個(gè)數(shù)的大小
public static boolean less(Comparable v,Comparable w){
return v.compareTo(w) < 0;
}
//交換兩個(gè)數(shù)
public static void exchange(Comparable a[],int i,int j){
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
//打印數(shù)組
public static void show(Comparable a[]){
for(int i=0;i<a.length;i++){
System.out.print(a[i]+",");
}
}
//數(shù)組是否有序
public static boolean isSort(Comparable a[]){
for(int i=1;i<a.length;i++){
if(less(a[i],a[i-1])){
return false;
}
}
return false;
}
}
</pre>
<h4>首先介紹的就是-選擇排序</h4>
<blockquote>選擇排序即每次遍歷數(shù)組選擇數(shù)組中最小的(或者最大的)數(shù)，將其置于數(shù)組最前面,邏輯很簡單，就不做多解釋了，還是直接上代碼好了。</blockquote>
<pre>
package com.example.sort;
/**
* 選擇排序算法
* */
public class Selection extends SortTamplate{
public void sort(Comparable a[]){
long begin = System.currentTimeMillis();
int N = a.length;
for(int i=0;i<N;i++){
//最小數(shù)索引
int min = i;
//循環(huán)找出數(shù)組中最小的數(shù)的索引
for(int j=i+1;j<N;j++){
if(less(a[j],a[min])){
min = j;
}
}
//將最小數(shù)索引置于數(shù)組前面
exchange(a,i,min);
}
long end = System.currentTimeMillis();
System.out.println("算法用時(shí)："+(end-begin));
}
}
</pre>
<h6>可以從代碼很直觀的看出選擇排序需要N2/2次比較和N次交換，時(shí)間復(fù)雜度為0(n2)。其每次掃描出最小數(shù)對于下一次掃描未提供任何信息，所以對于一個(gè)有序或者部分有序的數(shù)組和完全無序數(shù)組來說，所需的時(shí)間復(fù)雜度是完全相等的。所以，就引出了下一個(gè)排序算法，插入排序。</h6>
<blockquote>
插入排序：顧名思義，往一個(gè)有序數(shù)組中添加一個(gè)數(shù)時(shí)，只需將這個(gè)數(shù)插入到數(shù)組中適當(dāng)?shù)奈恢眉纯伞２迦肱判蚶眠@一點(diǎn)，比較前1到n長度的數(shù)組，這樣做的目的是使每次比較都為后一次比較提供一個(gè)有序的子數(shù)組，后一個(gè)數(shù)只需插入到前一個(gè)子數(shù)組中。
</blockquote>
<pre>
package com.example.sort;
/**
* 插入排序
* */
public class Insertion extends SortTamplate{
public void sort(Comparable a[]){
}
public static void sort(Comparable a[],int low,int high){
long begin = System.currentTimeMillis();
int N = a.length;
for(int i= 0;i<N;i++){
for(int j=i;j>0 && less(a[j],a[j-1]);j--){//重點(diǎn)為此處循環(huán)終止條件
exchange(a,j,j-1);
}
}
long end = System.currentTimeMillis();
System.out.println("算法用時(shí)："+(end-begin));
}
}
</pre>
<h6>所以插入排序非常適合部分有序數(shù)組或者小規(guī)模數(shù)組。然而對于大規(guī)模的亂序數(shù)組插入排序很慢，因?yàn)樗唤粨Q相鄰的元素，因此元素只能一點(diǎn)一點(diǎn)地從一端移動(dòng)到另一端。接下來就介紹一種基于插入排序的快速的排序算法——希爾排序。</h6>
<blockquote>
希爾排序：希爾排序?yàn)榱思涌焖俣群唵蔚母倪M(jìn)了插入排序，交換不相鄰的元素對數(shù)組的局部進(jìn)行排序，并最終用插入排序?qū)τ诰植坑行驍?shù)組進(jìn)行排序。
<strong>希爾排序的思想是使數(shù)組中任意間隔為H的數(shù)組有序。換句話說，一個(gè)有序數(shù)組，是由h個(gè)互相獨(dú)立的有序數(shù)組組成，在進(jìn)行排序時(shí)，如果h很大，我們就能將元素移動(dòng)到很遠(yuǎn)的地方，為實(shí)現(xiàn)更小的h有序創(chuàng)造方便。用這種方式，對于任意以1結(jié)尾的序列，我們都能夠?qū)?shù)組排序。這就是希爾排序。
為方便理解，我自制了一張排序軌跡圖。</strong>
</blockquote>
<pre>
package com.example.sort;
/**
* 希爾排序
* */
public class ShellSort extends SortTamplate{
public void sort(Comparable a[]){
long begin = System.currentTimeMillis();
int N = a.length;
int h = 1;
while(h<N/3){
h = h*3 + 1;
}
while(h >= 1){
for(int i = h;i<N ;i++){
for(int j=i;j>=h && less(a[j],a[j-h]);j=j-h){
exchange(a,j,j-h);
}
}
h = h/3;
}
long end = System.currentTimeMillis();
System.out.println("算法用時(shí)："+(end-begin));
}
}
</pre>
<h6>對于h間隔步長的選擇建議使用序列1，4，13，40，121···有排序軌跡圖可知，希爾排序比插入排序時(shí)間復(fù)雜度有低很多，且數(shù)組規(guī)模越大，效率越明顯。在排序(下)中，我將介紹更加高效的算法。</h6>
