排序算法---插入排序-----详解&&代码

简介: 排序算法---插入排序-----详解&&代码

插入排序:

插入排序的思路也很简单:假设前面已经有i节点是有序的,那么就从第i+1个节点开始,插入到前面的i个节点的合适的位置中。由于第一个元素自身总是有序的,因此从第2个开始,不断插入前面的有序序列,直到全部排列完毕。



假设总共有n个节点,那么总共需要将n−1个节点插入到有序序列中,而插入节点时需要找到合适的位置,显然这个查找的过程时间复杂度是O(n−i),因此插入排序的时间复杂度是O(n−1)(n−i),即O(n^2)。


原始数据(80,50,20,30,2,18,100)

第一次排序:(50,80,20,30,2,18,100)

第二次排序:(20,50,80,30,2,18,100)

第三次排序:(20,30,50,80,2,18,100)

第四次排序:(2,20,30,50,80,18,100)

第五次排序:(2,18,20,30,50,80,100)

代码:(第一种方法)

void Insertsort(int data[], int len)
{
    int i, j;
    int temp;
    //插入排序
    for (i = 1; i < len; i++)
    {
        temp = data[i]; //备份
        //循环比较插入到指定位置
        for (j = i; j > 0; j--)
        {
            if (data[j] < data[j - 1])
            {
                data[j] = data[j - 1];
                data[j - 1] = temp;
            }
            else
                break;
        }
    }
}

代码:(第二种方法)

//就是默认第一个是有序的,后边是无序的,把后边无序的每个数插入到前面有序中,有序的越来越多,无序的越来越少。
//先找到有序数列的位置,然后插进去再把后边的数后移
void Insertsort1(int data[], int len)
{
    //1.把无序的数找到在有序数列的位置
    //0~i-1是无序的,i~是有序的
    int i, j, k;
    int temp;
    for (i = 1; i < len; i++)
    {
        //i是无序数列中第一个数,遍历有序数列
        for (j = 0; j < i; j++)
        {
            //找到位置了,j就是要插入的位置下标
            if (data[i] < data[j])
            {
                //k = j;
                temp = data[i];
                //把j后边的数往后挪
                /*for (; j < len; j++)
                    data[j+1] = data[j];*/
                for (k = i - 1; k >= j; k--) //a[j] ~ a[i-1]所有的元素往后挪动一位
                {
                    data[k + 1] = data[k];
                }
                data[j] = temp;
            }
        }
    }
}
相关文章
|
1天前
|
并行计算 算法 Python
Dantzig-Wolfe分解算法解释与Python代码示例
Dantzig-Wolfe分解算法解释与Python代码示例
|
10天前
|
存储 算法 大数据
Python算法高手的必修课:深入理解分治法、贪心算法、动态规划,让你的代码更智能!
【7月更文挑战第9天】在Python算法学习中,分治法(如归并排序)将大问题分解为小部分递归解决;贪心算法(如货币找零)在每步选择局部最优解尝试达到全局最优;动态规划(如斐波那契数列)通过存储子问题解避免重复计算,解决重叠子问题。掌握这三种方法能提升代码效率,解决复杂问题。
|
17天前
|
算法 搜索推荐 C#
|
17天前
|
算法 PHP
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
【php经典算法】冒泡排序,冒泡排序原理,冒泡排序执行逻辑,执行过程,执行结果 代码
12 1
|
28天前
|
机器学习/深度学习 算法 搜索推荐
数据结构算法--2 冒泡排序,选择排序,插入排序
**基础排序算法包括冒泡排序、选择排序和插入排序。冒泡排序通过相邻元素比较交换,逐步将最大值“冒”到末尾,平均时间复杂度为O(n^2)。选择排序每次找到剩余部分的最小值与未排序部分的第一个元素交换,同样具有O(n^2)的时间复杂度。插入排序则类似玩牌,将新元素插入到已排序部分的正确位置,也是O(n^2)复杂度。这些算法适用于小规模或部分有序的数据。**
|
22天前
|
人工智能 搜索推荐 JavaScript
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
心得经验总结:排序算法:插入排序法(直接插入法和希尔排序法)
13 0
|
24天前
|
人工智能 算法 Java
java中经典算法代码整理
java中经典算法代码整理
22 0
|
24天前
|
机器学习/深度学习 搜索推荐 算法
【C/排序算法】:直接插入排序和希尔排序
【C/排序算法】:直接插入排序和希尔排序
13 0
|
25天前
|
算法 IDE 开发工具
c语言的经典算法代码
c语言进阶11-经典算法代码