直接插入排序

如下，以C中數(shù)組為例來(lái)展示該算法。在insertSort函數(shù)中對(duì)待排序數(shù)組從第二位數(shù)開(kāi)始進(jìn)行比較（均與前一位進(jìn)行比較），在內(nèi)循環(huán)中選定該次循環(huán)待排序數(shù)的位置并放置，直接插入是穩(wěn)定的排序方法。
直接插入排序算法的時(shí)間復(fù)雜度為o(n2)，空間復(fù)雜度為1。
直接插入排序并不能保證每一次使得待排序數(shù)處于其最終位置（這是快排的特點(diǎn)）。將insertSort函數(shù)看為內(nèi)外兩個(gè)循環(huán)，外循環(huán)每次選一個(gè)新的待排序數(shù)，而內(nèi)循環(huán)將此待排序數(shù)及其之前所有數(shù)變?yōu)橛行虻摹Ｃ看螆?zhí)行一個(gè)外循環(huán)，有序數(shù)的個(gè)數(shù)加一，從而有序數(shù)越來(lái)越多，直至最終有序，排序結(jié)束。
內(nèi)循環(huán)的實(shí)現(xiàn)是這個(gè)排序的重點(diǎn)。
排序函數(shù)insertSort的參數(shù)為一個(gè)c數(shù)組及數(shù)組長(zhǎng)度。從而將原來(lái)的數(shù)組進(jìn)行升序排序。算法實(shí)現(xiàn)如下：

#include<iostream> void insertSort(int* arr,int num); int main() {int a[10] = { 3, 2, 4, 6, 7, 5, 18, 9, 0, 1 };for (int i = 0; i < 10; i++){std::cout << a[i] << " ";}std::cout << '\n';insertSort(a, 10);for (int i = 0; i < 10;i++){std::cout << a[i] << " ";}return 0; } //上面的么得啥用。。。void insertSort(int* arr, int num) {int temp,i,j;//temp保存每一次的新數(shù)，因?yàn)閿?shù)組元素的移動(dòng)會(huì)覆蓋掉新數(shù)for (i = 1; i<num; ++i)//所謂外循環(huán)，每次放一個(gè)新數(shù)進(jìn)去參與排序{if (arr[i]<arr[i-1])//若下標(biāo)i以前的數(shù)不是有序的，執(zhí)行if語(yǔ)句內(nèi)容//此時(shí)的無(wú)序指的是下標(biāo)0~i-1是有序的，需要將下標(biāo)i中的數(shù)重新插入，使其變得有序{temp = arr[i];//保存每次的新數(shù)for (j=i-1; temp<arr[j]&&j>=0;--j)arr[j+1] = arr[j];arr[j+1] = temp;//在合適的位置上插入新數(shù)}} }

穩(wěn)定降序算法如下：

void insertSort(int* arr, int num) {int temp,i,j;for (i = 1; i<num; ++i){if (arr[i]>arr[i-1]){temp = arr[i];for (j=i-1; temp>arr[j]&&j>=0;--j)arr[j+1] = arr[j];arr[j+1] = temp;}} }

總結(jié)

以上是生活随笔為你收集整理的插入排序之——直接插入排序（c/c++）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。