详解插入排序

插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法 。插入排序是一种最简单的排序方法,插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入,下面为大家详细讲解一下插入排序。

创新互联公司主要业务有网站营销策划、成都网站设计、成都做网站、外贸网站建设、微信公众号开发、微信小程序定制开发H5开发、程序开发等业务。一次合作终身朋友,是我们奉行的宗旨;我们不仅仅把客户当客户,还把客户视为我们的合作伙伴,在开展业务的过程中,公司还积累了丰富的行业经验、网络营销推广资源和合作伙伴关系资源,并逐渐建立起规范的客户服务和保障体系。 

算法步骤

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

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

动图演示

插入排序简介插入排序简介

代码实现

JavaScript

实例

function insertionSort(arr) {
   var len = arr.length;
   var preIndex, current;
   for (var i = 1; i while(preIndex >= 0 && arr[preIndex] > current) {
           arr[preIndex+1] = arr[preIndex];
           preIndex--;
       }
       arr[preIndex+1] = current;
   }
   return arr;
}

Python

实例

def insertionSort(arr):
   for i in range(len(arr)):
       preIndex = i-1
       current = arr[i]
       while preIndex >= 0 and arr[preIndex] > current:
           arr[preIndex+1] = arr[preIndex]
           preIndex-=1
       arr[preIndex+1] = current
   return arr

Go

实例

func insertionSort(arr []int) []int {
       for i := range arr {
               preIndex := i - 1
               current := arr[i]
               for preIndex >= 0 && arr[preIndex] > current {
                       arr[preIndex+1] = arr[preIndex]
                       preIndex -= 1
               }
               arr[preIndex+1] = current
       }
       return arr
}

Java

实例

public class InsertSort implements IArraySort {

   @Override
   public int[] sort(int[] sourceArray) throws Exception {
       // 对 arr 进行拷贝,不改变参数内容
       int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

       // 从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的
       for (int i = 1; i while (j > 0 && tmp if (j != i) {
               arr[j] = tmp;
           }

       }
       return arr;
   }
}

PHP

实例

function insertionSort($arr)
{
   $len = count($arr);
   for ($i = 1; $i $len; $i++) {
       $preIndex = $i - 1;
       $current = $arr[$i];
       while($preIndex >= 0 && $arr[$preIndex] > $current) {
           $arr[$preIndex+1] = $arr[$preIndex];
           $preIndex--;
       }
       $arr[$preIndex+1] = $current;
   }
   return $arr;
}

C

实例

void insertion_sort(int arr[], int len){
       int i,j,key;
       for (i=1;i=0) && (arr[j]>key)) {
                       arr[j+1] = arr[j];
                       j--;
               }
               arr[j+1] = key;
       }
}

C++

实例

void insertion_sort(int arr[],int len){
       for(int i=1;i
  
   while((j>=0) && (key
   
  

C#

实例

public static void InsertSort(int[] array)
{
   for(int i = 1;i for(int j = i - 1;j >= 0;j--)
       {
           if(array[j] > temp)
           {
               array[j + 1] = array[j];
               array[j] = temp;
           }
           else
               break;
       }
   }
}

Swift

实例

for i in 1..
  
   let temp = arr[i]    
   for j 
   in (0..
   reversed() {        if arr[j] > temp {            arr.swapAt(j, j+1)        }    } } 
  

当前标题:详解插入排序
文章转载:http://www.gawzjz.com/qtweb/news19/178919.html

网站建设、网络推广公司-创新互联,是专注品牌与效果的网站制作,网络营销seo公司;服务项目有等

广告

声明:本网站发布的内容(图片、视频和文字)以用户投稿、用户转载内容为主,如果涉及侵权请尽快告知,我们将会在第一时间删除。文章观点不代表本网站立场,如需处理请联系客服。电话:028-86922220;邮箱:631063699@qq.com。内容未经允许不得转载,或转载时需注明来源: 创新互联