今天這篇文章簡單介紹下最最最基礎(chǔ)的排序
我們數(shù)據(jù)的存儲方式默認(rèn)為數(shù)組，長度為N個元素
選擇排序：
算法描述：就是在數(shù)組中找到最小的元素恼五，和第一位元素互換內(nèi)容昌罩，倘若第一位的元素最小，則自己和自己互換灾馒。然后從第二位開始（因為第一位已經(jīng)排好序了）遍歷數(shù)組找到現(xiàn)存最小的元素茎用，讓他和第二互換位置。然后從第三位開始重復(fù)睬罗。轨功。。容达。古涧。
影響排序的時間的因素有兩點(diǎn)，一個是數(shù)據(jù)移動董饰，為N次蒿褂。一個是數(shù)組比較（其實(shí)就是數(shù)組遍歷的過程）為N-1+N-2+····+2+1=N（N-1）/2約為N^2的量級
根據(jù)上面分析可以看出選擇排序的時間和輸入無關(guān)圆米，無論是隨機(jī)打亂的數(shù)組還是已經(jīng)排好序的數(shù)組卒暂，進(jìn)行排序所用的時間都一樣。
選擇排序的代碼實(shí)現(xiàn)
public class Selection {
public static void sort(int [] a) {
int n=a.length;
int min;
for(int i=0;i<n;i++) { //i代表正在排序的位置
min=i;
for(int j=i+1;j<n;j++) { //遍歷數(shù)組只需要從i后面的數(shù)組就行娄帖，前面已經(jīng)排好序了
if(a[j]<a[min]) min=j; //找到最小的元素也祠，然后記錄它的序號
}
exchange(a, i, min);
}
}
//交換數(shù)組元素的次序
public void exchange(int []a,int b,int min) {
int temp=a[b];
a[b]=a[min];
a[min]=temp;
}
}
插入排序：
算法描述：是自己從大到小的序號開始遍歷數(shù)組元素，比如剛好遍歷到i序號近速，則序號0-(i-1)都是維護(hù)大小順序诈嘿，現(xiàn)在就是要將原來序號為i的的元素插入到已經(jīng)維護(hù)好的數(shù)組堪旧，形成排序好的i+1數(shù)組，不斷增加排序好的數(shù)組的元素數(shù)目奖亚。最后形成數(shù)量為n的排序后的數(shù)組淳梦。
這個算法的時間是和輸入有關(guān)的最壞情況要分別有~n^/2 比較和交換。最好的情況為n-1次比較0次交換昔字，平均下來是n^2/4的比較和交換爆袍，看起來如果n比較大的話好像插入比選擇排序更快
public class Insertionsort {
public static void sort(int []a) {
int n=a.length;
for(int i=1;i<n;i++) {
for(int j=i;j>0&&(a[j]<a[j-1]);j--) {
exchange(a,j,j-1);
}
}
}
public static void exchange(int []a,int b,int min) {
int temp=a[b];
a[b]=a[min];
a[min]=temp;
}
}
希爾排序
這個有一點(diǎn)點(diǎn)難懂，它其實(shí)是上面插入排序的升級版作郭。不過它維護(hù)數(shù)組不是從左到右長度逐漸變大（傳統(tǒng)插入排序的方式）陨囊。它是將數(shù)組分成gap組，每組數(shù)組的元素為間隔為gap的元素夹攒，每一組的元素數(shù)可能為n/gap（如果gap不是n的因數(shù)的話部分?jǐn)?shù)組的元素數(shù)為n/gap+1）然后分別維護(hù)他們的順序蜘醋。然后再將gap的值按一定規(guī)則變小，重新切割數(shù)組再維護(hù)數(shù)組順序咏尝。gap變得越來越小压语，最后變成1。這時候就維護(hù)長度為n的序列编检，就是完整的遍歷冒泡排序无蜂，（冒泡和插入，區(qū)別不大蒙谓，但是有區(qū)別的斥季，具體查查冒泡排序）這里說冒泡是強(qiáng)調(diào)最后一次數(shù)組遍歷保證排序的正確性，前面的工作只是為了減少這一步的比較和交換次序的操作累驮。
希爾排序的核心思想維護(hù)部分部分有序最終利于維護(hù)整體有序酣倾。
public class Shellsort {
public static void sort(int [] a) {
int n=a.length;
int gap=n/2;
while(gap>=1) {
for(int i=gap;i<n;i++) {
for(int j=i;j>=0&&a[j]<a[j-gap];j-=gap) {
exchange(a,j,j-gap);
}
}
gap/=2;
}
}
public static void exchange(int []a,int b,int c) {
int temp=a[b];
a[b]=a[c];
a[c]=temp;
}
}
注意gap的取值和縮小規(guī)律是如何其實(shí)都是沒關(guān)系的，不會影響算法的正確性谤专。但是gap一定要最后是為1Ｔ晡！置侍！
希爾排序?qū)χ械却笮〉臄?shù)組的運(yùn)行時間還是可以接受的映之，但它還只是一種基礎(chǔ)的算法，對于大型的數(shù)組排序還是需要更高效的算法蜡坊，這就需要我們繼續(xù)的學(xué)習(xí)了杠输。:）
