原理
1、把所有的元素分为两组, 已经排序的未排序的;
2、找到未排序组中的第一个元素, 向已经排序的组中进行插入;
3、倒序遍历已经排序的元素, 依次和待插入的元素进行比较, 直到找到一个元素小于待插入元素, 那么就把待插入元素放到这个位置, 其他的元素向后移动一位;
实现类 public class Insertion { /** * 对数据a中的元素进行选择排序 * * @param a */ public static void sort(Comparable[] a) { for (int i = 1; i < a.length; i++) { for (int j = i; j > 0; j--) { // 比较索引j处的值和索引j-1处的值, 如果索引j-1处的值比索引j处的值大, // 则交换数据, 否则, 就是找到合适的位置, 退出循环即可 if (greater(a[j - 1], a[j])) { exchange(a, j - 1, j); } else { break; } } } } /** * 比较v元素是否大于w元素 * * @param v * @param w * @return */ private static boolean greater(Comparable v, Comparable w) { return v.compareTo(w) > 0; } /** * 数据元素i和j交换位置 * * @param a * @param i * @param j */ private static void exchange(Comparable[] a, int i, int j) { Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } }
测试类 public static void main(String[] args) { Integer[] a = {4,3,2,10,12,1,5,6}; Insertion.sort(a); // 期望值 [1, 2, 3, 4, 5, 6, 10, 12] System.out.println(Arrays.toString(a)); }
时间复杂度
比较次数为 (N-1) + (N-2) + (N - 3) + .... + 2 + 1 = ((N-1)+1) * (N-1)/2=N^2/2-N/2; 元素交换的次数; (N-1) + (N-2) + (N - 3) + .... + 2 + 1 = ((N-1)+1) * (N-1)/2=N^2/2-N/2; 总执行次数为: (N^2/2-N/2) + (N^2/2-N/2) = N^2 -N; 按照大O记法, 冒泡排序的时间复杂度为O(N^2)
使用场景: 适用于数据量不大的排序