首页 > 其他分享 >插入排序

插入排序

时间:2022-11-01 18:35:03浏览次数:55  
标签:nums int 插入排序 insertion 排序 复杂度

插入排序是基础简单,同时效率也不高的排序

void insertion_sort(vector<int>& nums) {
	int n = nums.size();
	// 把第一个当作是有序序列,从第二个开始操作
	for (int i = 1; i < n; i++) {
		int j = i;
		while (j>0&&nums[j] < nums[j - 1]) {
			swap(nums[j], nums[j - 1]);
			j--;
		}
	}
}

int main() {
	vector<int> nums = { 2,8,1,5,3,9,6 };
	insertion_sort(nums);
	for (int i : nums) cout << i << " ";
	return 0;
}

随手写一个,可以看出其实还是基于比较并交换的排序
最坏时间复杂度应该是在O(N^2^)级别,最好是一次遍历无需交换,原地排序空间复杂度O(1)

标签:nums,int,插入排序,insertion,排序,复杂度
From: https://www.cnblogs.com/yaocy/p/16848740.html

相关文章

  • js-基础排序实现(冒泡排序,快速排序,选择排序,插入排序,希尔排序,归并排序,堆排序)
    冒泡排序:两个指针循环,遇到不合适就交换,直到将符合要求的浮到边界functionbubbleSort(list){ for(leti=0;i<list.length;i++){ for(letj=0;j<list.length-i-1;j++)......
  • 插入排序
    packageclass01;importjava.util.Arrays;/***插入排序*概述:先将i指向第二个数(索引为1),将j指向i-1位置,如果j大于等于0,并且arr[j]>arr[j+1],将将arr[j]和arr[j+......
  • 插入排序
    插入排序一、概念及其介绍插入排序(InsertionSort),一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是......
  • java插入排序
    如何才能插入排序描?如何才能插入排序描述思路假定这个数组的序是排好的,然后从头往后,如果有数比当前外层元素的值大,则将这个数的位置往后挪,直到当前外层元素的值大于或等于它......
  • 数据结构【c语言版】八大算法(上)图文详解带你快速掌握——希尔排序,堆排序,插入排序,选择
    数据结构之八大算法详解(1)——希尔排序,堆排序,插入排序,选择排序,冒泡排序!插入排序基本思想把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所......
  • C#:插入排序
    对于给定的一组记录,初始时假设第一个记录自成一个有序序列,其余的记录为无序序列。接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直至......
  • 3、插入排序-Go语言版
    前情提示Go语言学习者,文章若有不妥之处,感谢指正。本文参考:https://www.runoob.com/w3cnote/ten-sorting-algorithm.html为了便于下载和整理,已开源放在:https://github......
  • 插入排序
    插入排序的原理:将指针指向某元素(一般从第二个元素开始),假设该元素的左侧全部有序,将该元素抽取,然后按照从右往左的顺序分别与其左边的元素进行比较,遇到较大的元素便将较大的......
  • JavaScript 实现 -- 插入排序
    前言本文主要记录了JavaScript实现--插入排序,以及原理、时间复杂度、空间复杂度和算法稳定性。插入排序插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一......
  • 插入排序算法步骤和思路
    算法步骤将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置......