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

2022-08-11 22:00:54

1. 直接插入排序介紹

1.1 定義

直接插入排序是一種最簡單的排序方法，其基本操作是將一條記錄插入到已排好的有序表中，從而得到一個新的、記錄數量增1的有序表。

1.2 基本原理

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

第一趟比較前兩個數，然後把第二個數按大小插入到有序表中；第二趟把第三個資料與前兩個數從後向前掃描，把第三個數按大小插入到有序表中；依次進行下去，進行了(n-1)趟掃描以後就完成了整個排序過程。

下面的動圖非常清晰的詮釋了直接插入排序的過程：

1.3 時間複雜度

時間複雜度

最好的情況是陣列所有元素已經是有序排列，在排序時待排元素只需與前一元素比較，不用繼續往前搜尋比較，時間複雜度為O(n)；

最差的情況是陣列所有元素全部反序，在排序時待排元素需要與前面所有有序元素進行比較，比較次數為：

1+2+…+(n-1) = n(n-1)/2

每次前面的有序元素均要往後移動，移動次數為：

（1+2)+(2+2)+…+(n-1+2) =(n-1)(n+4)/2

綜上所述，直接插入排序的平均時間複雜度為O( n 2 n^2 n2) 。

1.4 空間複雜度

直接插入排序為平行移動，因此空間複雜度為：O(1) 。

1.5 優缺點

優點：直接插入排序演演算法簡單，當待排序記錄數量n很小時，區域性有序時，較為適用。

缺點：當資料量龐大並且亂序嚴重時，比較和移動次數多，排序效率低。

2. 程式碼實現

2.1 程式碼設計

a. 實現直接插入排序需要設計兩層迴圈，整個陣列為外迴圈，已經排列好的有序元素為內迴圈；

b. 從外迴圈取出待排元素array[i]，使用臨時變數temp儲存其值；

c. 將待排元素與內迴圈的有序元素依次（從後往前）進行比較，若有序元素比待排元素大，則向後移動一位；

d. 直至有序元素比待排元素小，則不再移動，將temp賦值給array[j+1]。

2.2 程式碼實現

#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;
}

執行結果：

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語言直接插入排序演演算法介紹及範例的文章就介紹到這了,更多相關C語言直接插入排序內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！