「前言」文章内容是排序算法之直接插入排序的讲解。(所有文章已经分类好,放心食用)
「归属专栏」排序算法
「主页链接」个人主页
「笔者」枫叶先生(fy)
目录
- 一、排序概念的介绍
- 二、直接插入排序
- 2.1 原理
- 2.2 代码实现(C/C++)
- 2.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]有序,把end+1位置的值插入,保持有序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(vector<int>& arr)
{int n = arr.size();for (int i = 0; i < n - 1; ++i) // 达到n-1时,数组已经有序,无需再遍历最后一次,避免多余的循环{// [0, end]有序,把end+1位置的值插入,保持有序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
「 声明 」 余之才疏学浅,故所撰文疏漏难免,或有谬误或不准确之处,敬请读者批评指正。