资讯专栏INFORMATION COLUMN

JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

cgspine / 2206人阅读

摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上,通常采用排序即只需用到的额外空间的排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括:

插入排序

插入排序(英语:Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

算法步骤

将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

2 动图演示

JavaScript 代码实现

</>复制代码

  1. function insertionSort(arr) {
  2. var len = arr.length;
  3. var preIndex, current;
  4. for (var i = 1; i < len; i++) {
  5. preIndex = i - 1;
  6. current = arr[i];
  7. while(preIndex >= 0 && arr[preIndex] > current) {
  8. arr[preIndex+1] = arr[preIndex];
  9. preIndex--;
  10. }
  11. arr[preIndex+1] = current;
  12. }
  13. return arr;
  14. }

Python 代码实现

</>复制代码

  1. def insertionSort(arr):
  2. for i in range(len(arr)):
  3. preIndex = i-1
  4. current = arr[i]
  5. while preIndex >= 0 and arr[preIndex] > current:
  6. arr[preIndex+1] = arr[preIndex]
  7. preIndex-=1
  8. arr[preIndex+1] = current
  9.    return arr

Go 代码实现

</>复制代码

  1. func insertionSort(arr []int) []int {
  2. for i := range arr {
  3. preIndex := i - 1
  4. current := arr[i]
  5. for preIndex >= 0 && arr[preIndex] > current {
  6. arr[preIndex+1] = arr[preIndex]
  7. preIndex -= 1
  8. }
  9. arr[preIndex+1] = current
  10. }
  11. return arr
  12. }

6 Java实现

</>复制代码

  1. public static void insertion_sort( int[] arr ){
  2. for( int i=0; i0; j-- )
  3. {
  4. if( arr[j-1] <= arr[j] )
  5. break;
  6. int temp = arr[j];
  7. arr[j] = arr[j-1];
  8. arr[j-1] = temp;
  9. }
  10. }
  11. }

7 Java的另一个版本

</>复制代码

  1. public static void insertion_sort(int[] arr){
  2. for (int i = 1; i < arr.length; i++ ) {
  3. int temp = arr[i];
  4. int j = i - 1;
  5. for (; j >= 0 && arr[j] > temp; j-- ){
  6. arr[j + 1] = arr[j];
  7. }
  8. arr[j + 1] = temp;
  9. }
  10. }

8 C#实现

</>复制代码

  1. public static void InsertSort(double[] data){
  2. int i, j;
  3. var count = data.Length;
  4. for (i = 1 ; i < count ; i++) {
  5. var t = data[i];
  6. for(j = i - 1; j >= 0 && data[j] > t; j--)
  7. data[j + 1] = data[j];
  8. data[j + 1] = t;
  9. }
  10. }

希望可以一起交流技术,有兴趣可以加qq邀请入群:525331804 全栈技术开发qq群:581993430

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/70016.html

相关文章

  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列插入排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上,通常采用排序即只需用到的额外空间的排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: showImg(https://segm...

    lufficc 评论0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列插入排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。插入排序在实现上,通常采用排序即只需用到的额外空间的排序,因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: showImg(https://segm...

    GeekQiaQia 评论0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,系列归并排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语,或,是创建在归并操作上的一种有效的排序算法,效率为。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    zhou_you 评论0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,系列归并排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语,或,是创建在归并操作上的一种有效的排序算法,效率为。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    caoym 评论0 收藏0
  • JavaScript算法 ,Python算法,Go算法,java算法,系列归并排序

    摘要:常见的内部排序算法有插入排序希尔排序选择排序冒泡排序归并排序快速排序堆排序基数排序等。用一张图概括归并排序英语,或,是创建在归并操作上的一种有效的排序算法,效率为。 常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。用一张图概括: showImg(https://segmentfault.com/img/bVNwuO?w=966&h=...

    microcosm1994 评论0 收藏0

发表评论

0条评论

cgspine

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<