江阴网站制作,2023年最新新闻简短摘抄,做乒乓球网站的图片,wap手机网站「前言」文章内容是排序算法之直接插入排序的讲解。#xff08;所有文章已经分类好#xff0c;放心食用#xff09; 「归属专栏」排序算法 「主页链接」个人主页 「笔者」枫叶先生(fy) 目录 一、排序概念的介绍二、直接插入排序2.1 原理2.2 代码实现#xff08;C/C#xf… 「前言」文章内容是排序算法之直接插入排序的讲解。所有文章已经分类好放心食用 「归属专栏」排序算法 「主页链接」个人主页 「笔者」枫叶先生(fy) 目录 一、排序概念的介绍二、直接插入排序2.1 原理2.2 代码实现C/C2.3 特性总结 一、排序概念的介绍 排序的概念 排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的内部排序数据元素全部放在内存中的排序外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内存和外存之间移动数据的排序 常见的排序算法 二、直接插入排序
2.1 原理 直接插入排序是一种简单直观的排序算法它的基本思想是将一个元素插入到已经排好序的部分数组中从而使得数组保持有序。[基于数组顺序表的结构进行排序] 例如假设前n-1个元素已有序现将第n个元素插入到前面已经排好的序列中使得前n个元素有序。按照此法对所有元素进行插入直到整个序列有序
具体步骤如下
从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5
例如对数组[4, 2, 5, 1, 6, 3]进行排序使用直接插入排序如下升序 动图演示数据不和上面相同 时间、空间复杂度 时间复杂度最好情况下为O(N)此时待排序列为升序或者说接近升序时间复杂度最坏情况下为O(N^2)此时待排序列为逆序或者说接近逆序总的来说直接插入排序的时间复杂度为O(N^2)在原有的数组上操作空间复杂度为O(1)
2.2 代码实现C/C
C语言代码如下升序
// 直接插入排序
void InsertSort(int* arr, int n) // arr:需要排序的数组; n:数组的大小
{for (int i 0; i n-1; i) // 达到n-1时数组已经有序无需再遍历最后一次避免多余的循环{// [0, end]有序把end1位置的值插入保持有序int end i; // 记录有序序列的最后一个下标int tmp arr[end 1]; // 保存等待插入的值while (end 0) {if (arr[end] tmp) // arr[end]比要插入的数大向后移动{arr[end 1] arr[end]; // 向后移进行覆盖tmp已经保存被覆盖的值--end; // 迭代}else // arr[end]比要插入的数小已有序跳出循环{break;}}arr[end 1] tmp; // 进行插入}
}C代码升序
// 直接插入排序
void InsertSort(vectorint arr)
{int n arr.size();for (int i 0; i n - 1; i) // 达到n-1时数组已经有序无需再遍历最后一次避免多余的循环{// [0, end]有序把end1位置的值插入保持有序int end i; // 记录有序序列的最后一个下标int tmp arr[end 1]; // 保存等待插入的值while (end 0){if (arr[end] tmp) // arr[end]比要插入的数大向后移动{arr[end 1] arr[end]; // 向后移进行覆盖tmp已经保存被覆盖的值--end; // 迭代}else // arr[end]比要插入的数小已有序跳出循环{break;}}arr[end 1] tmp; // 进行插入}
}2.3 特性总结 直接插入排序的特性总结 元素集合越接近有序直接插入排序算法的时间效率越高时间复杂度O(N^2)空间复杂度O(1)它是一种稳定的排序算法稳定性稳定
--------------------- END ----------------------
「 作者 」 枫叶先生
「 更新 」 2024.1.9
「 声明 」 余之才疏学浅故所撰文疏漏难免或有谬误或不准确之处敬请读者批评指正。
