本篇將詳細(xì)講一下以下排序算法：
- 直接插入排序
- 希爾排序
- 選擇排序
- 快速排序
- 歸并排序
- 計(jì)數(shù)排序
排序的概念
排序：所謂排序，就是使一串記錄，按照其中的某個(gè)或某寫關(guān)鍵字的大小，按照遞增或遞減0排列起來的操作。
穩(wěn)定性的概念
假定在待排序的記錄序列中，存在多個(gè)具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對(duì)次序保持不變。如一下例子，
5?2 3 4 5 9 8
?經(jīng)過排序，如果紅5和藍(lán)5的相對(duì)順序不對(duì)，這就叫穩(wěn)定，反之則不穩(wěn)定。
?直接插入排序
直接插入排序的思想：將待排序的記錄按其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)排好序的序列中，直到所有的序列為有序序列。
實(shí)際中，我們玩撲克牌時(shí)，就用到了這樣的一個(gè)排序算法。
?
時(shí)間復(fù)雜度：?
直接插入排序時(shí)一個(gè)穩(wěn)定的排序，如果有相同的元素，它們的相對(duì)位置不會(huì)發(fā)生變化。它時(shí)間復(fù)雜度最好的情況下是O（N）,當(dāng)一個(gè)數(shù)插入到已經(jīng)排好序的序列中，只需要比較一次就好了。
最壞情況：O（N^2）?，在完全逆序的情況下，要排升序。
希爾排序?
?希爾排序其實(shí)和插入排序很像，只不過希爾排序的思想是：先預(yù)排序，最后插入排序。
預(yù)排序的意義在哪里？？
- 大的數(shù)更快到后面去，小的數(shù)更快到前面去。gap越大跳的越快，越不有序，當(dāng)gap =1 時(shí)就是插入排序。
?文章來源地址http://www.zghlxwxcb.cn/news/detail-713021.html
?文章來源：http://www.zghlxwxcb.cn/news/detail-713021.html
?時(shí)間復(fù)雜度
?
希爾排序的時(shí)間復(fù)雜度：大約為O（N^1.3）?
選擇排序
選擇排序的思想：選擇排序可以在一次查找中找到最大的數(shù)和最小的數(shù)，然后把最大的數(shù)放到最后，最小的數(shù)放到最前面。
?
時(shí)間復(fù)雜度
時(shí)間復(fù)雜度是O（N^2）
穩(wěn)定性：差?
?快速排序
快排思想：說到排序，或多或少都聽過快速排序，快速排序是Hoare于1962年提出的一種二叉樹結(jié)構(gòu)的交換方法，其基本思想為：任取待排序元素序列中的某個(gè)元素作為基準(zhǔn)值，按照該排序嗎將待排序集合分割成2個(gè)子序列，左序列小于keyi值，右序列大于keyi值，然后重復(fù)此方法，最后拍完序。
快速排序一次可以確定一個(gè)值在正確的位置上。（這個(gè)值就是key值）
if (begin >= end)
{
return;
}
int left = begin, right = end;
int keyi = left;
while (left < right)
{
//先讓右邊先走
while (left<right && a[right]>=a[keyi])
{
--right;
}
while (left < right && a[left] <= a[keyi])
{
++left;
}
Swap(&a[left], &a[right]);
}
Swap(&a[keyi], &a[left]);
keyi = left;
//[begin,keyi-1] keyi [keyi+1,end]
QuickSort(a,begin,keyi-1);
QuickSort(a,keyi+1,end);最常見的就是上面的遞歸代碼，這是Hoare的一種方式實(shí)現(xiàn)快排。
Hoare思想：讓基準(zhǔn)值的右邊先走，直到找到比基準(zhǔn)值小的數(shù)，然后讓左邊走，直到找到比基準(zhǔn)值大的數(shù)，然后交換，最后left=right相等的時(shí)候，將left位置的值與基準(zhǔn)值交換。這樣就實(shí)現(xiàn)了一次排序。
這里我們想一想快速排序?yàn)槭裁匆尰鶞?zhǔn)值的對(duì)面開始？？？？
?
挖坑法： 用一個(gè)tmp記錄第一個(gè)值的坑位，讓右邊先走，直到找到比坑位小的數(shù)，然后讓a[right]賦值給坑位，然后把坑位給給right，繼續(xù)讓左邊先走，直到找到比坑位大的數(shù)，然后把值賦給坑位，讓坑位給給left，一直循環(huán)。
?
?
前后指針法：讓prev指向key值，cur指向key值之后的一個(gè)值，當(dāng)a[cur] < a[key] 的時(shí)候，就讓prev++和cur交換，然后一直循環(huán)。
?
?
快排的非遞歸： 快排的思想其實(shí)不難發(fā)現(xiàn)像一個(gè)棧（后進(jìn)先出），因?yàn)榭炫琶看慰梢源_定一個(gè)基準(zhǔn)值的位置，所以，第一次push進(jìn)left和right，讓他們進(jìn)行一次排序，就接著push進(jìn)right和keyi+1，再push進(jìn)keyi-1和left，注意順序，因?yàn)榭炫诺闹虚g也是一個(gè)后進(jìn)先出的思想。
?
快排的缺點(diǎn)
?快排其實(shí)是有缺點(diǎn)的，因?yàn)榭炫诺臅r(shí)間復(fù)雜度不一定是O(N*logN），如果排升序，給一個(gè)倒序的序列，就有可能達(dá)到O(N^2)。所以有了這么一個(gè)缺點(diǎn)，就可以做一個(gè)三數(shù)區(qū)中的優(yōu)化，其實(shí)Sort函數(shù)中也有這樣的處理，而且Sort中還優(yōu)化了一次快排遞歸深度過深的時(shí)候會(huì)用堆排序，在接近有序的時(shí)候會(huì)用插入排序，而且Sort中只對(duì)了右邊進(jìn)行遞歸處理。如果有興趣，可以去了解一下Sort的源碼，里面有詳細(xì)解釋。
?歸并排序
歸并排序：它是建立在歸并操作上的一種有效的排序算法，該算法采用了分治的思想。將已有序的子序列合并，得到完全有序的序列；即先使每個(gè)子序列有序，再使子序列段有序。若將兩個(gè)有序表合并成一個(gè)有序表，稱為二路歸并。????????
歸并排序可以看出是一個(gè)后序的排序，?先遞歸，然后從前面開始排好序，然后再memcpy到原數(shù)組。
歸并排序其實(shí)用在解決磁盤外的外排序問題中，如果有下面的場(chǎng)景，歸并排序就起到了很大的作用。
時(shí)間復(fù)雜度
?歸并排序也是一種經(jīng)典的O(N*logN)? 空間復(fù)雜度是O(N),這時(shí)因?yàn)殚_辟了一塊tmp臨時(shí)數(shù)組
?
計(jì)數(shù)排序?
思想：計(jì)數(shù)排序又稱為鴿巢原理，是對(duì)哈希直接定址法的變形應(yīng)用。
步驟：1.統(tǒng)計(jì)想相同元素出現(xiàn)的次數(shù)
2.根據(jù)統(tǒng)計(jì)的結(jié)果將序列回收到原來的序列中
?
?計(jì)數(shù)排序的特性：
- 計(jì)數(shù)排序在數(shù)據(jù)范圍集中時(shí)，效率很高，但是使用范圍及場(chǎng)景有限。
- 時(shí)間復(fù)雜度：O(MAX(N,范圍))
- 空間復(fù)雜度：O(范圍)
?
?
到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)——排序算法（C語言）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
