C語言直接插入排序算法

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

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

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];  // 設置哨兵
            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.算法介紹

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

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

3.實例

#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];  // 設置哨兵
            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] << " ";

}

總結

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

您可能感興趣的文章:

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