首页 > 编程语言 > 详细

插入排序

时间:2020-03-19 00:51:48      阅读:68      评论:0      收藏:0      [点我收藏+]

插入排序的基本思想是:将数组的第一个数认为是有序数组,从后往前(从前往后)扫描该有序数组,把数组中其余n-1个数,根据数值的大小,插入到有序数组中,直至数组中的所有数有序排列为止。这样的话,n个元素需要进行n-1趟排序!!!

举个例子:4个数字4,6,7,5进行从大到小的排序。前插排序法具体过程如下:
把第一个数4插入到空的有序数组中的第一个位置上,得到新数字序列4;

第一趟:从后往前扫描有序数组,将第二个数字6和有序数组中的4进行比较,6大于4,此时将4后移一个位置。此时已经扫描完有序数组中的数,将6插入到4的前面(有序数组的第一个位置),得到新数字序列6,4;

第二趟:从后往前扫描有序数组,先将第三个数字7和有序数组中的4进行比较,7大于4,此时将4后移一个位置;再将7和有序数组中的6进行比较,7大于6,此时将6后移一个位置。此时已经扫描完有序数组中的数,将7插入到6的前面(有序数组的第一个位置),得到新数字序列7,6,4;

第三趟:从后往前扫描有序数组,先将第四个数字5和有序数组中的4进行比较,5大于4,此时将4后移一个位置;再将5和有序数组中的6进行比较,5小于6,由于有序数组就按照从大到小排列的,此时直接把5插入到4的前面即可!不需要再和7进行比较!最后,得到新数字序列7,6,5,4;

上代码!!!

#include<iostream>
    #include<cstdio>
    using namespace std;
    #define N 5
    int a[N];//有序数组
    int main ( ) {
    	int i, k, x;
    	printf("Please input %d numbers:\n",N);   
    	for (i=0; i<N; i++) {
    		scanf ("%d", &x);
    		for ( k=i; k>0; k-- ) {	        /* 从后向前比较 */
    			if ( a[k-1] > x )    //x前面的数比它大
    				a[k]=a[k-1];         /* 将大数向后移动*/
    			else      break; /* 找到插入的位置,退出 */
    		}
    		a[k] = x;  /* 完成插入操作 */
    	}
    
    	for (i=0; i<N; i++)
    		printf("%d ", a[i]);
    	return 0;
    }

  

插入排序

原文:https://www.cnblogs.com/swithun333/p/12520942.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!