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)，由于元素之间是逐个进行比较的，直接插入排序是一种稳定的排序算法。
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语言插入排序内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网！
