前言：
排序演算法是我們編程中遇到的最多的演算法，目前主流的演算法有8種，
平均時間復雜度從高到低依次是：
冒泡排序（o(n2)），選擇排序（o(n2)），插入排序（o(n2)），堆排序（o(nlogn)），
歸并排序（o(nlogn)），快速排序（o(nlogn)）， 希爾排序（o(n1.25)），基數排序（o(n)）
申明：以下排序全部針對陣列{ 25, 1, 5, 2, 9, 11, 2, 4 }; 所有測驗使用備注，只是為了讓用戶根據結果看得更加明白，理解之后可洗掉，
一、冒泡排序：
思想：從陣列第一位開始，每個元素和它下一位比較，將大的換到后面，即每一輪回圈之后可以確定一個位置，提高效率（可定義一個標記，如果一輪回圈之后沒有發生交換直接結束）
代碼：
static void maopao() { int[] a = new int[] { 25, 1, 5, 2, 9, 11, 2, 4 }; bool sign = false; for (int i = 0; i < a.Length - 1; i++) { for (int j = 0; j < a.Length - i - 1; j++) { if (a[j] > a[j+1]) { outPuts(a, "交換之前");//測驗使用 Console.Write(String.Format(" {0:D2}<-交換->{1:D2} ", a[j], a[j + 1]));//測驗使用 int b = a[j]; a[j] = a[j + 1]; a[j + 1] = b; sign = true; outPuts(a, "交換之后");//測驗使用 Console.WriteLine();//測驗使用 } } if (!sign) break; } Console.WriteLine();//測驗使用 outPuts(a, "最后資料"); Console.ReadKey(); } private static void outPuts(int[] a, string str) { Console.Write(str + ":"); foreach (var item in a) { Console.Write(item + " "); } }
結果：
二、選擇排序：
對冒泡排序進行優化，由上結果可以看到25連續交換多次，那么如何實作一次回圈只交換一次就可以確定一個位置呢？
思想：對于第一趟，搜索整個陣列，尋找出最小（或最大此處以最小為例即從小到大排序）的，然后放置在陣列的0號位置；對于第二趟，搜索陣列的n-1個記錄，尋找出最小的（對于整個陣列來說則是次小的），然后放置到陣列的第1號位置，在第i趟時，搜索陣列的n-i+1個記錄，尋找最小的記錄（對于整個陣列來說則是第i小的），然后放在陣列i-1的位置（注意陣列以0起始），
代碼：
private static void xuanze() { int[] a = new int[] { 25, 1, 5, 2, 9, 11, 2, 4 }; for (int i = 0; i < a.Length - 1; i++) { int sign = i; for (int j = i + 1; j < a.Length; j++) { if (a[sign] > a[j]) { sign = j; } } if (sign != i) { outPuts(a, "交換之前");//測驗使用 Console.Write(String.Format(" {0:D2}<-交換->{1:D2} ", a[i], a[sign]));//測驗使用 int b = a[i]; a[i] = a[sign]; a[sign] = b; outPuts(a, "交換之后");//測驗使用 Console.WriteLine();//測驗使用 } } Console.WriteLine();//測驗使用 outPuts(a, "最后資料"); Console.ReadKey(); } private static void outPuts(int[] a, string str) { Console.Write(str + ":"); foreach (var item in a) { Console.Write(item + " "); } }
結果：
三、插入排序：
插入排序是一種對于有序數列高效的排序，非常聰明的排序，只是對于亂數列，效率一般，交換的頻率高，
思想：陣列下標1開始，和前面下標為0的資料作比較，如果下標0的資料大于（或小于即從大到小排序）下標1的資料則后移，下標1的資料插入到0的位置，否則插入當前位置，陣列下標m開始，和所以前面資料作比較，即下標為n(m-1>=n>=0)的資料作比較，如果下標n的資料大于（或小于即從大到小排序）下標m的資料則后移,直到n=-1,將下標為m得到資料插入到下標為0的位置，否則插入當前位置，
代碼：
private static void charu() { int[] data = https://www.cnblogs.com/unknown6248/p/new int[] { 25, 1, 5, 2, 9, 11, 2, 4 }; for (int i = 1; i < data.Length; i++) { int d = data[i]; bool result = true;//標記，表示已經比較到第一個位置 for (int j = i - 1; j >= 0; j--) { if (data[j] > d) { outPuts(data, "移動之前");//測驗使用 Console.Write(String.Format(" 從下標{0}開始 {1}<-移動->{2} ",i, j, j+1));//測驗使用 data[j + 1] = data[j]; outPuts(data, "移動之后");//測驗使用 Console.WriteLine();//測驗使用 } else { outPuts(data, "插入之前");//測驗使用 Console.Write(String.Format(" 從下標{0}開始 資料{1}<-插入到->{2} ", i, d, j + 1));//測驗使用 data[j + 1] = d; result = false; outPuts(data, "插入之后");//測驗使用 Console.WriteLine();//測驗使用 break; } } if (result) { outPuts(data, "插入之前");//測驗使用 Console.Write(String.Format(" 資料{0}<-插入到->{1} ", d, 0));//測驗使用 data[0] = d; outPuts(data, "插入之后");//測驗使用 Console.WriteLine();//測驗使用 } } Console.WriteLine();//測驗使用 outPuts(data, "最后資料"); Console.ReadKey(); } private static void outPuts(int[] a, string str) { Console.Write(str + ":"); foreach (var item in a) { Console.Write(item + " "); } }
//方法二 private static void charu2(int[] data) { int j; for (int i = 1; i < data.Length; i++) { int d = data[i]; for (j = i - 1; j >= 0 && data[j] > d; j--) { data[j + 1] = data[j]; } data[j + 1] = d; } }
結果：
四、快速排序：
快速排序是一種高效排序，它包含了“分而治之”以及“哨兵”的思想，
思想：從陣列中挑選一個數（一般為第一個資料）作為“哨兵”，使比它小的放在它的左側，比它大的放在它的右側，
說明：25為哨兵，定義變數保存，0位置為待處理位置，從right向前找直到找到比哨兵小的，將其放入到待處理位置，left++，并設定當前為待處理位置，從left開始向后找比哨兵大的放入待處理位置，right--，并設定當前為待處理位置，直到left>right結束，此時第一個哨兵位置確定，并以哨兵為點，將陣列分為兩段分別繼續遞回實作該方法，
代碼：
private static void kuaisu(int[] data, int left, int right) { if (left >= right) return; int x = data[left]; int i = left; int j = right; try { while (i < j) { while (i < j && data[j] >= x) { j--; } if (i == j) break; outPuts(data, "移動之前");//測驗使用 Console.Write(String.Format(" {0}<-移動到->{1} ", j, i));//測驗使用 data[i++] = data[j]; outPuts(data, "移動之后");//測驗使用 Console.WriteLine();//測驗使用 while (i < j && data[i] <= x) { i++; } if (i == j) break; outPuts(data, "移動之前");//測驗使用 Console.Write(String.Format(" {0}<-移動到->{1} ", i, j));//測驗使用 data[j--] = data[i]; outPuts(data, "移動之后");//測驗使用 Console.WriteLine();//測驗使用 } outPuts(data, "移動之前");//測驗使用 Console.Write(String.Format(" 資料{0}<-移動到->{1} 資料區間{2}--{3} ", x, i,left,right));//測驗使用 data[i] = x; outPuts(data, "移動之后");//測驗使用 Console.WriteLine();//測驗使用 kuaisu(data, left, i - 1); kuaisu(data, i + 1, right); } catch (Exception e) { Console.WriteLine(e); } } private static void outPuts(int[] a, string str) { Console.Write(str + ":"); foreach (var item in a) { Console.Write(item + " "); } }
結果：
五、歸并排序：
使用遞回方法，
思想：將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序，
那么如何確定一個子序列有序呢？當然子序列個數為1時自然有序，所以將陣列分為兩段，一直分段遞回下去，直到陣列長度為1回傳，此時將其歸并直到結束，
歸并操作的作業原理如下：
第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
第二步：設定兩個指標，最初位置分別為兩個已經排序序列的起始位置
第三步：比較兩個指標所指向的元素，選擇相對小的元素放入到合并空間，并移動指標到下一位置
重復步驟3直到某一指標超出序列尾
將另一序列剩下的所有元素直接復制到合并序列尾
代碼：
int[] data = https://www.cnblogs.com/unknown6248/p/new int[] { 25, 1, 5, 2, 9, 11, 2, 4 }; guibing(data, 0, data.Length - 1); outPuts(data, "最后資料"); Console.ReadKey();
private static void guibing(int[] data, int left, int right) { if (left < right) { int mid = (left + right) / 2; guibing(data, left, mid); guibing(data, mid + 1, right); arrayAdd(data, left, mid, right); } } private static void arrayAdd(int[] data, int left, int mid, int right) { int[] d = new int[right - left + 1]; int i = left; int j = mid + 1; int k = 0; while (i <= mid && j <= right) { if (data[j] < data[i]) d[k++] = data[j++]; else d[k++] = data[i++]; } while (i <= mid) { d[k++] = data[i++]; } while (j <= right) { d[k++] = data[j++]; } i = left; for (k = 0; k < d.Length; k++) { outPuts(data, "賦值之前");//測驗使用 Console.Write(" ");//測驗使用 data[i++] = d[k]; outPuts(data, "賦值之后");//測驗使用 Console.Write(String.Format(" 賦值下標位置范圍{0}--{1} 臨時陣列：",left,right));//測驗使用 foreach (int f in d) //測驗使用 { Console.Write(f + " "); } Console.WriteLine();//測驗使用 } } private static void outPuts(int[] a, string str) { Console.Write(str + ":"); foreach (var item in a) { Console.Write(item + " "); } }
結果：
六、希爾排序：
希爾排序是插入排序的一種更高效的改進版本，
思想：希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演算法排序，隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個數列恰被分成一組，演算法便終止，
增量演算法有：https://blog.csdn.net/foliciatarier/article/details/53891144
本文以：Hibbard 增量序列為例
代碼：
int[] data = https://www.cnblogs.com/unknown6248/p/new int[] { 25, 1, 5, 2, 9, 11, 2, 4 }; xier(data);
private static void xier(int[] data) { List<int> garArry = new List<int>(); int m = 0; while (Math.Pow(2,m) - 1 <= data.Length / 2) { m++; garArry.Add((int)Math.Pow(2, m) - 1); } for (int y = garArry.Count - 1; y >= 0; y--) { int gap = garArry[y]; int j; //比較次數 for (int i = gap; i < data.Length; i++) { int d = data[i]; for (j = i - gap; j >= 0 && data[j] > d; j -= gap) { outPuts(data, "移動之前");//測驗使用 Console.Write(String.Format(" {0}<-移動到->{1} 步長{2} ", j, j + gap, gap));//測驗使用 data[j + gap] = data[j]; outPuts(data, "移動之后");//測驗使用 Console.WriteLine();//測驗使用 } outPuts(data, "移動之前");//測驗使用 Console.Write(String.Format(" 資料{0}<-移動到->{1} 步長{2} ", d, j + gap, gap));//測驗使用 data[j + gap] = d; outPuts(data, "移動之后");//測驗使用 Console.WriteLine();//測驗使用 } } outPuts(data, "最后資料"); } private static void outPuts(int[] a, string str) { Console.Write(str + ":"); foreach (var item in a) { Console.Write(item + " "); } }
結果：
后續添加更多排序方法
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/112981.html
標籤：其他
上一篇：大資料時代的機遇和挑戰？
下一篇：學云計算專業怎么樣