C#實(shí)現(xiàn)(遞歸和非遞歸)快速排序和簡單排序

???? 本人因為最近工作用到了一些排序算法，就把幾個簡單的排序算法，想冒泡排序，選擇排序，插入排序，奇偶排序和快速排序等整理了出來，代碼用C#代碼實(shí)現(xiàn)，并且通過了測試。希望能給大家提供參考。

??? 1.冒泡排序

?????? 冒泡排序，是指計算機(jī)的一種排序算法，它的時間復(fù)雜度是O（n^2），雖然不及堆排序和快速排序時間復(fù)雜度為O（nlogn，底數(shù)為2），但是有兩個優(yōu)點(diǎn)：1：編程復(fù)雜度低，很容易實(shí)現(xiàn)；2 是具有穩(wěn)定性，這里的穩(wěn)定性是指源序列中相同元素的相對順序仍然保持到排序后的順序，而堆排序和快速排序都不具有穩(wěn)定性。

???? 基本概念

???????? 冒泡排序（BubbleSort)的基本概念：依次比較相鄰兩個數(shù)，小的在前，大的在后。在第一趟，首先比較第1個數(shù)和第2個數(shù)，小的放在前面，大的放在后面，然后比較第2個數(shù)和第3個數(shù)，小的在前，大的在后，如此繼續(xù)，直到比較最后兩個數(shù)，小的在前，大的在后，第一趟結(jié)束時，就把最大的數(shù)放在了最后。在第二趟，仍從第一對數(shù)開始比較（因為由于第2個數(shù)和第3個數(shù)的交換，使第1個數(shù)不再小于第2個數(shù)），將小數(shù)放前，大數(shù)放后，一直比較到倒數(shù)第二個數(shù)（倒數(shù)第一個數(shù)已經(jīng)是最大的），第二趟結(jié)束，這樣在倒數(shù)第二個位置得到一個新的最大數(shù)，如此循環(huán)下去，重復(fù)以上過程，直至最終完成排序。

比如有一個數(shù)列10, 33, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 1, 345, 61, 76, 31, 43, 76

第一次排序后：10,2,4,33,6,12,34,55,66,43,23,65,1,345,61,76,31,43,76,456

第二次排序后：2,4,10,6,12,33,34,55,43,23,65,1,66,61,76,31,43,76,345,456

第三次排序后：2,4,6,10,12,33,34,43,23,55,1,65,61,66,31,43,76,76,345,456

第四次排序后：2,4,6,10,12,33,34,23,43,1,55,61,65,31,43,66,76,76,345,456

第五次排序后: 2,4,6,10,12,33,23,34,1,43,55,61,31,43,65,66,76,76,345,456

第六次排序后: 2,4,6,10,12,23,33,1,34,43,55,31,43,61,65,66,76,76,345,456

第七次排序后: 2,4,6,10,12,23,1,33,34,43,31,43,55,61,65,66,76,76,345,456

第八次排序后: 2,4,6,10,12,1,23,33,34,31,43,43,55,61,65,66,76,76,345,456

第九次排序后: 2,4,6,10,1,12,23,33,31,34,43,43,55,61,65,66,76,76,345,456

第十次排序后: 2,4,6,1,10,12,23,31,33,34,43,43,55,61,65,66,76,76,345,456

第十一次排序后：2,4,1,6,10,12,23,31,33,34,43,43,55,61,65,66,76,76,345,456

第十二次排序后：2,1,4,6,10,12,23,31,33,34,43,43,55,61,65,66,76,76,345,456

第十三次排序后: 1,2,4,6,10,12,23,31,33,34,43,43,55,61,65,66,76,76,345,456

這樣經(jīng)過13趟排序后這個序列就成為一個有序的數(shù)列。

具體實(shí)現(xiàn)代碼為：

?????? private static void BubbleSort(int[] R) ??????? { ??????????? int len = R.Length; ??????????? bool flag = false; ??????????? for (int i = 0; i < len-1; i++) ??????????? { ??????????????? flag = false; ??????????????? for (int j = 0; j < len - i-1; j++) ??????????????? { ??????????????????? if (R[j] > R[j + 1]) ??????????????????? { ??????????????????????? Swap(ref R[j], ref R[j + 1]); ??????????????????????? flag = true; ??????????????????? } ??????????????? } ??????????????? if (!flag) ??????????????? { ??????????????????? break; ??????????????? } ??????????? } ??????? }

?????? private static void Swap(ref int left, ref int right) ??????? { ??????????? int temp = left; ??????????? left = right; ??????????? right = temp; ??????? }

?

2. 選擇排序

????? 每一趟從待排序的元素中選擇最小的（最大的）一個元素，順序放在已排好序的數(shù)列的最后，直到待排序的元素派完，選擇排序是不穩(wěn)定的排序。

??? 基本概念

????????? 具有n元素的數(shù)列可以進(jìn)行n-1趟直接選擇排序得到有序結(jié)果，初始狀態(tài)有序區(qū)為空，無序區(qū)為R[1...n]

????????? 第1趟排序在無序區(qū)R[1...n]選擇關(guān)鍵字最小的元素R[k],將它與無序區(qū)的R[1] 進(jìn)行交換，使R[1...1]和R[2...n]變?yōu)閭€增加為1新有序區(qū)，和無序區(qū)的元素個數(shù)減去1的新無序區(qū)。

???????? 第i趟排序開始時，當(dāng)前有序區(qū)和無序區(qū)分別為R[1..i-1]和R(1≤i≤n-1)。該趟排序從當(dāng)前無序區(qū)中選出關(guān)鍵字最小的記錄 R[k]，將它與無序區(qū)的第1個記錄R交換，

???????? 使R[1..i]和R分別變? 為記錄個數(shù)增加1個的新有序區(qū)和記錄個數(shù)減少1個的新無序區(qū)。 這樣，n個記錄的文件的直接選擇排序可經(jīng)過n-1趟直接選擇排序得到有序結(jié)果 .

???????? 對于數(shù)列??? 10,33,2,4,55,6,12,34,456,66,43,23,65,1,345, 61,76,31,43,76????

???????? 第一次排序后：1,33,2,4,55,6,12,34,456,66,43,23,65,10,345,61,76,31,43,76

???????? 第二次排序后:? 1,2,33,4,55,6,12,34,456,66,43,23,65,10,345,61,76,31,43,76

???????? 第三次排序后：1,2,4,33,55,6,12,34,456,66,43,23,65,10,345,61,76,31,43,76

???????? 第四次排序后：1,2,4,6,55,33,12,34,456,66,43,23,65,10,345,61,76,31,43,76

???????? 第五次排序后：1,2,4,6,10,33,12,34,456,66,43,23,65,55,345,61,76,31,43,76

???????? 第六次排序后:? 1,2,4,6,10,12,33,34,456,66,43,23,65,55,345,61,76,31,43,76

???????? 第七次排序后:? 1,2,4,6,10,12,23,34,456,66,43,33,65,55,345,61,76,31,43,76

???????? 第八次排序后:? 1,2,4,6,10,12,23,31,456,66,43,33,65,55,345,71,76,34,43,76

???????? 第九次排序后:? 1,2,4,6,10,12,23,31,33,66,43,456,65,55,345,71,76,34,43,76

???????? 第十次排序后:? 1,2,4,6,10,12,23,31,33,34,43,456,65,55,345,71,76,66,43,76

???????? 第十一次排序后: 1,2,4,6,10,12,23,31,33,34,43,43,65,55,345,71,76,66,456,76

???????? 第十二次排序后:? 1,2,4,6,10,12,23,31,33,34,43,43,55,65,345,71,76,66,456,76

???????? 第十三次排序后:? 1,2,4,6,10,12,23,31,33,34,43,43,55,65,66,71,76,345,456,76

??????? 第十四次排序后:?? 1,2,4,6,10,12,23,31,33,34,43,43,55,65,66,71,76,76,456,345

??????? 第十五次排序后:?? 1,2,4,6,10,12,23,31,33,34,43,43,55,65,66,71,76,76,345,456

?????? 最終經(jīng)過15次排序后成為有序的數(shù)列。

?????? 具體實(shí)現(xiàn)代碼為：

??????? private static void SelectSort(int[] R) ??????? { ??????????? int len = R.Length; ??????????? int min = 0; ??????????? for (int i = 0; i < len - 1; i++) ??????????? { ??????????????? min = i; ??????????????? for (int j = i + 1; j < len - 1; j++) ??????????????? { ??????????????????? if (R[min] > R[j]) ??????????????????? { ??????????????????????? min = j; ??????????????????? } ??????????????? } ??????????????? Swap(ref R[i], ref R[min]); ??????????? } ??????? }

?

3. 插入排序

??????? 插入排序算法是一種穩(wěn)定的算法，時間復(fù)雜度是O(n^2)，適用于少量數(shù)據(jù)的排序。插入算法的基本操作就是將一個數(shù)據(jù)插入到已經(jīng)排好序的有序數(shù)據(jù)中，從而得到一個新的，個數(shù)加1的有序數(shù)據(jù)。插入算法把要排序的數(shù)組分為兩部分：第一部分包含了數(shù)組的所有元素，但將最后一個元素除外，而第二部分就只包含這一個元素，在第一部分排序后，再把最后這個元素插入到此刻已是有序的一部分中。

?? 基本思想

???????? 1：每次處理都是將無序序列的第一個元素和有序序列的元素從后面逐一比較，查到合適的插入位置，將該元素插入到有序序列的合適位置。

???????? 2：從有序R[1]和無序R[2...n]開始進(jìn)行排序。

???????? 3：處理第i個元素時(i=2,3,…,n) ,數(shù)列{R1,R2,...Ri-1}都是有序的，而數(shù)列{Ri,Ri+1,...Rn}都是無序的，用Ri 與{R1,R2,...Ri-1}逐個比較，找到合適位置，將Ri插入，

???????? 4：重復(fù)第三部，共進(jìn)行n-i次插入處理，數(shù)組全部有序

???????? 對于數(shù)列??? 10,33,2,4,55,6,12,34,456,66,43,23,65,1,345, 61,76,31,43,76????

??????? 第一次排序后：10,33,2,4,55,12,34,456,66,43,23,65,1,345,61,76,31,43,76

??????? 第二次排序后:? 2,10,33,4,55,12,34,456,66,43,23,65,1,345,61,76,31,43,76

??????? 第三次排序后:? 2,4,10,33,55,12,34,456,66,43,23,65,1,345,61,76,31,43,76

??????? 第四次排序后:? 2,4,10,33,55,12,34,456,66,43,23,65,1,345,61,76,31,43,76

??????? 第五次排序后:? 2,3,10,12,33,55,34,456,66,43,23,65,1,345,61,76,31,43,76

??????? 第六次排序后:? 2,3,10,12,33,34,55,456,66,43,23,65,1,345,61,76,31,43,76

??????? 第七次排序后:? 2,3,10,12,33,34,55,456,66,43,23,65,1,345,61,76,31,43,76

??????? 第八次排序后:? 2,3,10,12,33,34,55,66,456,43,23,65,1,345,61,76,31,43,76

??????? 第九次排序后:? 2,3,10,12,33,34,43,55,66,456,23,65,1,345,61,76,31,43,76

??????? 第十次排序后:? 2,3,10,12,23,33,34,43,55,66,456,65,1,345,61,76,31,43,76

??????? 第十一次排序后: 2,3,10,12,23,33,34,43,55,65,66,456,1,345,61,76,31,43,76

??????? 第十二次排序后: 1,2,3,10,12,23,33,34,43,55,65,66,456,345,61,76,31,43,76

??????? 第十三次排序后: 1,2,3,10,12,23,33,34,43,55,65,66,345,456,61,76,31,43,76

??????? 第十四次排序后: 1,2,3,10,12,23,33,34,43,55,61,65,66,345,456,76,31,43,76

??????? 第十五次排序后: 1,2,3,10,12,23,33,34,43,55,61,65,66,76,345,456,31,43,76

??????? 第十六次排序后: 1,2,3,10,12,23,31,33,34,43,55,61,65,66,76,345,456,43,76

??????? 第十七次排序后: 1,2,3,10,12,23,31,33,34,43,43,55,61,65,66,76,345,456,76

??????? 第十八次排序后: 1,2,3,10,12,23,31,33,34,43,43,55,61,65,66,76,76,345,456

?????? 共十八次排序后，數(shù)組才是全部有序的。

????? 實(shí)現(xiàn)代碼為:

???????? private static void InsertSort(int[] R) ??????? { ??????????? int len = R.Length; ??????????? int j = 0; ??????????? int temp = 0; ??????????? for (int i = 1; i < len; i++) ??????????? { ??????????????? temp=R[i]; ??????????????? j=i-1; ??????????????? while (j >= 0 && temp < R[j]) ??????????????? { ??????????????????? R[j + 1] = R[j]; ??????????????????? j--; ??????????????? } ??????????????? R[j + 1] = temp; ??????????? } ??????? }

?

4. 快速排序

?????????? 快速排序是對冒泡排序的一種改進(jìn)，它的基本思想是：通過一趟排序?qū)⒁判虻臄?shù)列分成獨(dú)立的兩個部分，其中一部分的所有數(shù)據(jù)都比后一部分的所有數(shù)據(jù)都要小，然后再按此方法對這兩個部分分別進(jìn)行快速排序，整個排序過程可以遞歸進(jìn)行，以次達(dá)到整個數(shù)列變?yōu)橛行颉？焖倥判虿皇欠€(wěn)定的排序。

? 算法過程

???????? 設(shè)要排序的數(shù)組為R[1...n],首先任意選取一個元素（通常選擇第一個元素）作為關(guān)鍵元素，然后把所有比它小的都放在前面，所有比它大的都放在后面，這個過程成為一趟快速排序。

???????? 1. 設(shè)置兩個變量 low ,high,排序開始的時候low=0,high=n-1;

???????? 2. 以第一個數(shù)組元素為關(guān)鍵數(shù)據(jù)key,即key = R[low];

???????? 3. 從high開始往前搜索，即由后開始向前搜索，high=high-1,找到第一個小于key的值R[high], 并與R[low] 交換,

???????? 4. 從low 開始向后搜索，即由前開始向后搜索，low=low+1,找到第一個大于key的值R[low],并于R[high]交換。

???????? 5. 重復(fù)3,4.直到low=high.

??????????? 對于數(shù)列??? 10,33,2,4,55,6,12,34,456,66,43,23,65,1,345, 61,76,31,43,76??

?????????? 初始關(guān)鍵數(shù)據(jù)key=10;

?????????? 第一次交換后：1, 33, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 1, 345, 61, 76, 31, 43, 76

?????????? 第二次交換后:? 1, 33, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 33, 345, 61, 76, 31, 43, 76

?????????? 第三次交換后:?? 1, 6, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 33, 345, 61, 76, 31, 43, 76

?????????? 第四次交換后:? 1, 6, 2, 4, 55, 55, 12, 34, 456, 66, 43, 23, 65, 33, 345, 61, 76, 31, 43, 76

????????? 這樣low=high=4

?????????? 再把R[low]=key

????????? 這樣第一次快速排序后數(shù)列就變?yōu)閧1,6,2,4}10{55,12,34,456,66,43,23,65,33,345,61,76,31,43,76}?

????????? 這樣再分別對{1,6,2,4}和{55,12,34,456,66,43,23,65,33,345,61,76,31,43,76}? 分別進(jìn)行快速排序,重復(fù)這個步驟，最終使整個數(shù)組都是有序的。

???????? 具體實(shí)現(xiàn)代碼為：

????????? private static void QuickSort(int[] R, int low, int high) ??????? { ??????????? int pivotLoc = 0;

??????????? if(low<high)

???????????? { ????????????????? pivotLoc = Partition(R, low, high); ????????????????? QuickSort(R, low, pivotLoc - 1); ????????????????? QuickSort(R, pivotLoc + 1, high);

????????????? } ??????? }

??????? private static int Partition(int[] R, int low, int high) ??????? { ??????????? int temp = R[low]; ??????????? while (low < high) ??????????? { ??????????????? while (low < high && temp <= R[high]) ??????????????? { ??????????????????? high--; ??????????????? } ??????????????? R[low] = R[high]; ??????????????? while (low < high && temp >= R[low]) ??????????????? { ??????????????????? low++; ??????????????? } ??????????????? R[high] = R[low]; ??????????? } ??????????? R[low] = temp; ??????????? return low; ??????? }

??? //快速非遞歸排序 ??????? public static void QuickSort(int[] R, int Low, int High, Stack<int> stack) ??????? { ??????????? int low = Low; ??????????? int high = High; ??????????? int temp = R[low]; ??????????? while (high > low) ??????????? { ??????????????? while (low < high && temp <= R[high]) ??????????????? { ??????????????????? high--; ??????????????? } ??????????????? if (high > low) ??????????????? { ??????????????????? R[low] = R[high]; ??????????????????? R[high] = temp; ??????????????? } ??????????????? while (low < high && temp >= R[low]) ??????????????? { ??????????????????? low++; ??????????????? } ??????????????? if (high > low) ??????????????? { ??????????????????? R[high] = R[low]; ??????????????????? R[low] = temp; ??????????????? } ??????????????? if (low == high) ??????????????? { ??????????????????? if (Low < low - 1) ??????????????????? { ??????????????????????? stack.Push(Low); ??????????????????????? stack.Push(low - 1); ??????????????????? } ??????????????????? if (High > low + 1) ??????????????????? { ??????????????????????? stack.Push(low + 1); ??????????????????????? stack.Push(High); ??????????????????? } ??????????????? } ??????????? } ??????? }

?????? 測試代碼：

static void Main(string[] args)

{

??????? int[] arry = new int[] { 10, 33, 2, 4, 55, 6, 12, 34, 456, 66, 43, 23, 65, 1, 345, 61, 76, 31, 43, 76 }; ??????????? Stack<int> s=new Stack<int>(); ??????????? s.Push(0); ??????????? s.Push(arryk.Length - 1); ??????????? while (s.Count > 0) ??????????? { ??????????????? int low = s.Pop(); ??????????????? int high = s.Pop(); ??????????????? if (low > high) ??????????????? { ??????????????????? temp = low; ??????????????????? low = high; ??????????????????? high = temp; ??????????????? } ??????????????? QuickSort(arryk, low, high, s);????????????? ??????????? }?????? ??????????? Console.ReadLine();

}

通過對10萬條隨機(jī)數(shù)據(jù)進(jìn)行遞歸和非遞歸排序后發(fā)現(xiàn)，非遞歸方法的速度是遞歸方法速度的40倍左右。

5 . 一個無序的數(shù)組，如何通過一個函數(shù)取出最大值和最小值，要求時間復(fù)雜度最低和空間最少

? 具體算法如下：

??????? private static int[] GetMaxMin(int[] R) ??????? {????????? ??????????? int len=R.Length; ??????????? int min = R[0]; ??????????? int max = R[0]; ??????????? for (int i = 1; i < len;i++ ) ??????????? { ??????????????? if (min > R[i]) ??????????????? { ??????????????????? min = R[i]; ??????????????? } ??????????????? if (max < R[i]) ??????????????? { ??????????????????? max = R[i]; ??????????????? } ??????????? } ??????????? int[] res = new int[2]; ??????????? res[0] = min; ??????????? res[1] = max; ??????????? return res;

??????? } 6? 對于已知數(shù)組，隨機(jī)存儲一百個數(shù)，把奇數(shù)放左邊，偶數(shù)放右邊，具體算法如下：

??????? private static void SortNumber(int[] R) ??????? { ??????????? int high = R.Length - 1; ??????????? int low = 0; ??????????? int temp = R[low]; ??????????? while (low < high) ??????????? { ??????????????? while(low<high&&R[high]%2==0) ??????????????? { ??????????????????? high--; ??????????????? } ??????????????? R[low] = R[high]; ??????????????? while (low < high && R[low] % 2 == 1) ??????????????? { ?????????????????? low++; ??????????????? } ??????????????? R[high] = R[low]; ??????????? } ??????????? R[low] = temp; ??????? }

??????? 7.二分查找算法

??????????????? 二分查找算法又叫折半查找，優(yōu)點(diǎn)是比較次數(shù)少，查找速度快，平均性能好，缺點(diǎn)是給定的數(shù)組必須是有序的，且插入刪除困難，因此二分查找使用與不經(jīng)常變動而又查找頻繁的有序表。 首先，假設(shè)數(shù)組是按照升序的有序表，將表中間位置的元素與給定要查找的元素比較，如果相等，則查找成功，否則利用中間位置將表分為前后兩個字表，如果中間位置記錄的元素大于給定的查找的數(shù)據(jù)，在前面的字表中進(jìn)行查找，否則在后面的字表中進(jìn)行查找。重復(fù)以上過程，直到找到或沒有子表為止。

具體實(shí)現(xiàn)代碼如下：

?????? private static int BinarySearch(int[] R, int arg) ??????? { ??????????? int low = 0; ??????????? int high = R.Length - 1; ??????????? while (low < high) ??????????? { ??????????????? int middle = (low + high) / 2; ??????????????? if (arg == R[middle]) ??????????????? { ??????????????????? return middle; ??????????????? } ??????????????? else if (arg < R[middle]) ??????????????? { ??????????????????? high = middle - 1; ??????????????? } ??????????????? else ??????????????? { ??????????????????? low = middle + 1; ??????????????? } ??????????? } ??????????? return -1; ??????? }

轉(zhuǎn)載于:https://www.cnblogs.com/lyq88/archive/2013/01/10/2853983.html

總結(jié)

以上是生活随笔為你收集整理的C#实现(递归和非递归)快速排序和简单排序的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。