插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
算法描述
一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
1. 从第一个元素开始,该元素可以认为已经被排序
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置中
6. 重复步骤2
示例代码
void InsertSort(int array[], int length)
{
int i, j, key;
for (i = 1; i < length; i++)
{
key = array[i];
// 把i之前大于array[i]的数据向后移动
for (j = i - 1; j >= 0 && array[j] > key; j--)
{
array[j + 1] = array[j];
}
// 在合适位置安放当前元素
array[j + 1] = key;
}
}
算法复杂度
如果目标是把n个元素的序列升序排列,那么采用插入排序存在最好情况和最坏情况。最好情况就是,序列已经是升序排列了,在这种情况下,需要进行的比较操作需(n-1)次即可。最坏情况就是,序列是降序排列,那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上(n-1)次。平均来说插入排序算法复杂度为O(n2)。因而,插入排序不适合对于数据量比较大的排序应用。但是,如果需要排序的数据量很小,例如,量级小于千,那么插入排序还是一个不错的选择。
分享到:
相关推荐
# sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() #计数排序 # sort.quickSort() #快速排序 该排序算法把每次的排序结果都列出来,可供初学...
全面的排序算法实现,包括插入排序、合并排序、堆排序、快速排序。 堆排序:HeapSort 讲解详见http://blog.csdn.net/fly_yr/article/details/8550701 插入排序:InSertion_Sort 讲解详见...
基于python的排序算法-插入排序Insertion Sort
经典排序算法 - 插入排序Insertion sort 经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - ...
C C++ insertion sort
1. 3 InsertionSort:每次拿起一个数,插入到它左边数组的正确位置。 1.4 QuickSort:选择一个数,作为标准,小于它的放在左边,大于它的放在右边。并把它放在中间;递归地对左右子数组进行排序。 实现时:1. 确定...
本文介绍了一个使用Python实现的插入排序(Insertion Sort)算法。插入排序是一种简单直观的排序算法,其工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。具体来说,...
JavaScript_資料結構與演算法_氣泡排序_Bubble_Sort、插入排序_Insertion_Sort_實作與分析_-
插入排序算法,随机数列,可控制数列的上下界限,c++。
常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort), * 二路归并排序(MergeSort),堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现...
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
直接插入排序
主要介绍了PHP排序算法之直接插入排序(Straight Insertion Sort),结合实例形式较为详细的分析了直接插入排序算法的原理与实现技巧,需要的朋友可以参考下
3. 插入排序(Insertion Sort) 4. 快速排序(Quick Sort) 5. 归并排序(Merge Sort) 6. 堆排序(Heap Sort) 7. 计数排序(Counting Sort) 8. 桶排序(Bucket Sort) 9. 基数排序(Radix Sort) 10. 希尔排序...
C#,单向链表(Simply Linked List)的插入排序(Insertion Sort)算法与源代码 所谓插入排序法乃是将一个数目插入该占据的位置。 假设我们输入的是 “5,1,4,2,3” 我们从第二个数字开始,这个数字是1,我们的...
实现了选择排序(SeletionSort),插入排序(InsertionSort),自底向上排序(BottomupSort),合并排序(MergeSort)和快速排序(QuickSort)
这篇文章主要介绍了python常用排序算法的实现代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 排序是计算机语言需要实现的基本算法之一,有序的数据结构会...
直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下: 假设待排序...
主要介绍了Java数据结构及算法实例:插入排序 Insertion Sort,本文直接给出实例代码,代码中包含详细注释,需要的朋友可以参考下
插入排序(Insertion Sort)源码和运行示例,配合博客使用更佳。