首页 > 代码库 > 【Algorithm】插入排序

【Algorithm】插入排序

一. 算法描述

  插入排序具体算法描述如下:

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

  举个例子:5 7 6 4 3 8

  第一趟:5 7 6 4 3 8  =》5 7 6 4 3 8

  第二趟:5 7 6 4 3 8  =》5 6 7 4 3 8

  第三趟:5 6 7 4 3 8  =》4 5 6 7 3 8

  第四趟:4 5 6 7 3 8  =》3 4 5 6 7 8

  第五趟:3 4 5 6 7 8  =》3 4 5 6 7 8

三. 算法实现

  算法实现1

/** author:Knife* time:2014.06.13 16:07* Algorithm:插入排序(从前向后查找)*/#include<stdio.h>void main_insertSort(){    int intArr[] = {8,3,6,4,2,9,5,4,1,7};    int n = sizeof(intArr)/sizeof(intArr[0]); // 计算整型数组的长度    int i,j,k,tmp;    for(i = 1; i < n; i++){        for( j = 0; j < i; j++){            if(intArr[i] < intArr[j]){ // 插入位置j                tmp = intArr[i];                for(k = i; k>j; k--){                    intArr[k] = intArr[k-1];                }                intArr[j] = tmp; // 插入            }        }    }    // 打印输出    for(i=0; i<n; i++){        printf("%d ",intArr[i]);    }    printf("\n");}

  算法实现2

/** author:Knife* time:2014.06.13 16:07* Algorithm:插入排序(从后向前查找)*/#include<stdio.h>void main_1(){    int intArr[] = {8,3,6,4,2,9,5,4,1,7};    int n = sizeof(intArr)/sizeof(intArr[0]); // 计算整型数组的长度    int i,j,tmp;    //插入排序    for(i = 1; i < n; i++){        tmp = intArr[i];        j = i-1;        while(j>=0 && (tmp < intArr[j])){ // 插入位置            intArr[j+1] = intArr[j];            j--;        }        intArr[j+1] = tmp; // 插入操作    }    // 打印输出    for(i=0; i<n; i++){        printf("%d ",intArr[i]);    }    printf("\n");}

  算法实现3

#include<stdio.h>/** author:Knife* time:2014.06.13 16:43* Algorithm:插入排序(二分查找)*/void main(){    int intArr[] = {8,3,6,4,2,9,5,4,1,7};    int n = sizeof(intArr)/sizeof(intArr[0]); // 计算整型数组的长度    int i,j,low,high,mid,temp;    for(i = 1; i < n; ++i){        low = 0;        high = i-1;        while(low <= high){  //使用二分查找,寻找插入的位置             mid = low + ((high-low) >> 1);    //这种写法,有效避免溢出            if(intArr[i] > intArr[mid]){                low = mid + 1;            }else{                high = mid - 1;            }        }                temp = intArr[i];        for(j = i; j > low; j--){  //移动元素             intArr[j] = intArr[j-1];        }        intArr[low] = temp;  //在合适位置,插入。这里为什么是 low? 得仔细想想(答案在这里http://blog.csdn.net/zhangxiangdavaid/article/details/27373183)!     }    // 打印输出    for(i = 0; i < n; i++){        printf("%d ",intArr[i]);    }    printf("\n");}

四. 算法分析

  • 平均时间复杂度:O(n^2)
  • 空间复杂度:O(1)  (用于记录需要插入的数据)
  • 稳定性:稳定

参考资料

[1] http://blog.csdn.net/zhangxiangdavaid/article/details/27373183

[2] http://blog.csdn.net/cjf_iceking/article/details/7916194