演算法基礎_排序演算法

演算法基礎_排序演算法

一.冒泡排序

冒泡排序的原理非常簡單，它重複地走訪過要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。

步驟：

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。

2. 對第0個到第n-1個數據做同樣的工作。這時，最大的數就「浮」到了數組最後的位置上。

3. 針對所有的元素重複以上的步驟，除了最後一個。

4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

public static void BubbleSortsort(Comparable[] a){ int N= a.length; for(int i=0;i<N;i++) { for(int j= 1;j<n-i;j++) if(a[j-1]>a[j]) exch(a,j-1,j); }}

二.選擇排序 SelectionSort

選擇排序無疑是最簡單直觀的排序。選擇剩餘元素的最小值，從第一個位置開始交換 。

步驟：

1.在未排序序列找到最小元素，存放到排序序列的起始位置。

2.從剩餘未排序序列繼續尋找最小元素，然後放到已排序序列的末尾。

3.以此類推，直到所有元素均排序完畢。

//選擇排序實現public class Selection{ public static void sort(Comparable[] a) { int N = a.length; //數組長度 for(int i=0;i<N;i++) { int min =i; //先假設第一個為最小 for(int j=i+1;j< N;j++) if(less(a[j],a[min])) min=j; //找出後面誰比它的坐標 exchange(a,i,min); //交換兩項 } }}

三.插入排序 InsertionSort

將一個無序的元素插入到其他有序的數組元素中。類似打撲克牌，拿到一張新的牌，在已排序的序列中找到它的位置並插入其中

步驟：

1. 從第一個元素開始，該元素可以認為已經被排序

2. 取出下一個元素，在已經排序的元素序列中從後向前掃描

3. 如果被掃描的元素（已排序）大於新元素，將該元素後移一位

4. 重複步驟3，直到找到已排序的元素小於或者等於新元素的位置

5. 將新元素插入到該位置後

6. 重複步驟2~5

//插入排序實現public class Insertion{ public static void sort(Comparable[] a) { int N = a.length; //數組長度 for(int i=0;i<N;i++) { for(int j=i;j>0&&less(a[j],a[j-1]);j--)//找到它的位置 exchange(a,j,j-1); }0. }}

四.希爾排序 ShellSort

希爾排序是一種基於插入排序的快速的排序演算法。對於大規模亂序舒徐插入排序很慢，而希爾排序為了加快速度簡單改進了插入排序，交換彼此不相鄰的元素以對數組的局部進行排序，並最終用插入排序將局部有序的數組排序。

步驟

1.以步長為h進行插入排序。

2.縮短h，重複步驟1，直到h等於1。

3.以步長為1進行最後一次插入排序。

public class Shell //希爾排序的實現{ public static void sort(Comparable[] a) { int N = a.length; int h=1; while(h<N/3) h = 3*h+1; //找到合適的步長 while(h>=1) { for(int i=h;i<N;i++)//以步長為h進行插入排序 { for(int j =i;j>=h&&less(a[j],a[j-h];j-=h) exch(a,j,j-h); } h=h/3; } }}

五.歸併排序 MergeSort

歸併，即兩個有序的數組歸併成一個更大的有序數組。 歸併排序使用了遞歸分治的思想，所以理解起來比較容易。其基本思想是，先遞歸劃分子問題，然後合併結果。把待排序列看成由兩個有序的子序列，然後合併兩個子序列，然後把子序列看成由兩個有序序列。倒著來看，其實就是先兩兩合併，然後四四合併。最終形成有序序列。

步驟

1.將數組不斷地遞歸分解數組，直到分解出的小組只含有一個元素。

2.兩兩歸併數組。比較兩個數組的最前面的數，誰小就先取誰，取了後相應的指針就往後移一位。然後再比較，直至一個數組為空，最後把另一個數組的剩餘部分複製過來。

public static void merge(Comparable [],int lo,int mid,int hi) //歸併的具體實現{ int i=lo,j=mid+1; for(int k =lo;k<=hi;k++) aux[k]=a[k]; for(int k=lo;k<=hi;k++) if(i>mid) a[k]=aux[j++]; else if(j>hi)a[k]=aux[i++]; else if(less(aux[j],aux[i]))a[k]=aux[j++]; else a[k]=aux[i++];}public class Merge{ private static Comparable[] aux; public static void sort(Comparable[] a) { aux = new Comparable[a.length]; sort(a,0,a.length-1) }private static void sort(Comparable[] a,int lo ,int hi) { if(hi<=lo) //遞歸結束的條件 return; int mid = lo+(hi-lo)/2; //先分解數組 sort(a,lo,mid); sort(a,mid+1,hi)； merge(a,lo,mid,hi); //合併數組 }}

六.快速排序 QuickSort

快速排序是一種分治的排序演算法。它將一個數組分為兩個子數組，將兩部分獨立的排序。快速排序將數組排序的方式是當兩個子數組都有序時整個數組也就自然有序了。

步驟：

1. 從數列中挑出一個元素作為基準數。

1. 分區過程，將比基準數大的放到右邊，小於或等於它的數都放到左邊。

1. 再對左右區間遞歸執行第二步，直至各區間只有一個數

private static int partition(Comparable[] a,int lo,int hi){ int i=lo,j=hi+1; Comparable v =a[lo]; //以第一個元素為切分點 while(true) //從左右兩邊各找到不符合排序的元素，交換 { while(less(a[i++],v))if(i==hi)break; while(less(v,a[--j]))if(j==lo)break; if(i>=j)break; exch(a,i,j); } exch(a,lo,j); return j;}public class Quick{ public static void sort(Comparable[] a) { stdRandom.shuffle(a); sort(a,0,a.length-1); } private static void sort(Comparable[] a,int lo,int hi) { if(hi<=lo) return; //遞歸結束的條件 int j = partition(a,lo,hi); //選擇切分點 sort(a,lo,j-1); sort(a,j-1,hi); }}

各個演算法複雜度比較

推薦閱讀：