排序算法 #3 插入排序

题目解析TOPIC ANALYSIS接下来，以数组{4, 5, 3, 1, 2} 为例进行讲解。这里默认从小到大排序。对于该数组，初始，已排序区间元素是4，未排序区间的元素是5、3、1、2。然后，定义变量j，指向未排序区间的第一个元素5。接着将元素5和已排序区间的元素4，即变量j-1所指向的元素比较。5大于4，将元素5放在已排序区间末尾。此时，已排序区间的元素为4、5。接着，考察未排序区间的元素3，变量j所指向的元素。将其与已排序区间的元素5做比较，3小于5。因此，两个元素交换位置。接着，拿元素3和已排序区间的元素4做比较，3小于4。因此，两个元素交换位置。这时，元素3处于数组第一个位置，因此已将元素3插入合适的位置。元素3插入合适的位置之后，已排序区间的元素有3、4、5，而未排序区间的元素有1和2。对于未排序区间的元素，重复上述的步骤，最后就会将元素从小到大排列。
02代码实现CODE

public void insertionSort(Comparable[] arr) {    for (int i = 1; i < arr.length; i++) {        for (int j = i; j >0; j--) {            if (arr[j].compareTo(arr[j-1]) < 0) {                swap(arr, j, j - 1);            }else {                break;            }        }    }}
private void swap(Object[] arr, int i, int j) {    Object temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;}

更多相关文章

随机推荐