什么是插入排序算法?

原标题 |  Everything you need to know about Insertion Sort algorithm

者 |  Sanjula Madurapperuma

译者 | david95(研发工程师)

注:本文的相关链接请访问文末【阅读原文】

介绍

大家好,我是Sanjula,在这个教程中,我希望告诉你一些关于插入排序算法的知识,包括:

  • 什么是插入排序

  • 为什么插入排序很重要

  • 插入排序的性能

  • 插入排序的原理

  • Java代码实现

让我们开始吧!

什么是插入排序?

它是一种简单的排序算法,只需遍历一次数组即可完成排序。

为什么插入排序很重要?

插入排序有几个优势:

  • 算法简单好理解

  • 相同的值不需要交换顺序

  • 数组可以一边增加内容,一边排序

  • 对小数据集很高效,特别是和其他算法相比,比如有些时间复杂度要到O(n²)

  • 它带来额外的内存开销小,只有一个常数,时间复杂度是O(1)。

插入排序的性能

  • 最差的性能是 O(n²)的比较和交换

  • 最好的性能是O(n) 的比较和O(1)的交换

  • 平均的性能是O(n²) 的比较和交换

插入排序的原理

在每次迭代中,它对比当前元素和下一个元素,检查当前元素是否比它大。

如果大的话,就原地不动,进行下一个元素。如果小的话,它会一直向前比对,一直找到正确的位置。

Java代码实现

提示:看代码之前,你可以自己试着动手实现.


 

package com.sanjula.java.algorithms.InsertionSort;


public class InsertionSort {

/**

* Sort method using insertion sort

* @param arr - Integer array passed in

* to be sorted

**/

public void sort(int arr[]){

// Store the length of the array

int n = arr.length;

// For loop to iterate through each

for (int i = 0; i < n; i++){

// Storing current element to check correct position

int key = arr[i];

int j = i - 1;


// Move element to correct position if

// condition is true

while(j >= 0 && arr[j] > key){

arr[j + 1] = arr[j];

j = j - 1;

}

arr[j + 1] = key;

}

}


/**

* Print the array supplied

* @param arr - Array passed

* @param msg - Message to be printed

**/

public static void printArray(int arr[], String msg) {

int length = arr.length;

System.out.println(msg);

for (int i = 0; i < length; i++) {

System.out.print(arr[i] + " ");

}

System.out.println();

}


public static void main(String[] args) {

// Initialize and declare the array arr

int arr[] = {25, 12, 3, 1, 9, 15};

// Create new instance of class InsertionSort

InsertionSort insertionSort = new InsertionSort();


printArray(arr, "Array before insertion sort");

// Invoke the sort method, passing in the array arr

insertionSort.sort(arr);

// Print the sorted array

printArray(arr, "Array after insertion sort");

}

}

恭喜你,你现在应该了解插入排序算法了。

如果上面的代码你认为有问题,可以通过这个github联系我:

https://gist.github.com/sanjulamadurapperuma/25677635f216b9fa858d8051140e47f2

希望这篇文章能帮到你,感谢阅读!

本文编辑:王立鱼

英语原文:https://www.freecodecamp.org/news/everything-you-need-to-know-about-insertion-sort-algorithm/

想要继续查看该篇文章相关链接和参考文献?

点击底部 【阅读原文】 即可访问:

https://ai.yanxishe.com/page/TextTranslation/1913

你可能还想看

  点击  阅读原文   查看本文更多内容

我来评几句
登录后评论

已发表评论数()

相关站点

+订阅
热门文章