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

2024-08-05 15:28:17

1. 直接插入排序介绍

1.1 定义

直接插入排序是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。

1.2 基本原理

每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。

第一趟比较前两个数，然后把第二个数按大小插入到有序表中；第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。

下面的动图非常清晰的诠释了直接插入排序的过程：

1.3 时间复杂度

时间复杂度

最好的情况是数组所有元素已经是有序排列，在排序时待排元素只需与前一元素比较，不用继续往前搜索比较，时间复杂度为O(n)；

最差的情况是数组所有元素全部反序，在排序时待排元素需要与前面所有有序元素进行比较，比较次数为：

1+2+…+(n-1) = n(n-1)/2

每次前面的有序元素均要往后移动，移动次数为：

（1+2)+(2+2)+…+(n-1+2) =(n-1)(n+4)/2

综上所述，直接插入排序的平均时间复杂度为O( n 2 n^2 n2) 。

1.4 空间复杂度

直接插入排序为平行移动，因此空间复杂度为：O(1) 。

1.5 优缺点

优点：直接插入排序算法简单，当待排序记录数量n很小时，局部有序时，较为适用。

缺点：当数据量庞大并且乱序严重时，比较和移动次数多，排序效率低。

2. 代码实现

2.1 代码设计

a. 实现直接插入排序需要设计两层循环，整个数组为外循环，已经排列好的有序元素为内循环；

b. 从外循环取出待排元素array[i]，使用临时变量temp存储其值；

c. 将待排元素与内循环的有序元素依次（从后往前）进行比较，若有序元素比待排元素大，则向后移动一位；

d. 直至有序元素比待排元素小，则不再移动，将temp赋值给array[j+1]。

2.2 代码实现

#include <stdio.h>
void printArray(int array[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}
void insertSort(int array[], int size) {
    int temp,i,j;
    for (i = 1; i < size; i++) {
        temp = array[i];
        j = i-1;
        while (j >= 0 && array[j] > temp) {
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = temp;
        printArray(array, size);
    }
}
int main() {
    int array[] = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
    printArray(array, sizeof(array)/sizeof(int));
    insertSort(array, sizeof(array)/sizeof(int));
    return 0;
}

运行结果：

3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
3 44 38 5 47 15 36 26 27 2 46 4 19 50 48
3 38 44 5 47 15 36 26 27 2 46 4 19 50 48
3 5 38 44 47 15 36 26 27 2 46 4 19 50 48
3 5 38 44 47 15 36 26 27 2 46 4 19 50 48
3 5 15 38 44 47 36 26 27 2 46 4 19 50 48
3 5 15 36 38 44 47 26 27 2 46 4 19 50 48
3 5 15 26 36 38 44 47 27 2 46 4 19 50 48
3 5 15 26 27 36 38 44 47 2 46 4 19 50 48
2 3 5 15 26 27 36 38 44 47 46 4 19 50 48
2 3 5 15 26 27 36 38 44 46 47 4 19 50 48
2 3 4 5 15 26 27 36 38 44 46 47 19 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 50 48
2 3 4 5 15 19 26 27 36 38 44 46 47 48 50

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

C语言常见排序算法之插入排序(直接插入排序,希尔排序)

目录前言一.直接插入排序 1.1 基本思想 1.2 算法思想 1.3 程序实现 1.4 直接插入排序的总结二.希尔排序 2.1 算法思想 2.2 程序实现 2.3 希尔排序的特征总结前言本期为大家带来的是常见排序算法中的插入排序,主要有直接插入排序以及它的升级版——希尔排序,包您一看就会,快来试试吧~ 一.直接插入排序 1.1 基本思想在生活当中,这种排序方式处处可见: 在玩扑克牌的时候我们就会采用插入排序的思想,当我们拿起第二张牌时,就会下意识的与第一张牌进行比较,如果比第一张牌小
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语言深入浅出讲解直接插入排序算法的实现

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

目录一.什么是直接插入排序二.代码讲解总结直接插入排序 (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. 直接插入排序介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度 1.4 空间复杂度 1.5 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 直接插入排序介绍 1.1 定义直接插入排序是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表. 1.2 基本原理每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序. 第一趟比较前两个数,然后把第二个数按大小插入到有序表中: 第二趟把第三个
C语言顺序查找算法介绍及示例

目录 1. 顺序查找介绍 1.1 定义 1.2 基本原理 1.3 时间复杂度与空间复杂度 1.4 优缺点 2. 代码实现 2.1 代码设计 2.2 代码实现 1. 顺序查找介绍 1.1 定义查找是指在指定数据组合中找出满足条件的元素个体.顺序查找是按照序列原有顺序对数组进行遍历比较查询的基本查找算法. 顺序查找是最基础也是最简单的查找算法,在需要进行查找时,这是我们的首选方法,只有数据较多,结构复杂,耗时较多需要优化时,我们才会考虑使用其他查找方法. 1.2 基本原理对于任意一个序列以及一个
Java实现插入排序算法可视化的示例代码

参考文章图解Java中插入排序算法的原理与实现实现效果示例代码 import java.awt.*; public class AlgoVisualizer { private static int DELAY = 40; private InsertionSortData data; private AlgoFrame frame; public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){ // 初始化数据 data =
基于Go语言实现插入排序算法及优化

目录插入排序算法实现算法优化小结插入排序插入排序是一种简单的排序算法,以数组为例,我们可以把数组看成是多个数组组成.插入排序的基本思想是往前面已排好序的数组中插入一个元素,组成一个新的数组,此数组依然有序.光看文字可能不理解,让我们看看图示: 插入排序的时间复杂度为 O(N²). 算法实现 import ( "fmt" ) func main() { nums := [4]int{4, 1, 3, 2} fmt.Println("原数组:", nums)
C语言全排列回溯算法介绍

目录前言算法思想完整代码实验效果总结前言本博文源于最近学习的递归算法,递归中遇到一个问题全排列的问题,我看见回溯特别神奇,特此记录一下.对比一下深度优先搜索与广度优先搜索,个人感觉这里的回溯像是一种递归树中的深度优先搜索的算法,他不断构造往下延伸的深度,使其达到完全编列算法思想比如3拿来举例,按照一般正常的话就是应该, 123 132 213 231 312 321 六种,先造出一个hashtable数组让其存储在各位是否使用,然后创建path的p数组将数字进行选填,递归树我花
C语言实现冒泡排序算法的示例详解

目录 1. 问题描述 2. 问题分析 3. 算法设计动图演示 4. 程序设计设计一设计二结论 5. 流程框架 6. 代码实现 7. 问题拓展 1. 问题描述对N个整数(数据由键盘输入)进行升序排列. 2. 问题分析对于N个数因其类型相同,我们可利用数组进行存储. 冒泡排序是在两个相邻元素之间进行比较交换的过程将一个无序表变成有序表. 冒泡排序的思想:首先,从表头开始往后扫描数组,在扫描过程中逐对比较相邻两个元素的大小. 若相邻两个元素中,前面的元素大于后面的元素,则将它们互换,
Java语言Consistent Hash算法学习笔记（代码示例）

本文研究的主要是ConsistentHashing算法代码. 一致性哈希(Consistent Hash) 协议简介一致性哈希算法在1997年由麻省理工学院提出(参见0),设计目标是为了解决因特网中的热点(Hot pot)问题,初衷和CARP十分类似.一致性哈希修正了CARP使用的简单哈希算法带来的问题,使得DHT可以在P2P环境中真正得到应用. 哈希算法一致性哈希提出了在动态变化的Cache环境中,哈希算法应该满足的4个适应条件: 平衡性(Balance) 平衡性是指哈希的结果能够尽可能分
C语言编程题杨氏矩阵算法快速上手示例详解

目录题目概要一.解题思路二.具体代码题目概要有一个数字矩阵,矩阵的每行从左到右都是递增的,矩阵从上到下都是递增的,请编写程序在这样的矩阵中查找某个数字是否存在? 一.解题思路对于查找一个数组中元素是否存在,很多同学第一想法就是从头到尾遍历一遍.这样的想法优点是代码简单且无脑容易上手,但是这样的缺点也很明显,比如是m *n的数组,你从头到尾遍历,最坏情况要找m *n次.题目给的相关条件比如从左向右递增,从上向下递增你也完全没有使用,这样的暴力求解显然不是我们想看到的我们来介绍一种方法