包括:直接插入排序,二分插入排序(又称折半插入排序),链表插入排序,希尔排序(又称缩小增量排序)。属于稳定排序的一种(通俗地讲,就是两个相等的数不会交换位置) 。
基本思想:
将n个元素的数列分为已有序和无序两个部分,如下所示:
{{a1},{a2,a3,a4,…,an}}
{{a1⑴,a2⑴},{a3⑴,a4⑴ …,an⑴}}
…
{{a1(n-1),a2(n-1) ,…},{an(n-1)}}
每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,找出插入位置,将该元素插入到有序数列的合适位置中。
假设在一个无序的数组中,要将该数组中的数按插入排序的方法从小到大排序。假设啊a[]={3,5,2,1,4};插入排序的思想就是比大小,满足条件交换位置,一开始会像冒泡排序一样,但会比冒泡多一步就是交换后(a[i]=a[i+1]后)原位置(a[i])会继续和前面的数比较满足条件交换,直到a[i+1]前面的数组是有序的。比如在第二次比较后数组变成a[]={2,3,5,1,4};
插入排序过程示例
算法复杂度
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1)次。平均来说插入排序算法的时间复杂度为O(n^2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
稳定性
插入排序是在一个已经有序的小序列的基础上,一次插入一个元素。当然,刚开始这个有序的小序列只有1个元素,就是第一个元素。比较是从有序序列的末尾开始,也就是想要插入的元素和已经有序的最大者开始比起,如果比它大则直接插入在其后面,否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的,那么插入元素把想插入的元素放在相等元素的后面。所以,相等元素的前后顺序没有改变,从原无序序列出去的顺序就是排好序后的顺序,所以插入排序是稳定的。
算法的实现:
public class InsertSort { public static void main(String[] args) { int a[] = new int[]{1, 7, 9, 3, 5, 8, 6, 10, 6}; System.out.print("Before sort: "); for (int i : a) { System.out.print(i + " "); } sort(a); System.out.print("\nAfter sort: "); for (int i : a) { System.out.print(i + " "); } } private static void sort(int arr[]) { for (int i=1; i< arr.length; i++) { for (int j =i; j > 0; j--) { // 只要小于前面有序数组中任何一个,就交换 if (arr[j] < arr[j-1]) { int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } else { //不用交换,直接跳出 break; } } //输出每一步的结果 System.out.println(); for (int t : arr) { System.out.print(t + " "); } } } }
结果:
Before sort: 1 7 9 3 5 8 6 10 6 1 7 9 3 5 8 6 10 6 1 7 9 3 5 8 6 10 6 1 3 7 9 5 8 6 10 6 1 3 5 7 9 8 6 10 6 1 3 5 7 8 9 6 10 6 1 3 5 6 7 8 9 10 6 1 3 5 6 7 8 9 10 6 1 3 5 6 6 7 8 9 10 After sort: 1 3 5 6 6 7 8 9 10
算法演示: http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/straight_insertion_sort.asp
相关推荐
实现以下常用的内部排序算法并进行性能比较:"直接插入排序"," 折半插入排序"," 2—路插入排序"," 表插入排序"," 希尔排序"," 起泡排序"," 快速排序"," 简单选择排序"," 树形选择排序"," 堆排序"," 归并排序"," 链式...
Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...
C语言版的排序方法---插入排序,非常有用的代码,可以实际中使用。
输入n个数,用直接插入排序算法排序,并输出这n个数
NULL 博文链接:https://xieyan30.iteye.com/blog/1922400
排序算法 —— 直接插入排序(图文超详细)
NULL 博文链接:https://hoxis.iteye.com/blog/2034252
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
算法-理论基础- 排序- 直接插入排序(包含源程序).rar
此文件为数据结构中的九种排序算法,包含一些排序方法的过程,其九种排序包括:直接插入排序,折半插入排序,希尔排序,冒泡排序,快速排序,选择排序,堆排序,归并排序,基数排序!
七大排序算法如下: 交换排序:快速排序quicksort,冒泡排序bubblesort 选择排序:直接选择排序selectionsort,堆排序maxheapsort...插入排序:直接插入排序insertsort,希尔排序shellsort 合并排序:归并排序mergesort
三种排序算法(直接插入、冒泡、快速)的C++实现。有讲解
数据结构---直接插入排序/快速排序/选择排序/冒泡排序(详细实现算法和性能比较)
用c++类实现多种排序算法。一个类中实现全部算法,另一个类中实现界面设置和控制。
希尔排序,直接插入排序,折半插入排序算法的实现,c语言实现希尔排序
数据结构之排序算法 包含目前所有排序方法: 1 快速排序 2 冒泡排序 3 堆排序 4 希尔排序 5 直接插入排序 6 直接选择排序 7 基数排序 8 箱、桶排序 9 归并排序
(1) 完成5种常用内部排序算法的演示,5种排序算法为:快速排序,直接插入排序,选择排序,堆排序,希尔排序; (2) 待排序元素为整数,排序序列存储在数据文件中,要求排序元素不少于30个; (3) 演示程序开始,...
7大排序算法(快速排序,冒泡排序,选择排序,归并排序,插入排序,希尔排序,堆排序)实现源码
数据结构(c语言版)严蔚敏 吴伟民编著 中直接插入排序、折半排序、shell排序、冒泡排序、快速排序、选择排序、堆排序的实现、归并排序,使用c语言实现
提供五种排序算法的C++实现方法,输入(待排序元素个数、排序码上界(采用随机生成数组方式)),可选择输出(原始数组、排序后数组、原始数组有序度和无序度、排序过程中数据比较次数与数据移动次数、数组中出现...