C語言直接插入排序算法是什么

這篇文章將為大家詳細講解有關(guān)C語言直接插入排序算法是什么，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個參考，希望大家閱讀完這篇文章后對相關(guān)知識有一定的了解。

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.算法介紹

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

算法的時間復(fù)雜度為O(n^2)，最好的情況為待排序列本身就是有序的，只需要遍歷一遍，時間復(fù)雜度為O(n)，最壞的情況為逆序，時間復(fù)雜度為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];  // 設(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] << " ";

}

關(guān)于C語言直接插入排序算法是什么就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。