【数据结构周周练】031 直接插入排序算法原理详解及代码分享

深藏阁楼爱情的钟 2021-06-11 15:13 359阅读 0赞

## 一、直接插入排序 ##

### 1、直接插入排序简介 ###

直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。主要有下面三个步骤：

1.查找到L(i)所在数组中的位置，
    	2.将该位置以后的所有元素后移
    	3.将L(i)复制到该位置

这个算法原理是比较简单的，同时是一个稳定的算法。这个算法适用于顺序表和链表，其他很少能同时适用顺序表与链表的，希望大家能够掌握。

### 2、算法思想及流程 ###

排序时，从第二个数据开始，与其前一个判断，如果比前面的小，就需要前移。主要做如下几个步骤：

1.用中间变量暂存该数据。

2.将该数据与其前面数据依次做对比，直到找到或者到开头，每比较出现比该数据大的数据，将该数据后移。

3.将该数据存储在最后对比出来的位置。

## 二、全部代码 ##

刚才上面是分析，接下来我将所有的代码分享一下。

#include<iostream>
    using namespace std;
    
    /*
    	1.查找到L(i)所在数组中的位置，
    	2.将该位置以后的所有元素后移
    	3.将L(i)复制到该位置
    */
    void InsertSort(int Arr[],int length) {
    	int temp;
    	int i,j;
    	for (i = 1; i < length; i++)//找到每个元素所在位置
    	{
    		if (Arr[i] < Arr[i - 1])
    		{
    			temp = Arr[i];
    			for (j = i - 1; temp < Arr[j] && j >= 0; j--)//查找位置，并后移
    				Arr[j + 1] = Arr[j];
    			Arr[j + 1] = temp;//将数据复制到其位置
    		}
    	}
    }
    
    void OutputArr(int Arr[],int length) {
    	for (int i = 0; i < length; i++)
    	{
    		cout << Arr[i] << ", " ;
    
    	}
    	cout << endl;
    }
    
    void main() {
    	int Arr[] = { 45,57,12,31,1,60,92,71,87 };
    	InsertSort(Arr, 9);
    	OutputArr(Arr, 9);
    }

## 三、结果 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_22_color_1FFF2F_t_70][]

大家有什么问题在下面留言哦！！！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NodWl5aXhpbg_size_22_color_1FFF2F_t_70]: /images/20210516/74cb8884611543d3abe4400b486e2a72.png