Java數據結構與演算法–簡單排序
- 2019 年 11 月 21 日
- 筆記
版權聲明：本文為部落客原創文章，遵循 CC 4.0 BY-SA 版權協議，轉載請附上原文出處鏈接和本聲明。
本文鏈接：https://blog.csdn.net/wangtongxue123456/article/details/72638485
簡單排序
本文討論比較簡單的排序演算法：冒泡排序、選擇排序、插入排序
三個演算法都包括如下兩個步驟。
- 比較兩個數據項
- 交換兩個數據項、或複製其中一項。
冒泡排序
冒泡排序演算法運行起來非常慢，但是在概念上他是排序演算法中最簡單的。
冒泡排序遵循的規則： 1. 比較兩個數據 2. 如果左邊的數據大，則兩個數據交互位置。 3. 向右移動一個位置，比較下面兩個數據。（沿著這個隊列一直比較下去，一直比較到隊列的最右端），這時最右端的數據應該會是最大的數。 4. 當碰到第一個排定的數據後，就返回隊列的左端重新開始下一趟排序。 程式碼實現
/** * 冒泡排序 */ public class BubbleSort { //初始化數組 private static long a[]=new long[]{11,4,7,9,2,10,23,8,34,29}; //數組長度 private static int nElems=a.length; public static void main(String[] args) { int in,out; for (out=nElems-1;out>1;out--){ // for (in=0;in<out;in++){ //比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。 if (a[in]>a[in+1]){ swap(in,in+1); } } } //輸出排序 for (long l:a){ System.out.print(l+" "); } } //交換數據 private static void swap(int in, int i) { long temp=a[in]; a[in]=a[in+1]; a[in+1]=temp; }
演算法思路 １.將最小的數據項放在數組的最開始，並將最大的數據項放在數組的最後。 ２.外層for 循環的計數器out從數組的最後開始，沒經過一次循環ｏｕｔ減一。下標大於ｏｕｔ的數據項都是已經排好序的，變數ｏｕｔ每完成一次內部循環（計數器為ｉｎ）後就左移一位。 ３.內層ｆｏｒ循環計數器ｉｎ從數組的最開始算起（ｉｎ＝０），沒完成一次內部循環體加一，當它等於ｏｕｔ時結束一次循環，在內層ｆｏｒ循環體重，數組下標ｉｎ和ｉｎ＋１的兩個數據項進行比較，如果ｉｎ數據大於ｉｎ＋１數據項，則交換數據。 ４.為了清晰增加獨立的ｓｗａｐ（）方法執行交換，但是它會增加一些額外的消耗，如果自己使用排序程式，最好將交換操作這段程式碼直接放到程式中。這樣可以提高一些速度。
選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序演算法。它的工作原理是每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完。 選擇排序是不穩定的排序方法
程式碼實現
/** * Created by YcDr on 2017/5/24. * 選擇排序 */ public class SelectSort { //初始化數組 private static long a[]={12,34,19,2,54,13,11,33,18,9}; //數組長度 private static int nElems=a.length; public static void main(String[] args) { int in,out,temp; for (out=0;out<nElems;out++){ temp=out;//temp臨時變數，用於存取最小值下標 for (in=out+1;in<nElems;in++){ if (a[temp]>a[in]){ temp=in; } } //每次循環找出最小值下標後，在進行數據交換 swap(out,temp); } for (long l:a) System.out.print(l+" "); } //交換數據 private static void swap(int i,int t) { long temp=a[t]; a[t]=a[i]; a[i]=temp; } }
與冒泡排序比較
選擇排序與冒泡排序相比，都執行了相同的比較次數N*(N-1)/2,但是相比冒泡排序，選擇排序降低了交換數據的次數。 選擇排序和冒泡排序一樣運行了O（N^2）時間，但是顯然選擇排序要比冒泡排序更快一些，因為選擇排序交換次數很少，如果交換時間及比比較時間及要大的多時，選擇排序實際要快的多。
插入排序
在大多數情況下，插入演算法是本章描述的基本排序演算法中最後的一種，雖然插入排序演算法任然需O(N^2) 的時間，但是在一般情況下他要比冒泡排序快一倍，比選擇排序還要快一點。
演算法思路 1. 默認序列中的第0個元素是有序的； 2. 從下標為1（下標從0開始）的元素開始，取當前下標i位置處的元素a[i]保存到一個臨時變數里； 3. 對前半部分有序序列的循環遍歷，並與臨時變數比較，直到遇到一個比臨時變數小的元素（這裡默認是從小到大排序），交換數據 4. 將待插入元素的下標 i 向後推移一個位置； 5. 重複進行第2步到第4步，直到亂序序列中的元素被全部插入到有序序列中；
程式碼實現
/** * Created by YcDr on 2017/5/25. * 插入排序 */ public class InsertSort { //初始化數組 private static long a[]={12,19,34,2,54,13,11,33,18,9}; //數組長度 private static int nElems=a.length; public static void main(String[] args) { int in,out; for (out=1;out<nElems;out++){ long temp=a[out]; in=out; while (in>0&&a[in-1]>=temp){ a[in]=a[in-1]; in--; } a[in]=temp; } for (long l:a){ System.out.print(l+" "); } } }
穩定性
有些時候，排序要考慮數據項擁有相同關鍵字的情況，例如，僱員姓名按字典進行排序，現在又想按郵政編碼排序，並希望，讓不需要排序的數據保持原來的排序。這種情況下，則只需要演算法對需要排序的數據進行排序，讓不需要的數據保持原來的順序，某些演算法滿足這樣的要求，他們就可以稱為穩定的演算法。
