您当前的位置： 首页 > 慢生活 > 程序人生 网站首页程序人生

c语言实现插入排序算法

发布时间：2021-04-22 21:06:17编辑：雪饮阅读（）

 插入排序

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到 {\displaystyle O(1)} {\displaystyle O(1)}的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后
 
挪位，为最新元素提供插入空间。
过程演示：

其实这个图来自于菜鸟教程，这个图不够形象具体，也可以参考下面这个图

实例：
#include <stdio.h>
void main(){
    int arr[]={3,6,4,9,7,5,2};
    int len=7;
    int i,j,temp;
    for (i=1;i<len;i++){
            temp = arr[i];
            printf("sort %d: swap before:",i);
            for(int x=0;x<len;x++){
                if(x==len-1){
                    printf("%d",arr[x]);
                }
                else{
                    printf("%d,",arr[x]);
                }
            }
            printf("\n");  
            /*
            已排序的序列中从后向前扫描
            */
            printf("sort %d:former:",i);
            printf("\n"); 
            for (j=i;j>0 && arr[j-1]>temp;j--){
                printf("\tarr[j]=>arr[%d]:%d",j,arr[j]);
                printf(" arr[j-1]=>arr[%d]:%d",j-1,arr[j-1]);
                //把每个比temp大的都移动到temp这侧
                //比temp大的都后边去
                arr[j] = arr[j-1];
                //预判下一次是否循环执行
               
                if(j-1>0&&arr[j-1-1]>temp){
                    printf(",");
                }
               
            }
             printf("\n");
            // printf("swap:%d,%d",arr[j],temp);
             printf("sort %d:arr[j]=>arr[%d]=%d,swap,temp=arr[%d]=%d",i,j,arr[j],i,temp);
            
             printf("\n");
             //上面循环结束后最后一个不大于temp的地方（j-1）的右边就是temp应该放置的地方，所以temp最后要放置的地方就是j
            arr[j] = temp;
          
            printf("sort %d swap after:",i);
            for(int y=0;y<len;y++){
                if(y==len-1){
                    printf("%d",arr[y]);
                }
                else{
                    printf("%d,",arr[y]);
                }
            }
            printf("\n");  
            printf("\n");
            printf("\n");    
    }
}
 
/*
 
3，4，6，7，9，5，2
 
3，4，6，7，9，9，2
3，4，6，7，7，9，2
3，4，6，6，7，9，2
*/
/*
总结：
选择排序：
    每次向已排序里面默认最新索引为最小，然后从未排序里面挑选最小值，且比当前已排序最新索引对应值还小的就覆盖目前已排序的最新索引为未排序里面的这个最小值的索引，
    最后根据已排序里面最新索引是否被覆盖（与i相同），来判断是否需要交换
插入排序：
    每次遍历到一个新值，就和已排序数组里面进行比较，大于这个新值的都靠右边去，一直推到左边没有比这个新值大的索引位置（小于或等于），此时该索引位置向后加一个就是这个新值该存放的位置
    向后加一个位置进行存放的时候不会导致原来该位置的值被覆盖从而导致丢失，因为，这个新值原来的位置被新值索引位置减去一个单位的索引位置对应的值给覆盖了，所以是整体向右移动一个单位，
    所以这个新值最终存放的地址不会导致原来该位置的值丢失。
*/