插入类排序（直接插入排序，希尔排序）

一、直接插入排序

对于一个有序的序列，不断将后面的元素插入前面的有序序列，保持序列继续有序。

对于直接插入排序的思路：将要排序的元素保存，，然后逐个和其前面的元素进行比较，如果前面的元素比其大，则将前面的元素后移一个。

时间复杂度为n*n

void insert_sort(int a[],int n){ int i,j; int temp; for(i=1;i<n;i++) {temp = a[i]; j=i-1; while((j>=0)&& (temp<a[j])) {a[j+1] = a[j];j–; }a[j+1] = temp; }}

二、希尔排序

把整个序列分割成为若干个子序列，分别进行插入排序。待整个序列“基本有序”，再对全体序列进行排序。

#include <stdio.h>void shell_sort(int a[],int n){int i,j,k,temp; //选择间隔为每次都除以2，取整数for(i=n/2;i>0;i=i/2) //i为间隔{for(j=i;j<n;j++) {temp = a[j];for(k=j-i;(k>=0)&&(temp<a[k]);k=k-i){a[k+i] = a[k];}a[k+i] = temp; }}for(i=0;i<n;i++){ printf("%d,",a[i]);}}void main(){int a[] = {5,6,2,9,3,1,77,22,17};int n =9;shell_sort(a,n);}

版权声明：本文为博主原创文章，未经博主允许不得转载。

旁观者的姓名永远爬不到比赛的计分板上。