5
排序算法——直接插入排序
source link: https://suiyia.github.io/2019/10/31/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E2%80%94%E2%80%94%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
排序算法——直接插入排序
插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
public class 直接插入排序 {
public static int[] order(int[] a){
if (a == null){
return null;
}
if (a.length == 0 || a.length == 1){
return a;
}
// 每次插入一个元素到合适位置
for (int i = 1; i < a.length ; i++) {
// 将当前位置的值插入到合适地方
int currNum = a[i];
int j = i - 1;
while (j >= 0 && a[j] > currNum){
a[j + 1] = a[j];
j --;
}
a[j + 1] = currNum;
}
return a;
}
public static void main(String[] args) {
int[] a = {6,3,2,9,5,3,1,0};
System.out.println(Arrays.toString(order(a)));
}
}
时间复杂度：O(n*n)
空间复杂度：O(1)
算法稳定性：假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的！
直接插入排序是稳定的排序算法
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK