您好,登錄后才能下訂單哦!
今天小編給大家分享一下C語言如何直接插入排序算法的相關(guān)知識(shí)點(diǎn),內(nèi)容詳細(xì),邏輯清晰,相信大部分人都還太了解這方面的知識(shí),所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。
直接插入排序是一種最簡(jiǎn)單的排序方法,其基本操作是將一條記錄插入到已排好的有序表中,從而得到一個(gè)新的、記錄數(shù)量增1的有序表。
每次從無序表中取出第一個(gè)元素,把它插入到有序表的合適位置,使有序表仍然有序。
第一趟比較前兩個(gè)數(shù),然后把第二個(gè)數(shù)按大小插入到有序表中; 第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從后向前掃描,把第三個(gè)數(shù)按大小插入到有序表中;依次進(jìn)行下去,進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過程。
下面的動(dòng)圖非常清晰的詮釋了直接插入排序的過程:
時(shí)間復(fù)雜度
最好的情況是數(shù)組所有元素已經(jīng)是有序排列,在排序時(shí)待排元素只需與前一元素比較,不用繼續(xù)往前搜索比較,時(shí)間復(fù)雜度為O(n);
最差的情況是數(shù)組所有元素全部反序,在排序時(shí)待排元素需要與前面所有有序元素進(jìn)行比較,比較次數(shù)為:
1+2+…+(n-1) = n(n-1)/2
每次前面的有序元素均要往后移動(dòng),移動(dòng)次數(shù)為:
(1+2)+(2+2)+…+(n-1+2) =(n-1)(n+4)/2
綜上所述,直接插入排序的平均時(shí)間復(fù)雜度為O( n 2 n^2 n2) 。
直接插入排序?yàn)槠叫幸苿?dòng),因此空間復(fù)雜度為:O(1) 。
優(yōu)點(diǎn):直接插入排序算法簡(jiǎn)單,當(dāng)待排序記錄數(shù)量n很小時(shí),局部有序時(shí),較為適用。
缺點(diǎn):當(dāng)數(shù)據(jù)量龐大并且亂序嚴(yán)重時(shí),比較和移動(dòng)次數(shù)多,排序效率低。
a. 實(shí)現(xiàn)直接插入排序需要設(shè)計(jì)兩層循環(huán),整個(gè)數(shù)組為外循環(huán),已經(jīng)排列好的有序元素為內(nèi)循環(huán);
b. 從外循環(huán)取出待排元素array[i],使用臨時(shí)變量temp存儲(chǔ)其值;
c. 將待排元素與內(nèi)循環(huán)的有序元素依次(從后往前)進(jìn)行比較,若有序元素比待排元素大,則向后移動(dòng)一位;
d. 直至有序元素比待排元素小,則不再移動(dòng),將temp賦值給array[j+1]。
#include <stdio.h> void printArray(int array[], int size) { int i; for (i = 0; i < size; i++) { printf("%d ", array[i]); } printf("\n"); } void insertSort(int array[], int size) { int temp,i,j; for (i = 1; i < size; i++) { temp = array[i]; j = i-1; while (j >= 0 && array[j] > temp) { array[j+1] = array[j]; j--; } array[j+1] = temp; printArray(array, size); } } int main() { int array[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48}; printArray(array, sizeof(array)/sizeof(int)); insertSort(array, sizeof(array)/sizeof(int)); return 0; }
運(yùn)行結(jié)果:
3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
3 38 44 5 47 15 36 26 27 2 46 4 19 50 48
3 5 38 44 47 15 36 26 27 2 46 4 19 50 48
3 5 38 44 47 15 36 26 27 2 46 4 19 50 48
3 5 15 38 44 47 36 26 27 2 46 4 19 50 48
3 5 15 36 38 44 47 26 27 2 46 4 19 50 48
3 5 15 26 36 38 44 47 27 2 46 4 19 50 48
3 5 15 26 27 36 38 44 47 2 46 4 19 50 48
2 3 5 15 26 27 36 38 44 47 46 4 19 50 48
2 3 5 15 26 27 36 38 44 46 47 4 19 50 48
2 3 4 5 15 26 27 36 38 44 46 47 19 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50
以上就是“C語言如何直接插入排序算法”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會(huì)為大家更新不同的知識(shí),如果還想學(xué)習(xí)更多的知識(shí),請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。