插入排序-Java实现
什么是插入排序?
插入排序是一种简单,直观的排序算法.
就像打牌时,从牌桌上取出一张牌后,插入到手中已有的牌的方式.
插入排序有一个前提. 即: 假设前面的元素是已经排好顺序的, 我只需要将后面的元素依次插入到前面排好序的队列中即可.
插入排序过程
1. 图解插入排序
2. 插入排序步骤详解
假设前面M个元素已经排好序
将第M+1个元素依次与前一个元素比较
当后面的元素比前面的元素大时,交换两个元素顺序
依次执行上述过程,直到所有的元素都排好序.
如何实现插入排序?
Java实现
public class InsertSort { public static void sort(Comparable[] c) { for (int i = 1; i < c.length; i ++) { // 假设前i个元素已经排好序, 用第i+1个元素,依次与前面的比较 for ( int j = i; j > 0; j--) { Comparable next = c[j]; Comparable pre = c[j - 1]; if (next.compareTo(pre) < 0) { Comparable tmp = next; c[j] = pre; c[j-1] = tmp; } else { break; } } System.out.println(String.format("第%s次插入, 结果为: %s", i, Arrays.toString(c))); } } public static void main(String[] args) { Integer[] test = {5, 7, 9, 6, 4, 3, 1}; sort(test); } } |
输入: [5, 7, 9, 6, 4, 3, 1]
输出:
第1次插入, 结果为: [5, 7, 9, 6, 4, 3, 1]
第2次插入, 结果为: [5, 7, 9, 6, 4, 3, 1]
第3次插入, 结果为: [5, 6, 7, 9, 4, 3, 1]
第4次插入, 结果为: [4, 5, 6, 7, 9, 3, 1]
第5次插入, 结果为: [3, 4, 5, 6, 7, 9, 1]
第6次插入, 结果为: [1, 3, 4, 5, 6, 7, 9]