排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 我们这里的排序是内部排序。
所谓排序,就是要整理表中的记录,使之按关键字递增(或递减)有序排列,当排序的关键字都不相同时,排序结果是唯一的。本篇博客介绍插入排序。
插入排序的基本思想是:每次将一个待排序的记录,按其关键字的大小插入到前面已经排好序的子表中的适当位置,直到全部记录插入完成为止。主要介绍直接插入排序,二分插入排序,希尔排序
1.直接插入排序
基本思路
每次从无序表中取出第一个元素,把它插入到有序表的合适位置,使有序表仍然有序。假设待排序的记录存放在数组R[0..n]中。初始时,R[0]自成1个 有序区,无序区为R[1..n]。从i=1起直至i=n为止,依次将R[i]插入当前的有序区R[1..i-1]中,生成含n个记录的有序区。
实现代码
void InsertSort(int a[],int len)//递增排列 { int temp; for(int i=1;i<len;i++)//a[0]在有序区,需要依次把a[1...len-1]插入到有序区 { temp=a[i]; int j=i-1;//从有序区间最右边对比插入 while(j>=0&&temp<a[j]) { a[j+1]=a[j]; j--; } a[j+1]=temp; } //输出结果 for(int i=0;i<len;i++) cout<<a[i]<<" "; }
效率分析
直接插入排序所耗费的时间是有很大差异的。最好情况是表初态为正序,此时算法的时间复杂度为O(n),最坏情况是表的初态为反序,此时的时间复杂度为 O(n^2)。算法的平均时间复杂度也是O(n^2)。直接插入排序算法只使用了几个辅助变量,与问题n无关,即辅助空间复杂度为O(1),也就是说它是 一个就地排序。
2.二分插入排序
基本思想
是在上面直接插入排序的方法上在比较大小时用上前面说的二分查找。即在数据表中有一个元素序列v[0],v[1],v[2]......v[n].其中v[0],v[1],v[2]......v[i-1]是已经排好序的元素。在插入v[i]。利用折半搜索寻找v[i]的插入位置。
实现代码
//二分插入排序 void InsertSort1(int a[],int len)//递增排列 { int temp,low,high,mid; for(int i=1;i<len;i++)//a[0]在有序区,需要依次把a[1...len-1]插入到有序区 { temp=a[i]; low=0;high=i-1; while(low<=high)//在a[low....high]中二分查找有序插入的位置 { mid=(low+high)/2; if(temp<a[mid]) high=mid-1; else low=mid+1; } for(int j=i-1;j>=high+1;j--) a[j+1]=a[j]; a[high+1]=temp; } }
效率分析
二分插入排序的空间复杂度为O(1)。二分插入排序只是减少了关键字的比较次数,而记录的移动次数不变。因此,时间复杂度仍为O(n^2)。
3.希尔排序
基本思想
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。
具体步骤
先取定一个小于n(数组的长度)的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1
的倍数的记录放在同一个组中,在各组内进行直接插入排序;然后,取第二个增量d2(d2<d1),重复上面步骤,直至所取的增量为d=1(di<di+i),,即所有记录放在同一组中进行直接插入排序。
例如:
实现代码
我们简单处理增量序列:增量序列d = {n/2 ,n/4, n/8 .....1} n为要排序数的个数。
void ShellSort(int a[],int len) { int gap,temp,j; gap=len/2;//增量初始值 while(gap>0) { //---把gap当1,即相当直接排序代码 for(int i=gap;i<len;i++)//对相隔增量gap位置的所有元素直接插入排序 { temp=a[i]; j=i-gap; while(j>=0&&temp<a[j])//对相隔gap的元素进行排序 { a[j+gap]=a[j]; j=j-gap; } a[j+gap]=temp; j=j-gap; } gap=gap/2; } }
效率分析
希尔排序的性能分析是一个复杂的问题,与增量有关,一般认为其平均时间复杂度为O(n^1.3)。希尔排序一般要比直接插入排序快。希尔排序算法也只是使用了几个辅助变量,与问题n无关,所以辅助空间复杂度为O(1),也是就地排序。
然而,希尔排序是一种不稳定的排序。因为两个元素相等时,希尔排序可能会改变它们两的位置,所以是不稳定排序
最后附上源码地址:https://github.com/longpo/algorithm/tree/master/InsertSort
相关推荐
**插入排序**是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。这种算法对大数据量的处理效率较低,但对于小规模数据或者部分有序的...
Java排序算法 - 插入排序 插入排序(Insertion Sort)是一种简单的排序算法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增 1 的有序表。该算法的实现非常简单,但其时间复杂度...
插入排序是一种基础且直观的排序算法,它的工作原理可以类比于整理扑克牌。在实际应用中,插入排序对于小规模数据或者部分有序的数据表现优秀,但对于大规模无序数据,其效率相对较低。以下是关于插入排序的详细知识...
插入排序算法是一种简单的排序算法,它的工作原理是通过将每个元素插入到已经排序的序列中,以达到排序的目的。插入排序算法的时间复杂度为O(n^2),因此它适合小规模的数据排序。 4.快速排序算法 快速排序算法是一...
理解插入排序算法-讲解
经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - ...
直接插入排序是一种基础且简单的排序算法,它的工作原理可以形象地比喻为扑克牌的洗牌过程。在实际应用中,虽然对于大规模数据的排序效率不如更高级的算法,如快速排序、归并排序等,但它的实现简单,适合小规模或...
在编程领域,排序算法是计算机科学中的核心概念,特别是在Java这样的高级编程语言中。这个名为"java排序算法-大全.rar"的压缩包文件显然包含了多种Java实现的排序算法,这对于我们理解和掌握这些算法至关重要。 ...
**插入排序(Insertion Sort)**是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到...
插入排序是一种简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序...
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
本文将深入探讨标题和描述中提到的一些基本排序算法,包括选择排序、冒泡排序、插入排序、希尔排序、堆排序、快速排序以及归并排序,并结合C++编程语言进行讲解。 1. **选择排序(Selection Sort)** - 选择排序是一...
- 直接插入排序:是一种简单的排序算法,将每个元素插入到已排序的部分,保持有序。时间复杂度为O(N^2),适用于小规模数据和基本有序的数据。 - 希尔排序:是插入排序的一种改进版本,通过设定间隔序列(希尔增量...
直接插入排序是一种基础且常用的排序算法,它的工作原理可以直观地理解为手动整理扑克牌的过程。在本篇文章中,我们将深入探讨直接插入排序的细节,包括它的基本思想、步骤、时间复杂度以及适用场景。 一、基本思想...
在这个例子中,可能会有一个类`SortAlgorithms`包含各种排序算法的成员函数,如冒泡排序、选择排序、插入排序、快速排序等。另一个类`UserInterface`则负责处理用户交互和控制执行哪种排序算法。 3. **排序算法的...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
本篇文章将详细讨论几种常见的排序算法:选择排序、冒泡排序、插入排序、合并排序以及快速排序,分析它们的算法原理、时间效率,并通过经验分析验证理论分析的准确性。 **1. 选择排序(Selection Sort)** 选择排序...
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
该资源提供了Java中实现插入排序的全面指南。文档中涵盖了插入排序的基本概念,包括如何对数组进行排序以及如何在Java中实现插入排序。此外,文档还包括一个逐步指南,介绍了如何在Java中实现插入排序,包括详细的...