排序之直接插入排序

1 .原理：将排列的数组分成有序和无序2个部分，一般以第一个元素作为有序的部分，然后将无序部分（也就是第二元素开始到数据尾部为无序部分）的第一个元素开始和有序部分从后往前比较排序，然后将无序数据逐个插入到有序数据中

2 .直接插入排序为稳定排序，基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增加1的有序表。时间复杂度为O（n*n），辅助空间为O（1）

3.排序演示

4.java实现方式

public class StraightInsertionSort {

/**
 * 辅助函数:输出数组内容
 * 
 * @param a：待输出数组
 */
public static void printArray(int[] a) {
for (int index = 0; index < a.length; index++) {
System.out.print(a[index] + " ");
}
System.out.println("");
}

/**
 * 直接插入排序 实现1
 * 
 * @param a：待排序数组
 */
public static void insertSort(int[] a) {
// 输出原始数组
printArray(a);
for (int index = 1; index < a.length; index++) {

int subIndex = index;

// 等待插入的数据
int currentData = a[index];

while ((subIndex > 0) && (a[subIndex - 1] > currentData)) {
a[subIndex] = a[subIndex - 1];
subIndex--;
}

// 插入到合适的位置
a[subIndex] = currentData;

// 每次排序后也输出
printArray(a);
}
}

/**
 * 直接插入排序 实现2
 * @param a：待排序数组
 */
public static void insertSort2(int[] a) {

int n = a.length;
int i, j;
for (i = 0; i < n; i++) {
int temp = a[i];
for (j = i; j > 0 && temp < a[j - 1]; j--) {
a[j] = a[j - 1];
}
a[j] = temp;

printArray(a);
}
}

public static void main(String[] args) {
//insertSort(new int[] { 8, 2, 4, 9, 3, 6, 7, 10 });
insertSort2(new int[] { 8, 2, 4, 9, 3, 6, 7, 10 });
}
}

5.C语言实现方式

#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
#define MAXSIZE 10
typedef struct 
{
 int length;
 int arr[MAXSIZE+2];
}list;

void insert(list* p)
{
 int i,j;
 for (i = 2; i <= p->length; i += 1)//第一个暂存，第二个数字是待比较的数字，从第三个开始比较起
  {
   p->arr[0] = p->arr[i];//数组的第一个数字用来暂存每次用来比较的arr[i]

     for (j = i-1; (p->arr[0] < p->arr[j]) && j!=0; j --)
     {
     p->arr[j+1] = p->arr[j];
     }
   p->arr[j+1] = p->arr[0];

  }
}
int main()
{
 int i;
 list *plist;
 plist = (list*)malloc(sizeof(list));//分配空间
 plist->length = MAXSIZE;
 plist->arr[MAXSIZE+2] = 0;//将最后一个数字置为0

 srand((unsigned int)time(NULL));//随机种子生成

 for (i = 1; i < MAXSIZE+1; i += 1)//数组的第一个数字用来暂存每次用来比较的arr[i]
  {
  plist->arr[i] = (rand() % 100);//生成10个100以内的随机数
  printf("array before:%d\n", plist->arr[i]);
  }

 insert(plist);

 printf("\n");

 for (i = 1; i < MAXSIZE+1; i += 1)
  {
  printf("array after:%d\n", plist->arr[i]);
  }
 return 0;