原标题 | Everything you need to know about Insertion Sort algorithm 作者 | Sanjula Madurapperuma 译者 | david95(研发工程师) 注:本文的相关链接请访问文末【阅读原文】
介绍
大家好,我是Sanjula,在这个教程中,我希望告诉你一些关于插入排序算法的知识,包括:
让我们开始吧!
什么是插入排序?
它是一种简单的排序算法,只需遍历一次数组即可完成排序。
为什么插入排序很重要?
插入排序有几个优势:
插入排序的性能
插入排序的原理
在每次迭代中,它对比当前元素和下一个元素,检查当前元素是否比它大。
如果大的话,就原地不动,进行下一个元素。如果小的话,它会一直向前比对,一直找到正确的位置。
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