不懂演算法的程序員不是好工程師!
時刻提醒自己,技術之路修遠兮,予以自勉。
作者 | 菜鳥奮鬥史
責編 | 胡巍巍
演算法主要衡量標準
時間複雜度(運行時間)
在演算法時間複雜度維度,我們主要對比較和交換的次數做對比,其他不交換元素的演算法,主要會以訪問數組的次數的維度做對比。
其實有很多同學對於演算法的時間複雜度有點模糊,分不清什麼所謂的O(n),O(nlogn),O(logn)......等,也許下圖對一些人有一些更直觀的認識。
空間複雜度(額外的內存使用)
排序演算法的額外內存開銷和運行時間同等重要。就算一個演算法時間複雜度比較優秀,空間複雜度非常差,使用的額外內存非常大,筆者認為它也算不上一個優秀的演算法。
結果的正確性
這個指標是筆者自己加上的,我始終認為一個優秀的演算法最終得到的結果必須是正確的。就算一個演算法擁有非常優秀的時間和空間複雜度,但是結果不正確,又有什麼意義呢?
原理
在起始位置右側(或左側)找出最小的那個元素,然後和起始位置的元素交換。選擇排序是一個不穩定的排序演算法。
具體步驟如下:
在一個數據列表中找到最小的那個元素,將它和列表的第一個元素交換位置。
在第二個元素位置開始再次尋找最小的那個元素,然後和列表的第二個位置的元素交換。
在第三個元素位置開始再次尋找最小的那個元素,然後和列表的第三個位置的元素交換
如此反覆,直到開始查找起始位置到達列表末尾。
如果查找過程中最小的元素就是起止位置的元素,那麼它就和它自己交換。
因為這種演算法總是在不斷的選擇剩餘元素中最小者,因此得名選擇排序。
複雜度
時間複雜度
1.比較次數
對於長度為N的列表,選擇排序需要大約n2 /2次比較.即:O(n2)平方級別。
2.交換次數
對於長度為N的列表,選擇排序需要大約N次交換.即:O(N) 線性級別。
性能和特點
總體來說,選擇排序是一種比較簡單的排序演算法,很容易理解也很好用代碼實現,當然他的特點也很明顯:
運行時間和數據初始狀態無關
為什麼這麼說呢?演算法進行中為了查找最小的元素而遍歷列表並不能為下次遍歷帶來任何信息,這個特性在大部分情況下是缺點。
如果一個數據列表初始狀態是有序的或者部分有序的,選擇排序仍然需要全部掃描一次和交換。因此和一個完全無序的列表排序所花的時間相差不大。
數據移動次數是最少的
每次交換隻會改變兩個列表元素,因此長度為N的列表只會發生N次交換,交換次數和列表的長度是線性關係,其他演算法都不具備這個特性。
適用場景
由於選擇排序的對比次數在平方級別,但是移動次數在線性級別,所以當N比較小的時候比較適用。
其他
為什麼選擇排序不穩定呢?
首先我們要明白演算法穩定是什麼意思呢?
在待排序的數據中,存在多個相同的數據,經過排序之後,他們的相對順序依舊保持不變,實際上就是說array[i]=array[j],i
那麼經過排序之後array[i]依舊在array[j]之前,那麼這個排序演算法穩定,否則,這個排序演算法不穩定。
根據以上定義很容易可以得出這樣的結論:
我們舉出一個實例,序列5 8 5 2 9, 這個在執行選擇排序的時候,第一遍,肯定會將array[0]=5,交換到2所在的位置,也就是 2 8 5 5 9。
那麼很顯然,之後的排序我們就會發現,array[2]中的5會出現在原先的array[0]之前,所以選擇排序不是一個穩定的排序。
實現案例
c#
staticvoidMain(string[] args)
{
List data =newList() ;
for(inti =; i
{
data.Add(newRandom(Guid.NewGuid().GetHashCode()).Next(1,100));
}
//列印原始數組值
Console.WriteLine($"原始數據:{string.Join(",", data)}");
intn = data.Count;
//此處可以直接從第二個元素開始
for(inti =1; i
{
//查找最小的元素的索引
for(intj = i; j>; j--)
{
if(data[j]
{
//異或法 交換兩個變數,不用臨時變數
data[j] = data[j] ^ data[j-1];
data[j-1] = data[j] ^ data[j -1];
data[j ] = data[j] ^ data[j -1];
}
}
}
//列印排序後的數組
Console.WriteLine($"排序數據:{string.Join(",", data)}");
Console.Read();
}
運行結果:
原始數據:97,85,61,22,62,12,67,22,68,42
排序數據:12,22,22,42,61,62,67,68,85,97
作者簡介:一個奔走在通往互聯網更高之路的工程師,熱衷於互聯網技術。目前就職於某互聯網教育公司,應用服務端主要負責人。擁有10年+互聯網開發經驗。熱衷於高性能、高並發、分散式技術領域的研究。 主要工作語言為C#和Golang 。
※把 Python 扒了一層皮後,得出了這些結論……
※阿里全盤調整組織架構意味著什麼?|暢言
TAG:CSDN |