首页 > 代码库 > c++ 插入排序算法

c++ 插入排序算法

第一、算法描述

      直插排序很容易理解,在我们打扑克牌的时候,每一次摸完牌,都会按数字大小或者花色,插入到合适的位置,直到摸完最后一张牌,我们手中的牌已经按大小顺序排列好了。这整个过程就是一个插入排序

下面举个例子,初始数组 {12, 15, 9, 20, 6, 31, 24}

我们把第一个元素12作为已经排序号的数组,用中括号括起来,方便我们观察

那么初始数组:[12], 15, 9, 20, 6, 31, 24

第一步,拿着15和12比较,发现15大于12,把15插入到12后面,于是当前数组变成

     数组结果:[12, 15 ], 9, 20, 6, 31, 24

第二步,拿着9和15比较,发现15>9,把15向后面移动一位,在把9和12比较发现12>9,把12向后移动一位,最后把9插入

     数组结果:[9,12, 15 ],  20, 6, 31, 24

第三步,拿着20和15比较,发现15<20,不需要调整

     数组结果:[9,12, 15 ,20], 6, 31, 24

如此执行下去,直到所有排序完成,

技术分享

上面一张图能完美的展示整个排序过程 ,其中虚线代表while中循环执行的,看下面算法实现

 

第二、算法实现

#include "stdafx.h"#include<iostream>using namespace std;void InsertSort(int a[], int n){	for (int j = 1; j < n; j++)	{		int key = a[j]; //待排序第一个元素		int i = j - 1;  //代表已经排过序的元素最后一个索引数		while (i >= 0 && key < a[i])		{			//从后向前逐个比较已经排序过数组,如果比它小,则把后者用前者代替,			//其实说白了就是数组逐个后移动一位,为找到合适的位置时候便于Key的插入			a[i + 1] = a[i];			i--;		}		a[i + 1] = key;//找到合适的位置了,赋值,在i索引的后面设置key值。	}}void main() {	int d[] = { 12, 15, 9, 20, 6, 31, 24 };	cout << "输入数组  { 12, 15, 9, 20, 6, 31, 24 } " << endl;	InsertSort(d,7);	cout << "排序后结果:";	for (int i = 0; i < 7; i++)	{		cout << d[i]<<" ";	}}

  

 

第三、测试实现

技术分享

希望我的文章对你能有所帮助。如果喜欢帮我点个推荐,谢谢~  

c++ 插入排序算法