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->arr[j + 1] = L->arr[j];
            L->arr[j + 1] = L->arr[0];
        }
    }
}

2.算法介绍

直接插入排序的基本思想是：对于一个长度为n的序列，从第2的元素开始，逐个向之前排好的序列中插入新元素（第1个元素可以视为一个长度为1的有序的子序列），从而得到一个长度为n的有序的序列。

算法的时间复杂度为O(n^2)，最好的情况为待排序列本身就是有序的，只需要遍历一遍，时间复杂度为O(n)，最坏的情况为逆序，时间复杂度为O(n*n)，由于元素之间是逐个进行比较的，直接插入排序是一种稳定的排序算法。

3.实例

#include <iostream>
using namespace std;

const int N = 100;

typedef struct
{
    int arr[N];
    int length;
} SqList;

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->arr[j + 1] = L->arr[j];
            L->arr[j + 1] = L->arr[0];
        }
    }
}

int main()
{
    SqList L;
    L.arr[1] = 50;
    L.arr[2] = 10;
    L.arr[3] = 90;
    L.arr[4] = 30;
    L.arr[5] = 70;
    L.arr[6] = 40;
    L.arr[7] = 80;
    L.arr[8] = 60;
    L.arr[9] = 20;
    L.length = 9;

    InsertSort(&L);
    for (int i = 1; i <= L.length; i ++ )
        cout << L.arr[i] << " ";

}

总结

到此这篇关于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语言排序算法之插入排序

    算法实现: 使用插入排序将下面的数字按照从小到大的顺序排列 步骤1:数组中已经排好的是{1},将9插入数组中 步骤2:数组中已经排好的是{2,9},将5插入数组中 步骤3:数组中已经排好的是{2,5,9},将4插入数组中 步骤4:数组中已经排好的是{2,4,,5,9},将8插入数组中 步骤5:数组中已经排好的是{2,4,,5,8,9},将1插入数组中 步骤6:数组中已经排好的是{1,2,4,,5,8,9},将6插入数组中 步骤7:排序完成 程序代码: #include <stdio.h> #i

  • C语言中快速排序和插入排序优化的实现

    C语言中快速排序和插入排序优化的实现

    快速排序 快速排序思想 1962年,由C.A.R.Hoare创造出来.该算法核心思想就一句话:"排序数组时,将数组分成两个小部分,然后对它们递归排序".然而采取什么样的策略将数组分成两个部分是关键,想想看,如果随便将数组A分成A1和A2两个小部分,即便分别将A1和A2排好序,那么A1和A2重新组合成A时仍然是无序的.所以,我们可以在数组中找一个值,称为key值,我们在把数组A分解为A1和A2前先对A做一些处理,让小于key值的元素都移到其左边,所有大于key值的元素都移到其右边.这样递

  • 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语言直接插入排序算法介绍

    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语言直接插入排序算法介绍及示例

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

  • 基于Go语言实现插入排序算法及优化

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

  • C语言基本排序算法之插入排序与直接选择排序实现方法

    本文实例讲述了C语言基本排序算法之插入排序与直接选择排序实现方法.分享给大家供大家参考,具体如下: 声明待排序元素类型 /*-------------------------- typedef.h 方便修改待排序元素类型 -------------------------------------*/ #ifndef TYPEDEF_H #define TYPEDEF_H typedef int T; #endif 插入排序: /*---------------------------------

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

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

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

  • 必须知道的C语言八大排序算法(收藏)

    必须知道的C语言八大排序算法(收藏)

    概述 排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存. 我们这里说说八大排序就是内部排序. 当n较大,则应采用时间复杂度为O(nlog2n)的排序方法:快速排序.堆排序或归并排序序. 快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短: 1.插入排序-直接插入排序(Straight Insertion Sort) 基本思想: 将一个记录插入到

  • 浅谈2路插入排序算法及其简单实现

    2路插入排序算法是在直接插入排序算法的基础上增加了一个辅助数组,其目的是减少排序过程中的移动次数,需要增加n个记录的辅助空间. 难点可能在于对取余的考虑吧,可以把辅助数组看成一个环状空间,这样就能更好的理解辅助空间中最大值和最小值的位置了. 算法整体思想还是很简单的,直接贴出可运行代码,注释还是挺清楚的,大家直接看就ok了 C语言实现示例 #include <stdio.h> #include <stdlib.h> void insert_sort(int *arr, int *t

  • C语言 八大排序算法的过程图解及实现代码

    C语言 八大排序算法的过程图解及实现代码

    目录 前言 一.插入排序 时间复杂度 空间复杂度 代码实现(升序) 二.希尔排序 时间复杂度 空间复杂度 代码实现 三.选择排序 时间复杂度 空间复杂度 代码实现 四.堆排序 时间复杂度 空间复杂度 代码实现 五.冒泡排序 时间复杂度 空间复杂度 代码实现 六.快排排序 时间复杂度 空间复杂度 代码实现 七.归并排序 时间复杂度 空间复杂度 代码实现 八.计数排序 时间复杂度 空间复杂度 九.各种排序总结比较 前言 排序是数据结构中很重要的一章,先介绍几个基本概念. 排序稳定性:多个具有相同的关

  • C语言数据结构与算法之排序总结(一)

    C语言数据结构与算法之排序总结(一)

    目录 一.前言 二.基本概念 1.排序 2.排序方法的稳定性 3.内部和外部排序 三.插入类排序 1.直接插入排序 2.折半插入排序 3.希尔排序 四.交换类排序 1.冒泡排序 2.快速排序 五.总结比较 一.前言 学习目标: 排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确 理解各种排序算法的定义和特点,并能将代码灵活运用 掌握各种排序方法时间复杂度与空间复杂度 理解排序稳定和不稳定的概念                 重点和难点: 希尔.快速.堆.归并排序这几种快

随机推荐