一缸沃、幾種經(jīng)典排序算法及其時(shí)間復(fù)雜度級(jí)別
冒泡、插入幌绍、選擇 O(n^2) 基于比較
快排颁褂、歸并 O(nlogn) 基于比較
計(jì)數(shù)、基數(shù)傀广、桶 O(n) 不基于比較
二颁独、如何分析一個(gè)排序算法？
1.學(xué)習(xí)排序算法的思路伪冰？明確原理誓酒、掌握實(shí)現(xiàn)以及分析性能。
2.如何分析排序算法性能？從執(zhí)行效率靠柑、內(nèi)存消耗以及穩(wěn)定性3個(gè)方面分析排序算法的性能寨辩。
3.執(zhí)行效率：從以下3個(gè)方面來(lái)衡量
1）最好情況、最壞情況歼冰、平均情況時(shí)間復(fù)雜度
2）時(shí)間復(fù)雜度的系數(shù)靡狞、常數(shù)、低階：排序的數(shù)據(jù)量比較小時(shí)考慮
3）比較次數(shù)和交換（或移動(dòng)）次數(shù)
4.內(nèi)存消耗：通過(guò)空間復(fù)雜度來(lái)衡量隔嫡。針對(duì)排序算法的空間復(fù)雜度甸怕，引入原地排序的概念，原地排序算法就是指空間復(fù)雜度為O(1)的排序算法腮恩。
5.穩(wěn)定性：如果待排序的序列中存在值等的元素蕾各，經(jīng)過(guò)排序之后，相等元素之間原有的先后順序不變庆揪，就說(shuō)明這個(gè)排序算法時(shí)穩(wěn)定的式曲。
三、冒泡排序
1.排序原理
1）冒泡排序只會(huì)操作相鄰的兩個(gè)數(shù)據(jù)缸榛。
2）對(duì)相鄰兩個(gè)數(shù)據(jù)進(jìn)行比較吝羞，看是否滿(mǎn)足大小關(guān)系要求，若不滿(mǎn)足讓它倆互換内颗。
3）一次冒泡會(huì)讓至少一個(gè)元素移動(dòng)到它應(yīng)該在的位置钧排，重復(fù)n次，就完成了n個(gè)數(shù)據(jù)的排序工作均澳。
4）優(yōu)化：若某次冒泡不存在數(shù)據(jù)交換恨溜，則說(shuō)明已經(jīng)達(dá)到完全有序，所以終止冒泡找前。
2.代碼實(shí)現(xiàn)
/// <summary>
/// 冒泡排序
/// </summary>
/// <param name="array"></param>
public static void BubbleSort(int[] array)
{
for (int i = 0; i < array.Length - 1; i++)
{
for (int j = 0; j < array.Length - 1 - i; j++)
{
if(array[j] > array[j + 1])
{
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
3.性能分析
1）執(zhí)行效率：最小時(shí)間復(fù)雜度糟袁、最大時(shí)間復(fù)雜度、平均時(shí)間復(fù)雜度
最小時(shí)間復(fù)雜度：數(shù)據(jù)完全有序時(shí)躺盛，只需進(jìn)行一次冒泡操作即可项戴，時(shí)間復(fù)雜度是O(n)。
最大時(shí)間復(fù)雜度：數(shù)據(jù)倒序排序時(shí)槽惫，需要n次冒泡操作周叮，時(shí)間復(fù)雜度是O(n^2)。
平均時(shí)間復(fù)雜度：通過(guò)有序度和逆序度來(lái)分析界斜。
什么是有序度仿耽？
有序度是數(shù)組中具有有序關(guān)系的元素對(duì)的個(gè)數(shù)，比如[2,4,3,1,5,6]這組數(shù)據(jù)的有序度就是11各薇，分別是[2,4][2,3][2,5][2,6][4,5][4,6][3,5][3,6][1,5][1,6][5,6]项贺。同理，對(duì)于一個(gè)倒序數(shù)組，比如[6,5,4,3,2,1]敬扛，有序度是0晰洒；對(duì)于一個(gè)完全有序的數(shù)組，比如[1,2,3,4,5,6]啥箭，有序度為n(n-1)/2谍珊，也就是15，完全有序的情況稱(chēng)為滿(mǎn)有序度急侥。
什么是逆序度砌滞？逆序度的定義正好和有序度相反。核心公式：逆序度=滿(mǎn)有序度-有序度坏怪。
排序過(guò)程贝润，就是有序度增加，逆序度減少的過(guò)程铝宵，最后達(dá)到滿(mǎn)有序度打掘，就說(shuō)明排序完成了。
冒泡排序包含兩個(gè)操作原子鹏秋，即比較和交換尊蚁，每交換一次，有序度加1侣夷。不管算法如何改進(jìn)横朋，交換的次數(shù)總是確定的，即逆序度百拓。
對(duì)于包含n個(gè)數(shù)據(jù)的數(shù)組進(jìn)行冒泡排序琴锭，平均交換次數(shù)是多少呢？最壞的情況初始有序度為0衙传，所以要進(jìn)行n(n-1)/2交換决帖。最好情況下，初始狀態(tài)有序度是n(n-1)/2粪牲，就不需要進(jìn)行交互古瓤。我們可以取個(gè)中間值n(n-1)/4，來(lái)表示初始有序度既不是很高也不是很低的平均情況腺阳。
換句話說(shuō)，平均情況下穿香，需要n*(n-1)/4次交換操作亭引，比較操作可定比交換操作多，而復(fù)雜度的上限是O(n2)皮获，所以平均情況時(shí)間復(fù)雜度就是O(n2)焙蚓。
以上的分析并不嚴(yán)格，但很實(shí)用，這就夠了购公。
2）空間復(fù)雜度：每次交換僅需1個(gè)臨時(shí)變量萌京，故空間復(fù)雜度為O(1)，是原地排序算法宏浩。
3）算法穩(wěn)定性：如果兩個(gè)值相等知残，就不會(huì)交換位置，故是穩(wěn)定排序算法比庄。
四求妹、插入排序
1.算法原理
首先，我們將數(shù)組中的數(shù)據(jù)分為2個(gè)區(qū)間佳窑，即已排序區(qū)間和未排序區(qū)間制恍。初始已排序區(qū)間只有一個(gè)元素础废，就是數(shù)組的第一個(gè)元素韧掩。插入算法的核心思想就是取未排序區(qū)間中的元素，在已排序區(qū)間中找到合適的插入位置將其插入铅乡，并保證已排序區(qū)間中的元素一直有序溉委。重復(fù)這個(gè)過(guò)程强挫，直到未排序中元素為空，算法結(jié)束薛躬。
2.代碼實(shí)現(xiàn)
/// <summary>
/// 插入排序
/// </summary>
/// <param name="array"></param>
public static void InsertionSort(int[] array)
{
if (array.Length <= 1) return;
for (int i = 1; i < array.Length; i++)
{
int value = array[i]; //要插入的數(shù)
int j = i - 1;
//尋找插入的位置,從有序區(qū)間后往前遍歷
for (; j >= 0; j--)
{
if(array[j] > value)
{
array[j + 1] = array[j];
}
else
{
break;
}
}
array[j + 1] = value; //插入數(shù)據(jù)
}
}
3.性能分析
1）時(shí)間復(fù)雜度：最好俯渤、最壞、平均情況
如果要排序的數(shù)組已經(jīng)是有序的型宝，我們并不需要搬移任何數(shù)據(jù)八匠。只需要遍歷一遍數(shù)組即可，所以時(shí)間復(fù)雜度是O(n)趴酣。如果數(shù)組是倒序的梨树，每次插入都相當(dāng)于在數(shù)組的第一個(gè)位置插入新的數(shù)據(jù)，所以需要移動(dòng)大量的數(shù)據(jù)岖寞，因此時(shí)間復(fù)雜度是O(n2)抡四。而在一個(gè)數(shù)組中插入一個(gè)元素的平均時(shí)間復(fù)雜都是O(n)，插入排序需要n次插入仗谆，所以平均時(shí)間復(fù)雜度是O(n2)指巡。
2）空間復(fù)雜度：從上面的代碼可以看出，插入排序算法的運(yùn)行并不需要額外的存儲(chǔ)空間隶垮，所以空間復(fù)雜度是O(1)藻雪，是原地排序算法。
3）算法穩(wěn)定性：在插入排序中狸吞，對(duì)于值相同的元素勉耀，我們可以選擇將后面出現(xiàn)的元素指煎，插入到前面出現(xiàn)的元素的后面，這樣就保持原有的順序不變便斥，所以是穩(wěn)定的至壤。
五、選擇排序
- 選擇排序?qū)?shù)組分成已排序區(qū)間和未排序區(qū)間枢纠。初始已排序區(qū)間為空像街。每次從未排序區(qū)間中選出最小的元素插入已排序區(qū)間的末尾，直到未排序區(qū)間為空京郑。
- 空間復(fù)雜度：選擇排序是原地排序算法宅广。
- 時(shí)間復(fù)雜度：最好情況、最壞情況些举、平均情況（都是O(n^2)）
- 穩(wěn)定性：選擇排序不是穩(wěn)定的排序算法跟狱。
- 代碼實(shí)現(xiàn)
/// <summary>
/// 選擇排序
/// </summary>
/// <param name="array"></param>
public static void SelectSort(int[] array)
{
if (array.Length <= 1) return;
for (int i = 0; i < array.Length; i++)
{
int min = i;
for (int j = array.Length - 1; j > i; j--)
{
if(array[j] < array[min])
{
min = j;
}
}
if(min != i)
{
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
}
