直接插入排序
基本思想:
在要排序的一组数中,假设前面(n-1)[n>=2] 个数已经是排 好顺序的,现在要把第 n 个数插到前面的有序数中,使得这 n 个数也是排好顺序的。如此反复循环,直到全部排好顺序。
代码实现
package Suanfa;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 插入排序
* Created by hushangjie on 2017/11/6.
*/
public class InsertSort {
public static void sort(int[] arr) {
int temp = 0;
for (int i = 1; i < arr.length; i++) {
temp = arr[i];
int j = i -1;
while (j >= 0 && temp < arr[j]) {
//往后移动
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
}
public static void main(String[] args) {
int[] arr = {34, 2, 33, 12, 5, 55};
sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.println(arr[i]);
}
}
}
特点
插入排序是稳定的,时间复杂度为 O(n^2),待排序数列越接近有序,则算法效率越高。插入排序一般不会单独使用,因为其效率并不高,但是可以结合其他排序一起使用,比如快速排序,因为快速排序最后的数据往往是有序的,此时可以使用插入排序收尾。
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于