快捷導(dǎo)航

C語(yǔ)言直接插入排序算法

更新時(shí)間：2022年01月07日 09:47:43 作者：恒天1020

大家好，本篇文章主要講的是C語(yǔ)言直接插入排序算法，感興趣的同學(xué)趕快來(lái)看一看吧，對(duì)你有幫助的話記得收藏一下，方便下次瀏覽

1.算法模板

void InsertSort(SqList *L)
{
    int j;
    for (int i = 2; i <= L->length; i ++ ) {
        if (L->arr[i] < L->arr[i-1])
        {
            L->arr[0] = L->arr[i];  // 設(shè)置哨兵
            for (j = i - 1; L->arr[j] > L->arr[0]; j -- )
                L->arr[j + 1] = L->arr[j];
            L->arr[j + 1] = L->arr[0];
        }
    }
}

2.算法介紹

直接插入排序的基本思想是：對(duì)于一個(gè)長(zhǎng)度為n的序列，從第2的元素開(kāi)始，逐個(gè)向之前排好的序列中插入新元素（第1個(gè)元素可以視為一個(gè)長(zhǎng)度為1的有序的子序列），從而得到一個(gè)長(zhǎng)度為n的有序的序列。

算法的時(shí)間復(fù)雜度為O(n^2)，最好的情況為待排序列本身就是有序的，只需要遍歷一遍，時(shí)間復(fù)雜度為O(n)，最壞的情況為逆序，時(shí)間復(fù)雜度為O(n*n)，由于元素之間是逐個(gè)進(jìn)行比較的，直接插入排序是一種穩(wěn)定的排序算法。

3.實(shí)例

#include <iostream>
using namespace std;

const int N = 100;

typedef struct
{
    int arr[N];
    int length;
} SqList;

void InsertSort(SqList *L)
{
    int j;
    for (int i = 2; i <= L->length; i ++ ) {
        if (L->arr[i] < L->arr[i-1])
        {
            L->arr[0] = L->arr[i];  // 設(shè)置哨兵
            for (j = i - 1; L->arr[j] > L->arr[0]; j -- )
                L->arr[j + 1] = L->arr[j];
            L->arr[j + 1] = L->arr[0];
        }
    }
}

int main()
{
    SqList L;
    L.arr[1] = 50;
    L.arr[2] = 10;
    L.arr[3] = 90;
    L.arr[4] = 30;
    L.arr[5] = 70;
    L.arr[6] = 40;
    L.arr[7] = 80;
    L.arr[8] = 60;
    L.arr[9] = 20;
    L.length = 9;

    InsertSort(&L);
    for (int i = 1; i <= L.length; i ++ )
        cout << L.arr[i] << " ";

}

總結(jié)

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

您可能感興趣的文章:

相關(guān)文章

Linux vmstat命令實(shí)戰(zhàn)詳細(xì)解析
這個(gè)命令是我查看Linux/Unix最喜愛(ài)的命令，一個(gè)是Linux/Unix都支持，二是相比top，我可以看到整個(gè)機(jī)器的CPU,內(nèi)存,IO的使用情況，而不是單單看到各個(gè)進(jìn)程的CPU使用率和內(nèi)存使用率(使用場(chǎng)景不一樣)
2013-09-09
詳解C++之函數(shù)重載
這篇文章主要介紹了c++函數(shù)重載的相關(guān)知識(shí)，文章講解的非常細(xì)致，代碼幫助大家更好的理解和學(xué)習(xí)，感興趣的朋友可以了解下
2020-06-06
C語(yǔ)言函數(shù)調(diào)用堆棧詳情分析
這篇文章主要介紹了C語(yǔ)言函數(shù)調(diào)用堆棧詳情分析，文章圍繞主題展開(kāi)詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，需要的小伙伴可以參考一下
2022-07-07
深入探索C++中stack和queue的底層實(shí)現(xiàn)
這篇文章主要介紹了C++中的stack和dequeue的底層實(shí)現(xiàn),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下
2023-09-09
C++封裝成DLL并調(diào)用的實(shí)現(xiàn)
本文主要介紹了C++封裝成DLL并調(diào)用的實(shí)現(xiàn)，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2023-03-03
基于Linux系統(tǒng)調(diào)用--getrlimit()與setrlimit()函數(shù)的方法
本篇文章是對(duì)在Linux系統(tǒng)中調(diào)用getrlimit()與setrlimit()函數(shù)的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下
2013-05-05
深入解析int(*p)[]和int(**p)[]
以下是對(duì)int(*p)[]和int(**p)[]的使用進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以參考下
2013-07-07
c語(yǔ)言實(shí)現(xiàn)從源文件從文本到可執(zhí)行文件經(jīng)歷的過(guò)程
這篇文章主要介紹了c語(yǔ)言實(shí)現(xiàn)從源文件從文本到可執(zhí)行文件經(jīng)歷的過(guò)程，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教
2022-07-07
c++與c中的數(shù)組初始化默認(rèn)值如何為0
這篇文章主要介紹了c++與c中的數(shù)組初始化默認(rèn)值如何為0問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
2023-08-08
C語(yǔ)言實(shí)現(xiàn)游戲VIP停車場(chǎng)管理系統(tǒng)
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)游戲VIP停車場(chǎng)管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2019-12-12