C语言深入浅出讲解直接插入排序算法的实现

目录
  • 直接插入排序
    • 1.基本思想
    • 2.算法实现
    • 3.时间复杂度

插入排序分为两种：直接插入排序&希尔排序

直接插入排序

1.基本思想

直接插入排序是一种简单的插入排序算法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

说得通俗一点就是：

假设区间[0, end]有序，将end+1位置的值插入到[0, end]中，保持区间[0, end+1]依旧有序。

生活中我们玩扑克牌时，就用了插入排序的思想。

在这里，我们以排升序为例。

核心思想：摸牌的过程

动图演示：

2.算法实现

写排序时，先从单趟开始考虑

//[0, end]已经有序，将end+1位置的值插入到[0,end]中，使得[0,end+1]依旧保持有序
//有一个有序区间，插入一个数据，依旧保持有序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	//控制摸牌的过程，一开始从仅一张开始
	//注意循环结束条件，只需要到n-2的位置，若将其改成i<n，则会出现越界的情况
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)//保证牌是有序的
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];//往后挪，注意画图感受哦
				end--;
			}
			else
			//有两种可能：（现想常规的，再考虑特殊情况）
			//一是找到了比它小的数，放到其后；
			//二是没有比它小的数，直到end为-1才结束
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

完整代码：

3.时间复杂度

直接插入排序时间复杂度是O(N^2)，注意哦，不是因为双重循环，需要实际计算来得出时间复杂度。

最坏情况：逆序有序，1+2+3+……+n - 1；O(N^2)

最好情况：顺序有序，1+1+1+……+1。O(N)

到此这篇关于C语言深入浅出讲解直接插入排序算法的实现的文章就介绍到这了,更多相关C语言直接插入排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言实现选择排序、直接插入排序、冒泡排序的示例

    选择排序 选择排序是一种简单直观的排序算法,其核心思想是:遍历数组,从未排序的序列中找到最小元素,将其放到已排序序列的末尾. 时间复杂度:O(n^2) 稳定性 :不稳定 /* * @brief selection sort */ void selection_sort(int a[], int n) { int i, j, min, tmp; for (i = 0; i < n - 1; ++i) { min = i; for (j = i+1; j < n; ++j) { if (a[j]

  • C语言直接插入排序算法介绍

    C语言直接插入排序算法介绍

    目录 前言 一.什么是直接插入排序 二.代码讲解 总结 前言 直接 插入排序 (Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表.. 废话不多说先看看代码 #define _CRT_SECURE_NO_WARNINGS 1 //直接插入排序法 #include <stdio.h> void Compare(int arr[], int len) { int i = 0; for (i =

  • C语言直接插入排序算法

    目录 1.算法模板 2.算法介绍 3.实例 总结 1.算法模板 void InsertSort(SqList *L) { int j; for (int i = 2; i <= L->length; i ++ ) { if (L->arr[i] < L->arr[i-1]) { L->arr[0] = L->arr[i]; // 设置哨兵 for (j = i - 1; L->arr[j] > L->arr[0]; j -- ) L->ar

  • C语言之直接插入排序算法的方法

    C语言之直接插入排序算法的方法

    目录 一.什么是直接插入排序 二.代码讲解 总结 直接 插入排序 (Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表.. 废话不多说先看看代码 #define _CRT_SECURE_NO_WARNINGS 1 //直接插入排序法 #include <stdio.h> void Compare(int arr[], int len) { int i = 0; for (i = 0; i

  • 简单了解C语言中直接插入排序与直接选择排序实现

    直接插入排序 基本思路: 1. 从a[0]开始,也就是从1个元素开始是有序的,a[1]~a[n-1]是无序的. 2. 从a[1]开始并入前面有序的数组,直到n-1. #include <stdio.h> #define N 5 void insertsort(int a[], int n); void swap(int *x, int *y); void insertsort(int a[], int n){ int i,j; for(i=1; i<n; i++){ for(j=i; j

  • C语言深入浅出讲解直接插入排序算法的实现

    C语言深入浅出讲解直接插入排序算法的实现

    目录 直接插入排序 1.基本思想 2.算法实现 3.时间复杂度 插入排序分为两种:直接插入排序&希尔排序 直接插入排序 1.基本思想 直接插入排序是一种简单的插入排序算法,其基本思想是: 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 . 说得通俗一点就是: 假设区间[0, end]有序,将end+1位置的值插入到[0, end]中,保持区间[0, end+1]依旧有序. 生活中我们玩扑克牌时,就用了插入排序的思想. 在这里,

  • C++深入浅出讲解希尔排序算法的实现

    C++深入浅出讲解希尔排序算法的实现

    目录 希尔排序 1.基本思想 预排序 2.算法实现 3.时间复杂度 插入排序分为两种:直接插入排序&希尔排序 希尔排序 1.基本思想 希尔排序是在直接插入排序基础上的优化,属于非常牛掰的一个排序. 核心思想: 先进行预排序,让数组接近有序: 直接插入排序 预排序 预排序步骤: 分组排,假设gap==3,间隔为gap的为一组,然后分别使用插入排序的思想对这gap组数据进行排序 多组间隔为gap的预排序,gap由大变小,gap越大,大的数可以越快的到后面,小的数可以越快得到前面,gap越大,预排完越

  • C语言深入浅出讲解顺序表的实现

    C语言深入浅出讲解顺序表的实现

    目录 1.线性表 2.顺序表 2.1 概念及结构 2.2 提供接口 2.3 接口实现 今天起开始编写数据结构中的各种数据结构及算法的实现,说到顺序表,我们首先得了解下线性表. 1.线性表 线性表(linear list)是n个具有相同特性的数据元素的有限序列. 线性表是一种在实际中广泛使用的数据结构,常见的线性表:顺序表.链表.栈.队列.字符串… 线性表在逻辑上是线性结构,也就说是连续的一条直线.但是在物理结构上并不一定是连续的,线性表在物理上存储时,通常以数组和链式结构的形式存储. 2.顺序表

  • C语言 深入浅出讲解指针的使用

    C语言 深入浅出讲解指针的使用

    目录 一.利用指针倒序字符串 二.题目实例 三.总结 一.利用指针倒序字符串 void _reversal(char* left, char* right) { while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } 通过上述代码不难看出,left与right分别代表一个字符数组的首端和尾端,通过中间变量 tmp进行首尾交换,left++中的left是char*类型,同

  • python插入排序算法的实现代码

    1.算法:设有一组关键字{ K 1 , K 2 ,-, K n }:排序开始就认为 K 1 是一个有序序列:让 K 2 插入上述表长为 1 的有序序列,使之成为一个表长为 2 的有序序列:然后让 K 3 插入上述表长为 2 的有序序列,使之成为一个表长为 3 的有序序列:依次类推,最后让 K n 插入上述表长为 n-1 的有序序列,得一个表长为 n 的有序序列. 2.python插入排序代码 复制代码 代码如下: def insertion_sort(list2):    for i in ra

  • C语言深入探究直接插入排序与希尔排序使用案例讲解

    C语言深入探究直接插入排序与希尔排序使用案例讲解

    目录 一.直接插入排序 1.1直接插入排序引入 1.2直接插入排序的核心思想与算法分析 1.3实例说明 1.4直接插入排序代码实现 1.5直接插入排序性能分析 二.希尔排序 2.1希尔排序引入 2.2希尔排序的核心思想与算法分析 2.3实例说明 2.4希尔排序代码实现 2.5希尔排序性能分析 一.直接插入排序 1.1直接插入排序引入 排序是我们生活中经常会面对的问题,以打扑克牌为例,你摸的手牌肯定是杂乱的,你一定会将小牌移动到大牌的左面,大牌移动到小牌的右面,这样顺序就算理好了.这里我们的理牌方

  • Java十大经典排序算法的实现图解

    Java十大经典排序算法的实现图解

    目录 前言 一.排序算法 1.排序算法概述(百度百科) 2.<数据结构与算法>中的排序算法 3.算法分析 二.十大经典排序算法(Java开发版) 1.冒泡排序 2.快速排序 3.基数排序 4.插入排序 5.选择排序 6.希尔排序 7.归并排序 8.计数排序 9.堆排序 10.桶排序 前言 本文章主要是讲解我个人在学习Java开发环境的排序算法时做的一些准备,以及个人的心得体会,汇集成本篇文章,作为自己对排序算法理解的总结与笔记. 内容主要是关于十大经典排序算法的简介.原理.动静态图解和源码实现

  • C++深入浅出讲解函数重载

    C++深入浅出讲解函数重载

    目录 前言 函数重载 1.1 函数重载的概念 1.2 函数重载的意义 1.3 名字修饰(name Mangling) 1.4 extern "C" 前言 自然语言中,一个词可以有多重含义,人们可以通过上下文来判断该词真实的含义,即该词被重载了. 比如:以前有一个笑话,国有两个体育项目大家根本不用看,也不用担心.一个是乒乓球,一个是男足.前者是“谁也赢不了!”,后者是“谁也赢不了!” 函数重载 1.1 函数重载的概念 函数重载: 它是函数的一种特殊情况,C++允许在同一作用域中同一作用域

  • Linux内核中红黑树算法的实现详解

    Linux内核中红黑树算法的实现详解

    一.简介 平衡二叉树(BalancedBinary Tree或Height-Balanced Tree) 又称AVL树.它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.若将二叉树上结点的平衡因子BF(BalanceFactor)定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1.0和1.(此段定义来自严蔚敏的<数据结构(C语言版)>) 红黑树 R-B Tree,全称是Red-B

  • java几种排序算法的实现及简单分析

    本文实例讲述了java几种排序算法的实现及简单分析.分享给大家供大家参考.具体如下: package test; public class first { /*普通的插入排序*/ public void insertSort(int[] list) { int i, j; list[0] = -999; //相当于设置一个监视哨兵,不用判断是否越界, //但要求数组从第二个数开始即i=1开始存储 for (i = 1; i < list.length; i++) { j = i; while (

随机推荐