插入排序算法(Insertion_Sort)

插入排序算法(Insertion_Sort)

一. 介绍

插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 [1] 。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 。

中文名:插入排序

外文名: Insertion sort

别 称: 直接插入排序

分 类: 排序方法

时间复杂度: O(N^(1-2))

空间复杂度: O(1)

稳定性: 稳定

二. 逻辑

在一组无序的数组arr[]中,将索引为1的的元素arr[1]和索引为0的元素arr[0]进行比较,if( arr[1] < arr[0] )则将arr[1]和arr[0]的位置互换,如果arr[1]>arr[0], 则寻找索引为2的元素arr[2]和arr[1]进行比较,if(arr[2] < arr[1] ) 则将arr[1]和arr[2]的位置互换,再进一步将arr[2]和arr[0]比较,if(arr[2] < arr[0]) 则这两个元素进行位置的互换;如果arr[2] > arr[1] 则寻找到下一个元素,以此类推……

例如:

​ 数组{3, 5, 2, 1, 6, 4, 7}, 此时数组是无序的

1.以索引为1的数开始 (数组第二个元素,因为第一个数已经排序在了第一个位置)
arr[0] = 3, arr[1] = 5, arr[2] = 2, arr[3] = 1, arr[4] = 6, arr[5] = 4, arr[6] = 7
这里 5 > 3,所以得到数组仍然是{3, 5, 2, 1, 6, 4, 7}
2.再将索引加1,此时就是2和5比,因为2 < 5,所以得到数组{3, 2, 5, 1, 6, 4, 7}
然后再将2和3进行比较,因为2 < 3, 所以得到数组{2, 3, 5, 1, 6, 4, 7}
3.以此类推………就可以得到有序数组{1, 2, 3, 4, 5, 6, 7}

三. 代码

这里我使用的是用C++实现

#include<iostream>

using namespace std;

//使用模板函数
template <typename T>
void InsertionSort(T arr[], int n){
    //第一个元素已经排在第一个位置,这里从索引为1开始
    for(int i = 1; i < n; i++){

        for(int j = i; j > 0; j--){
            if(arr[j] < arr[j-1])
                //swap来自c++标准库
                swap(arr[j], arr[j-1]);
            else
                break;
        }
    }

}
//测试InsertionSort
int main(){
    int q[10] = {2, 4, 1, 2, 6, 4, 2, 1, 1, 6};
    //InsertionSort函数的调用
    InsertionSort(q, 10);
    for(int i = 0; i < 10; i++)
        cout<<q[i]<<endl;
    return 0;
}



输出结果为:

1
1
1
2
2
2
4
4
6
6

上述使用的是传统的模式,明显存在一些问题,问题来自于swap函数,使用swap函数需要进行3次赋值操作,所以会降低插入排序的效率

下面我们进行优化我们的优化版本不使用swap函数,而是直接使用赋值操作

代码如下:

#include<iostream>

using namespace std;

//使用模板函数
template <typename T>
void InsertionSort(T arr[], int n){
    //第一个元素已经排在第一个位置,这里从索引为1开始
    for(int i = 1; i < n; i++){
        //将arr[i]的值赋值给e
        int e = arr[i];
        int j; 
        // j保存元素e应该插入的位置
        for (j = i; j > 0 && arr[j-1] > e; j--)
            arr[j] = arr[j-1];
        arr[j] = e;
    }
return;
}
//测试InsertionSort
int main(){
    int q[10] = {2, 4, 1, 2, 6, 4, 2, 1, 1, 6};
    //InsertionSort函数的调用
    InsertionSort(q, 10);
    for(int i = 0; i < 10; i++)
        cout<<q[i]<<endl;
    return 0;

}

输出结果为:

1
1
1
2
2
2
4
4
6
6
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!