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

目录
  • 前言
  • 一、直接插入排序
    • 1.1 基本思想
    • 1.2 算法思想
    • 1.3 程序实现
    • 1.4 直接插入排序的总结
  • 二、希尔排序
    • 2.1 算法思想
    • 2.2 程序实现
    • 2.3 希尔排序的特征总结

前言

本期为大家带来的是常见排序算法中的插入排序，主要有直接插入排序以及它的升级版——希尔排序，包您一看就会，快来试试吧~

一、直接插入排序

1.1 基本思想

在生活当中，这种排序方式处处可见：

在玩扑克牌的时候我们就会采用插入排序的思想，当我们拿起第二张牌时，就会下意识的与第一张牌进行比较，如果比第一张牌小，我们则将牌插入至第一张牌的左边，反之就插入至右边（升序）。以图为例：我们拿起一张7，发现比最后一张牌10小，自然7与10就要交换位置，交换完成后，发现7前面的数字比自己小，就不用交换了，所以就找到7的位置了。

我们会发现，在拿起一张牌准备插入时，待插入的区间已经是有序的，我们要做的是，插入后使区间依旧有序。

1.2 算法思想

当插入第 i (i>=1)个元素时，前面的array[0],a[1]……a[i-1] 已经排序好，此时用a[i]的排序码与     a[i-1],a[i-2]……进行比较，找到插入位置，原来位置上的数据元素顺序往后移。

用一组实例来观察一下是算法是怎么实现的的：

1.3 程序实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

//打印数据
void Print(int* a,int  n)
{
	for (int i=0;i<n;++i)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}

//直接插入排序
void InsertSort(int *a, int n)//升序
{
	for (int i=0;i<n-1;++i)
	{
		int end = i;
		int tmp = a[end + 1];;
		while (end>=0)
		{
			if (a[end] > tmp)//修改此处符号即可升序降序切换
			{
				a[end+1] = a[end];
				--end;
			}
			else
			{
				break;
			}
			a[end + 1] =tmp;
		}
	}
	//打印数据
	Print(a,n);
}

int main()
{
	int a[6] = { 5,2,4,6,1,3 };
	//直接插入排序
	InsertSort(a,sizeof(a)/sizeof(a[0]));
	return 0;
}

1.4 直接插入排序的总结

  • 1.元素集合越接近有序，直接插入排序算法时间效率越高
  • 2.时间复杂度：O(N^2)(最坏情况) ，最好情况时间复杂度是O(N);
  • 3.空间复杂度：O(1),是一种稳定的排序算法
  • 4.稳定性：稳定

二、希尔排序

希尔排序是一种特殊的插入排序，是直接插入排序基础上的优化。

2.1 算法思想

希尔排序又称为缩小增量法，希尔排序的基本思想是：先选定一个整数，把待排序文件中所有记录分成若干个组，所有距离为“gap”的记录分在同一组内，并对每一个组内的记录进行排序。然后，取，重复上述分组和排序工作。当“gap”（间隔）==1，所有记录在统一组内排好序。

  • 1.先进行预排序，使数组接近有序
  • 2.直接插入排序

预排序：分组排，间隔为 gap 是一组，假设 gap ==3;

9 8 7 6 5 4 3 2 1 0,如果将这组数据升序排序，使用直接插入排序，算法的复杂度就是 O(N^2);

每个 gap 间隔的小分组都再进行插入排序。

优点：大数，小数更快的到达两端，当gap等于1时，就是直接插入排序，这时候时间复杂度就是大大降低。

2.2 程序实现

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>

//希尔排序
void ShellSort(int* a, int n)//升序
{
	int gap = n;
	while (gap > 1)//当gap等于1时，就是直接插入排序
	{
		gap = gap / 2;
		//把间隔为gap的多组数据同时排序
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end>=0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
				a[end + gap] = tmp;
			}
		}
	}
	//打印数据
	Print(a, n);
}
int main()
{
	int a[10] = { 9,8,7,6,5,4,3,2,1,0 };
	//希尔排序
	ShellSort(a, sizeof(a) / sizeof(a[0]));
	return 0;
}

2.3 希尔排序的特征总结

  • 1.希尔排序是对直接插入排序的优化。
  • 2.当gap>1时都是预排序，目的是让数组更接近于有序。当gap==1时，数组已经接近有序，这样就会很快。整体而言，可以达到优化的效果。
  • 3.希尔排序的时间复杂度不好计算，需要根据数据进行推导，推导出来的的平均时间复杂度：O(N^1.3——N^2)。
  • 4.稳定性：不稳定

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

赞 (0)

相关推荐

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

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

  • 简单了解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语言实现选择排序、直接插入排序、冒泡排序的示例

    选择排序 选择排序是一种简单直观的排序算法,其核心思想是:遍历数组,从未排序的序列中找到最小元素,将其放到已排序序列的末尾. 时间复杂度: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.算法模板 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语言直接插入排序算法介绍

    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语言深入探究直接插入排序与希尔排序使用案例讲解

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

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

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

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

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

  • 排序算法图解之Java插入排序

    排序算法图解之Java插入排序

    目录 1.插入排序简介 2.插入排序思想及图解 3.插入排序代码实现 1.插入排序简介 插入排序,一般也被称为直接插入排序.对于少量元素的排序,它是一个有效的算法.插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的.记录数增1的有序表.在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动 2.插入排序思想及图解 插入排序的基本思想如下: 把n个待排序的元素看成为一个有序表和一个无

  • 10个python3常用排序算法详细说明与实例（快速排序，冒泡排序，桶排序，基数排序，堆排序，希尔排序，归并排序，计数排序）

    我简单的绘制了一下排序算法的分类,蓝色字体的排序算法是我们用python3实现的,也是比较常用的排序算法. Python3常用排序算法 1.Python3冒泡排序--交换类排序 冒泡排序(Bubble Sort)也是一种简单直观的排序算法. 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来. 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 作为最简单的排序算法

  • Java各种排序算法汇总(冒泡,选择,归并,希尔及堆排序等)

    本文实例汇总了Java各种排序算法.分享给大家供大家参考,具体如下: 1. 冒泡排序: public class SortTest { public static void main(String[] args) { int[] a = {345,7,32,5,4,-1,3,12,23,110,45645,321,456,78,-1,78,78,32,444,345}; show(a); bubbleSort(a); show(a); } private static void bubbleSo

  • PHP实现常见排序算法的示例代码

    目录 1.冒泡排序 2.选择排序 3.快速排序 4.插入排序 补充 1.冒泡排序 两两相比,每循环一轮就不用再比较最后一个元素了,因为最后一个元素已经是最大或者最小. function maopaoSort ($list) { $len = count($list); for ($i = 0; $i < $len - 1; $i++) { for ($j = 0; $j < $len - $i - 1; $j++) { if ($list[$j] > $list[$j + 1]) { $

  • C/C++实现八大排序算法汇总

    C/C++实现八大排序算法汇总

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

  • C++ 算法之希尔排序详解及实例

    C++ 算法之希尔排序详解及实例

    C++ 算法之希尔排序算法详解及实例 希尔排序算法 定义: 希尔排序是插入排序的一种,也称缩小增量排序,是直接插入排序算法的一种更高效的改进版本. 算法思想: 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰好被分为一组,算法终止. 时间复杂度: O(N) 空间复杂度: O(1) 性能: 希尔排序为不稳定算法(一次插入排序是稳定的,不会改变相同元素的相对顺序,但是在不同的插入排序中,相同的元素可能在各自的

  • java 排序算法之希尔算法

    java 排序算法之希尔算法

    目录 插入排序存在的问题 简单介绍 基本思想 代码实现 大数据量耗时测试 移动法实现希尔排序 移动法-大数据量耗时测试 算法分析 注:学习本篇的前提是要会插入排序,数据结构与算法--排序算法-插入排序 插入排序存在的问题 简单的插入排序可能存在的问题. 如数组 arr = {2,3,4,5,6,1} 这时需要插入的数 1(最小),过程是: 展示的是要移动 1 这个数,的过程,由于在最后,需要前面的所有数都往后移动一位 {2,3,4,5,6,6} {2,3,4,5,5,6} {2,3,4,4,5,

  • c++实现排序算法之希尔排序方式

    c++实现排序算法之希尔排序方式

    目录 排序算法之希尔排序 基本思想 希尔排序算法 复杂度分析 关于希尔排序的问题分析 排序算法之希尔排序及时间复杂度分析 希尔排序 时间复杂度 排序算法之希尔排序 基本思想 将相距某个“增量”的记录组成一个子序列,这样才能保证在子序列内分别进行直接插入排序后得到的结果是基本有序的而不是局部有序. 进一步理解: 先将整个待排元素序列分割成若干个子序列(由相隔某个“增量”的元素组成的)分别进行直接插入排序,然后依次缩减增量再进行排序,待整个序列中的元素基本有序(增量足够小)时,再对全体元素进行一次直

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

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

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

  • C语言常见排序算法之交换排序(冒泡排序,快速排序)

    目录 前言 1.交换排序——冒泡排序 1.1 算法思想 1.2 动图演示 1.3 冒泡最好的情况 2. 交换排序——快速排序 2.1 快速排序——挖坑法 快排的缺点 三数取中法 2.3 快速排序——左右指针法 2.4 前后指针法 前言 本期为大家带来的是常见排序算法中的交换排序,主要有冒泡排序,快速排序,快排分享了三种算法:挖坑法,左右指针法,前后指针法,以及两种优化方式:解决快排最坏情况的“三数取中”,避免递归次数过多的"小区间优化", 基本思想:所谓交换,就是根据序列中两个记录键值

随机推荐