C#七大經典排序算法系列(上)。本站提示廣大學習愛好者:(C#七大經典排序算法系列(上))文章只能為提供參考,不一定能成為您想要的結果。以下是C#七大經典排序算法系列(上)正文
今天是開篇,得要吹一下算法,算法就好比程序開發中的利劍,所到之處,刀起頭落。
針對現實中的排序問題,算法有七把利劍可以助你馬道成功。
首先排序分為四種:
交換排序: 包括冒泡排序,快速排序。
選擇排序: 包括直接選擇排序,堆排序。
插入排序: 包括直接插入排序,希爾排序。
合並排序: 合並排序。
那麼今天我們講的就是交換排序,我們都知道,C#類庫提供的排序是快排,為了讓今天玩的有意思點,
我們設計算法來跟類庫提供的快排較量較量。爭取KO對手。
冒泡排序:
首先我們自己來設計一下“冒泡排序”,這種排序很現實的例子就是:
我抓一把沙仍進水裡,那麼沙子會立馬沉入水底, 沙子上的灰塵會因為慣性暫時沉入水底,但是又會立馬像氣泡一樣浮出水面,最後也就真相大白咯。
關於冒泡的思想,我不會說那麼官方的理論,也不會貼那些文字上來,我的思想就是看圖說話。
那麼我們就上圖.
要達到冒泡的效果,我們就要把一組數字豎起來看,大家想想,如何冒泡?如何來體會重的沉底,輕的上浮?
第一步: 我們拿40跟20比,發現40是老大,不用交換。
第二步: 然後向前推一步,就是拿20跟30比,發現30是老大,就要交換了。
第三步:拿交換後的20跟10比,發現自己是老大,不用交換。
第四步:拿10跟50交換,發現50是老大,進行交換。
最後,我們經過一次遍歷,把數組中最小的數字送上去了,看看,我們向目標又邁進了一步。
現在大家思想都知道了,下面我們就強烈要求跟快排較量一下,不是你死就是我活。
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Diagnostics; using System.Threading; namespace BubbleSort { public class Program { static void Main(string[] args) { //五次比較 for (int i = 1; i <= 5; i++) { List<int> list = new List<int>(); //插入2k個隨機數到數組中 for (int j = 0; j < 2000; j++) { Thread.Sleep(1); list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 100000)); } Console.WriteLine("\n第" + i + "次比較:"); Stopwatch watch = new Stopwatch(); watch.Start(); var result = list.OrderBy(single => single).ToList(); watch.Stop(); Console.WriteLine("\n快速排序耗費時間:" + watch.ElapsedMilliseconds); Console.WriteLine("輸出前是十個數:" + string.Join(",", result.Take(10).ToList())); watch.Start(); result = BubbleSort(list); watch.Stop(); Console.WriteLine("\n冒泡排序耗費時間:" + watch.ElapsedMilliseconds); Console.WriteLine("輸出前是十個數:" + string.Join(",", result.Take(10).ToList())); } } //冒泡排序算法 static List<int> BubbleSort(List<int> list) { int temp; //第一層循環: 表明要比較的次數,比如list.count個數,肯定要比較count-1次 for (int i = 0; i < list.Count - 1; i++) { //list.count-1:取數據最後一個數下標, //j>i: 從後往前的的下標一定大於從前往後的下標,否則就超越了。 for (int j = list.Count - 1; j > i; j--) { //如果前面一個數大於後面一個數則交換 if (list[j - 1] > list[j]) { temp = list[j - 1]; list[j - 1] = list[j]; list[j] = temp; } } } return list; } } }
嗚嗚,看著這兩種排序體檢報告,心都涼了,冒泡被快排KO了,真慘,難怪人家說冒泡效率低,原來真低。
快速排序:
既然能把冒泡KO掉,馬上就激起我們的興趣,tnd快排咋這麼快,一定要好好研究一下。
首先上圖:
從圖中我們可以看到:
left指針,right指針,base參照數。
其實思想是蠻簡單的,就是通過第一遍的遍歷(讓left和right指針重合)來找到數組的切割點。
第一步:首先我們從數組的left位置取出該數(20)作為基准(base)參照物。
第二步:從數組的right位置向前找,一直找到比(base)小的數,
如果找到,將此數賦給left位置(也就是將10賦給20),
此時數組為:10,40,50,10,60,
left和right指針分別為前後的10。
第三步:從數組的left位置向後找,一直找到比(base)大的數,
如果找到,將此數賦給right的位置(也就是40賦給10),
此時數組為:10,40,50,40,60,
left和right指針分別為前後的40。
第四步:重復“第二,第三“步驟,直到left和right指針重合,
最後將(base)插入到40的位置,
此時數組值為: 10,20,50,40,60,至此完成一次排序。
第五步:此時20已經潛入到數組的內部,20的左側一組數都比20小,20的右側作為一組數都比20大,
以20為切入點對左右兩邊數按照"第一,第二,第三,第四"步驟進行,最終快排大功告成。
同樣,我們把自己設計的快排跟類庫提供的快拍比較一下。
using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading; using System.Diagnostics; namespace QuickSort { public class Program { static void Main(string[] args) { //5次比較 for (int i = 1; i <= 5; i++) { List<int> list = new List<int>(); //插入200個隨機數到數組中 for (int j = 0; j < 200; j++) { Thread.Sleep(1); list.Add(new Random((int)DateTime.Now.Ticks).Next(0, 10000)); } Console.WriteLine("\n第" + i + "次比較:"); Stopwatch watch = new Stopwatch(); watch.Start(); var result = list.OrderBy(single => single).ToList(); watch.Stop(); Console.WriteLine("\n系統定義的快速排序耗費時間:" + watch.ElapsedMilliseconds); Console.WriteLine("輸出前是十個數:" + string.Join(",", result.Take(10).ToList())); watch.Start(); new QuickSortClass().QuickSort(list, 0, list.Count - 1); watch.Stop(); Console.WriteLine("\n俺自己寫的快速排序耗費時間:" + watch.ElapsedMilliseconds); Console.WriteLine("輸出前是十個數:" + string.Join(",", list.Take(10).ToList())); } } } public class QuickSortClass { ///<summary> /// 分割函數 ///</summary> ///<param name="list">待排序的數組</param> ///<param name="left">數組的左下標</param> ///<param name="right"></param> ///<returns></returns> public int Division(List<int> list, int left, int right) { //首先挑選一個基准元素 int baseNum = list[left]; while (left < right) { //從數組的右端開始向前找,一直找到比base小的數字為止(包括base同等數) while (left < right && list[right] >= baseNum) right = right - 1; //最終找到了比baseNum小的元素,要做的事情就是此元素放到base的位置 list[left] = list[right]; //從數組的左端開始向後找,一直找到比base大的數字為止(包括base同等數) while (left < right && list[left] <= baseNum) left = left + 1; //最終找到了比baseNum大的元素,要做的事情就是將此元素放到最後的位置 list[right] = list[left]; } //最後就是把baseNum放到該left的位置 list[left] = baseNum; //最終,我們發現left位置的左側數值部分比left小,left位置右側數值比left大 //至此,我們完成了第一篇排序 return left; } public void QuickSort(List<int> list, int left, int right) { //左下標一定小於右下標,否則就超越了 if (left < right) { //對數組進行分割,取出下次分割的基准標號 int i = Division(list, left, right); //對“基准標號“左側的一組數值進行遞歸的切割,以至於將這些數值完整的排序 QuickSort(list, left, i - 1); //對“基准標號“右側的一組數值進行遞歸的切割,以至於將這些數值完整的排序 QuickSort(list, i + 1, right); } } } }
不錯,快排就是快,難怪內庫非要用他來作為排序的標准。
嗯,最後要分享下:
冒泡的時間復雜度為:0(n) - 0(n^2)
快排的時間復雜度為:
平均復雜度:N(logN)
最壞復雜度: 0(n^2)
以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持。