插入排序（C语言版）


前言

插入排序(insertion sort)的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排序好的序列中，直到全部记录插入完成为止.

直接插入排序

基本思想

假设待排序的记录存放在数组R[1..n]中。初始时，R[1]自成1个有序区，无序区为R[2..n].从i = 2起直到i = n 为止，依次将R[i]插入当前的有序区R[1..i - 1]中，生成含n个记录的有序区.

排序方法

将待插入记录R[i]的关键字从右向左依次与有序区中记录R[j](j=i - 1, i - 2, ....,1)的关键字比较：

  1. 若R[j]的关键字大于R[i]的关键字，则将R[j]后移一个位置
  2. 若R[j]的关键字小于或等于R[i]的关键字，则查找过程结束，j + 1即为R[i]插入位置

关键字比R[i]的关键字大的记录均已后移，所以j + 1的位置已经腾空，只要将R[i]直接插入到此位置即可完成一趟直接插入排序

c语言实现代码

#include <stdio.h>
#include <stdlib.h>

void insertSort(int *, int);

int main()
{
 int i, n;
 int num[10];

 while(scanf("%d", &n) != EOF)
 {
  //接收无序数据
  for(i = 0; i < n; i ++)
  {
   scanf("%d",num + i);
  }

  //快速排序
  insertSort(num, n);

  //打印输出
  for(i = 0; i < n; i ++)
  {
   printf("%d ",num[i]);
  }
  printf("\n");
 }
 return 0;
}

void insertSort(int *array, int len)
{
 int i, j, temp;

 for(i = 1; i < len; i ++)
 {
  temp = array[i];
  for(j = i - 1; j >= 0; j --)
  {
   if(array[j] > temp)
   {
    array[j + 1] = array[j]; 
   }else
   {
    break;
   }
  }
  array[j + 1] = temp;
 }
}

时间复杂度
当数组和要求排序的顺序相同时，为o(n)
当数组和要求排序的顺序相反时，为o(n * n)
平均时间复杂度为o(n * n)

相关内容