欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言直接插入排序算法介紹及示例

 更新時(shí)間:2022年08月11日 16:56:32   作者:柒號(hào)華仔  
插入排序是把一個(gè)記錄插入到已排序的有序序列中,使整個(gè)序列在插入該記錄后仍然有序。插入排序中較簡(jiǎn)單的種方法是直接插入排序,其插入位置的確定方法是將待插入的記錄與有序區(qū)中的各記錄自右向左依次比較其關(guān)鍵字值的大小

1. 直接插入排序介紹

1.1 定義

直接插入排序是一種最簡(jiǎn)單的排序方法,其基本操作是將一條記錄插入到已排好的有序表中,從而得到一個(gè)新的、記錄數(shù)量增1的有序表。

1.2 基本原理

每次從無序表中取出第一個(gè)元素,把它插入到有序表的合適位置,使有序表仍然有序。

第一趟比較前兩個(gè)數(shù),然后把第二個(gè)數(shù)按大小插入到有序表中; 第二趟把第三個(gè)數(shù)據(jù)與前兩個(gè)數(shù)從后向前掃描,把第三個(gè)數(shù)按大小插入到有序表中;依次進(jìn)行下去,進(jìn)行了(n-1)趟掃描以后就完成了整個(gè)排序過程。

下面的動(dòng)圖非常清晰的詮釋了直接插入排序的過程:

1.3 時(shí)間復(fù)雜度

時(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) 。

1.4 空間復(fù)雜度

直接插入排序?yàn)槠叫幸苿?dòng),因此空間復(fù)雜度為:O(1) 。

1.5 優(yōu)缺點(diǎn)

優(yōu)點(diǎn):直接插入排序算法簡(jiǎn)單,當(dāng)待排序記錄數(shù)量n很小時(shí),局部有序時(shí),較為適用。

缺點(diǎn):當(dāng)數(shù)據(jù)量龐大并且亂序嚴(yán)重時(shí),比較和移動(dòng)次數(shù)多,排序效率低。

2. 代碼實(shí)現(xiàn)

2.1 代碼設(shè)計(jì)

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]。

2.2 代碼實(shí)現(xiàn)

#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

到此這篇關(guān)于C語言直接插入排序算法介紹及示例的文章就介紹到這了,更多相關(guān)C語言直接插入排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • C語言楊氏矩陣中查找元素的示例代碼

    C語言楊氏矩陣中查找元素的示例代碼

    本文主要介紹了C語言楊氏矩陣中查找元素的示例代碼,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-07-07
  • Qt數(shù)據(jù)庫(kù)應(yīng)用之實(shí)現(xiàn)數(shù)據(jù)分組導(dǎo)出

    Qt數(shù)據(jù)庫(kù)應(yīng)用之實(shí)現(xiàn)數(shù)據(jù)分組導(dǎo)出

    這篇文章主要為大家詳細(xì)介紹了如何利用Qt實(shí)現(xiàn)數(shù)據(jù)庫(kù)數(shù)據(jù)分組導(dǎo)出,文中的示例代碼講解詳細(xì),對(duì)我們學(xué)習(xí)或工作有一定參考價(jià)值,需要的可以了解一下
    2022-06-06
  • C/C++獲取Windows平臺(tái)CPU占用率的方法

    C/C++獲取Windows平臺(tái)CPU占用率的方法

    最近在做系統(tǒng)信息相關(guān)的接口,為了實(shí)現(xiàn)跨平臺(tái),故在linux和Windows平臺(tái)獲取占用率信息,文章主要介紹Windows下的方法,文中給出了參考代碼,需要的朋友可以參考下
    2023-12-12
  • C語言實(shí)現(xiàn)簡(jiǎn)單的文本編輯器

    C語言實(shí)現(xiàn)簡(jiǎn)單的文本編輯器

    這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)簡(jiǎn)單的文本編輯器,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-05-05
  • C語言程序設(shè)計(jì)之指針的應(yīng)用詳解

    C語言程序設(shè)計(jì)之指針的應(yīng)用詳解

    為了讓大家能夠更準(zhǔn)確的了解C語言中指針的使用,本文為大家準(zhǔn)備了四個(gè)指針相關(guān)的例題,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以學(xué)習(xí)一下
    2022-11-11
  • C++如何在構(gòu)造函數(shù)和析構(gòu)函數(shù)中調(diào)用虛擬函數(shù)

    C++如何在構(gòu)造函數(shù)和析構(gòu)函數(shù)中調(diào)用虛擬函數(shù)

    這篇文章主要介紹了C++如何在構(gòu)造函數(shù)和析構(gòu)函數(shù)中調(diào)用虛擬函數(shù)問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-08-08
  • C++中l(wèi)ist的用法實(shí)例講解

    C++中l(wèi)ist的用法實(shí)例講解

    list是順序容器的一種,list是一個(gè)雙向鏈表,使用list需要包含頭文件list,這篇文章主要給大家介紹了關(guān)于C++中l(wèi)ist的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下
    2021-11-11
  • 詳解C語言動(dòng)態(tài)內(nèi)存的分配

    詳解C語言動(dòng)態(tài)內(nèi)存的分配

    這篇文章主要為大家介紹了C語言動(dòng)態(tài)內(nèi)存的分配,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來幫助
    2021-12-12
  • 利用Matlab制作一款狗頭翻牌子小游戲

    利用Matlab制作一款狗頭翻牌子小游戲

    本文將用Matlab制作一個(gè)狗頭翻牌子的小游戲,就是點(diǎn)擊一個(gè)牌子時(shí),該牌子和周圍四個(gè)牌子也會(huì)相應(yīng)發(fā)生變化,想辦法讓所有牌子都在同一面即為游戲勝利。感興趣的可以跟隨小編學(xué)習(xí)一下
    2022-03-03
  • C語言數(shù)據(jù)結(jié)構(gòu)之隊(duì)列算法詳解

    C語言數(shù)據(jù)結(jié)構(gòu)之隊(duì)列算法詳解

    這篇文章介紹了C語言數(shù)據(jù)結(jié)構(gòu)之隊(duì)列的算法,文中通過示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
    2021-12-12

最新評(píng)論