您好,登錄后才能下訂單哦!
這篇文章主要講解了“C語言排序算法實(shí)例分析”,文中的講解內(nèi)容簡(jiǎn)單清晰,易于學(xué)習(xí)與理解,下面請(qǐng)大家跟著小編的思路慢慢深入,一起來研究和學(xué)習(xí)“C語言排序算法實(shí)例分析”吧!
基本思想:當(dāng)插入第i(i>=1)個(gè)元素時(shí),前面的array[0],array[1],…,array[i-1]已經(jīng)排好序,此時(shí)用array[i]的排 序碼與array[i-1],array[i-2],…的排序碼順序進(jìn)行比較,找到插入位置即將array[i]插入,原來位置上的元素順序后移!
直接插入排序的特性總結(jié):
1. 元素集合越接近有序,直接插入排序算法的時(shí)間效率越高
2. 時(shí)間復(fù)雜度:O(N^2) 、空間復(fù)雜度:O(1)
3. 穩(wěn)定性:穩(wěn)定
void InsertSort(int* a, int n) { //直接插入排序 ———— 升序 for (int i = 0; i < n - 1; ++i) { int end = i; int tmp = a[end + 1]; while (end >= 0) { if (a[i] > tmp) //如果比tmp大的話就往后移 { a[end + 1] = a[end]; --end; } else //如果tmp比當(dāng)前元素大的話就不需要交換位置了,直接跳出循環(huán)! { break; } } a[end + 1] = tmp; // 最后把tmp放到比他小的元素后面! } }
基本思想:先選定一個(gè)整數(shù),把待排序文件中所有記錄分成個(gè)組,所有距離為gap的記錄分在同一組內(nèi),并對(duì)每一組內(nèi)的記錄進(jìn)行排序。然后重復(fù)分組和排序的工作。當(dāng)?shù)竭_(dá)gap=1時(shí),所有記錄在統(tǒng)一組內(nèi)排好序。
希爾排序的特性總結(jié):
1. 希爾排序是對(duì)直接插入排序的優(yōu)化。
2. 當(dāng)gap > 1時(shí)都是預(yù)排序,目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時(shí),數(shù)組已經(jīng)接近有序的 了,這樣就會(huì)很快。這樣整體而言,可以達(dá)到優(yōu)化的效果。
3. 希爾排序的時(shí)間復(fù)雜度不好計(jì)算,需要進(jìn)行推導(dǎo),推導(dǎo)出來平均時(shí)間復(fù)雜度: O(N^1.3— N^2)
4. 穩(wěn)定性:不穩(wěn)定
void ShellSort(int* a, int n) { //希爾排序————升序 int gap = n; while (gap > 1) { gap = gap / 2; for (int i = 0; i < n - gap; ++i) { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end = end - gap; } else { break; } a[end + gap] = tmp; } } } }
基本思想:
在元素集合array[i]--array[n-1]中選擇關(guān)鍵碼最大(小)的數(shù)據(jù)元素 若它不是這組元素中的最后一個(gè)(第一個(gè))元素,則將它與這組元素中的最后一個(gè)(第一個(gè))元素交換 在剩余的array[i]--array[n-2](array[i+1]--array[n-1])集合中,重復(fù)上述步驟,直到集合剩余1個(gè)元素。
直接選擇排序的特性總結(jié):(因?yàn)樘貏e簡(jiǎn)單就不畫圖了直接上代碼)
1. 直接選擇排序思考非常好理解,但是效率不是很好。實(shí)際中很少使用
2. 時(shí)間復(fù)雜度:O(N^2) 、空間復(fù)雜度:O(1)
3. 穩(wěn)定性:不穩(wěn)定
這里我們用一個(gè)優(yōu)化版本,每次確定兩個(gè)數(shù)的最終位置:
void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void SelectSort(int* a, int n) { int begin = 0; int end = n - 1; while (begin < end) { int min = begin; int max = begin; for (int i = begin; i <= end; ++i) { if (a[i] < a[min]) { min = i; } if (a[i] > a[max]) { max = i; } } Swap(&a[min], &a[begin]); if (max == begin) //如果max等于begin的話就證明最大值是begin的位置 //需要修正max的位置 { max = min; } Swap(&a[max], &a[end]); ++begin; --end; } }
堆排序(Heapsort)是指利用堆積樹(堆)這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法,它是選擇排序的 一種。它是通過堆來進(jìn)行選擇數(shù)據(jù)。需要注意的是排升序要建大堆,排降序建小堆。
堆排序的特性總結(jié):
1. 堆排序使用堆來選數(shù),效率就高了很多。
2. 時(shí)間復(fù)雜度:O(N*logN) 、空間復(fù)雜度:O(1)
3. 穩(wěn)定性:不穩(wěn)定
void AdjustDown(int* a, int n, int root) { int parent = root; int child = parent * 2 + 1; while (child < n) { if (child + 1 < n && a[child] < a[child + 1]) { child = child + 1; } if (a[child] > a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } void HeapSort(int* a, int n) { for (int i = (n - 1 - 1) / 2; i >= 0; --i) { AdjustDown(a, n, i); } int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); --end; } }
感謝各位的閱讀,以上就是“C語言排序算法實(shí)例分析”的內(nèi)容了,經(jīng)過本文的學(xué)習(xí)后,相信大家對(duì)C語言排序算法實(shí)例分析這一問題有了更深刻的體會(huì),具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云,小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章,歡迎關(guān)注!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。