本文共 2159 字，大约阅读时间需要 7 分钟。

C++ 插入排序 个人笔记

插入排序原理:

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，

找到相应位置并插入。插入排序在实现上，通常采用 in-place 排序（即只需用到 O(1)的额外空间

的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供

插入空间。

插入排序的步骤(文字描述)

//以从大到小的排列为例

1: 首先假设第一个元素就是一个数组(已排好序的数组)

2:用已排好序的数组的下一个元素,与已排好序的数组中的元素从后往前比较

3:如果已排好序中的元素大于已排好序的数组的下一个元素,已排好序中的元素移到下一个位置,上一个位置就可以被插入(覆盖)

4:重复步骤 3，直到找到已排序的元素小于或者等于已排好序的数组的下一个元素的位置；

5:将已排好序的数组的下一个元素插入这个位置

已排好序的数组长度加一

重复2-5步骤

插入排序的代码实现

第一个插入排序的版本

#include 
   
    #include 
    
     using namespace std;/********************************函数作用: 使用插入排序从小到大排列数据**函数参数: arr - int类型的数组首地址*          len - 数组的总元素个数**函数返回值: 无**************************************/void insertSort1(int* arr, int len) {	for (int i = 1; i < len; i++) {		int tmp = arr[i];//保存i下标中数据;		int index = i;		//index 需要插入的位置		for (int j = i-1; j >= 0; j--) {			if (arr[i] < arr[j]) {				index = j;			}		}		//使index 的位置空出来,可以被覆盖		for (int n = i; n > index; n--) {			arr[n] = arr[n - 1];		}		//用tmp数据覆盖index下标中的数据		if (index != i) {			arr[index] = tmp;		}	}}int main(void) {	int arr[] = { 100,2,3,87,80,54,98 };	int len = sizeof(arr) / sizeof(arr[0]);	insertSort1(arr,len);	for (int i = 0; i < len; i++) {		cout << arr[i] << setw(4);	}	return 0;}
    
   

第二个版本

#include 
   
    #include 
    
     using namespace std;/********************************函数作用: 使用插入排序从小到大排列数据**函数参数: arr - int类型的数组首地址*          len - 数组的总元素个数**函数返回值: 无**************************************/void insertSort2(int* arr, int len) {	//从下标为1的(数组第二个元素)开始遍历	for (int i = 1; i < len; i++) {		//i是已排序数组的下一个下标		int current = arr[i];//保存当前i下标中的数据 		int preindex = i - 1;//已排序的最后一个数组下标		//preindex 不小于零 且 		//prieindex 下标中的元素大于已排序数组的下一个下标中的元素		//进入循环		//第一次进入循环时preindex 是已排序的最后一个数组下标依次递减		while (preindex >= 0 && arr[preindex] > arr[i]) {			//空出preindex这个下标的位置,preindex 下标中的元素可以被覆盖			arr[preindex + 1] = arr[preindex];			//preindex			preindex--;		}		//这里的preindex下标经过了preindex--;所以加1;		//已排序数组的下一个下标中的元素覆盖preindex+1 下标中的元素		arr[preindex + 1] = current;	}}int main(void) {	int arr[] = { 100,2,3,87,80,54,98 };	int len = sizeof(arr) / sizeof(arr[0]);	insertSort2(arr,len);	for (int i = 0; i < len; i++) {		cout << arr[i] << setw(4);	}	return 0;}
    
   

代码测试

转载地址：http://wbyki.baihongyu.com/