数据结构与算法(排序)——直接插入排序
直接插入排序是一种最简单的排序算法,因此又称简单插入排序
思想:第i趟排序将序列中的第i+1个元素 k(i+1)插入到一个已经生成的子序列中合适的位置,使得插入的序列仍然保持有序。(不理解的就想打扑克牌时候手中码牌的顺序和方法)
例子:{3,6,4, 2,11,10,6}
实例代码:实现{2,5,6,3,7,8,0,9,12,1}的直接插入排序,要求从大到小排序
#include<stdio.h>
/*
*直接插入排序算法
*a[0]作为每次带插入元素k[i]的空间,也就相当于临时变量tmp
*/
void insertsort(int a[], int n)
{
int i, j;
for(i = 2; i <= n; i++)
{
a[0] = a[i];
j = i - 1;
while(j >0 && a[0] > a[j]) //找到插入位置,实现从大到小的排序
a[j+1] = a[j--];
a[j+1] = a[0]; //元素a[0]插入到指定位置 ,i-1趟完成
}
}
int main()
{
//a[0]可以任意置数
int i, a[11] = {-1, 2, 5, 6, 3, 7, 8, 0, 9, 12, 1};
printf("排序前:\n");
for(i = 1; i <= 10; i++)
{
printf("%d ", a[i]);
}
insertsort(a, 10);
printf("\n排序后:\n");
for(i = 1; i <= 10; i++)
{
printf("%d ", a[i]);
}
return 0;
}