原标题 | 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;publicclassInsertionSort {/** * Sort method using insertion sort * @param arr - Integer array passed in * to be sorted **/publicvoidsort(int arr[]){// Store the length of the arrayint n = arr.length;// For loop to iterate through eachfor (int i = 0; i < n; i++){// Storing current element to check correct positionint key = arr[i];int j = i - 1;// Move element to correct position if // condition is truewhile(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 **/publicstaticvoidprintArray(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(); }publicstaticvoidmain(String[] args) {// Initialize and declare the array arrint 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
你可能还想看
点击 阅读原文，查看本文更多内容
继续阅读
阅读原文