排序算法 #4 再讲插入排序

题目解析TOPIC ANALYSIS学校的老师给同学们按身高排队时，有两种做法。第一种是让同学们自己来按身高排队，即同学甲看到前面的同学乙比自己高，他俩交换下位置。交换位置之后，如果同学甲，发现前面的同学丁还是比自己高，他和同学丁再次交换位置，直到他前面那位同学的身高比自己低。上一节插入排序的代码思路就是这样的。第二种方法是这样的，老师让同学甲出队，然后老师看到前一位同学乙的身高，高于同学甲，则让同学乙后退一位站在同学甲之前的位置；接着，继续看前一位同学丁的身高是否高于同学甲，如果是，则让同学丁后退一位站在同学乙之前所在的位置。此时，如果发现前一位同学的身高低于同学甲，则让同学甲，站在同学丁之前的位置。
接下来，以数组{4, 5, 3, 1, 2} 为例，按第二种排队的方法进行讲解。这里默认从小到大排序。初始状态是这样的。即已排序区间的元素是4和5，未排序区间的元素是3、1、2。首先，将未排序区间的元素3复制一份，接着看已排序区间的元素5。因为元素5大于元素3。因此，元素5移动到元素3之前所在的位置。接着看已排序区间的元素4。同理，由于已排序区间元素4大于元素3。因此，元素4移动到元素5之前所在的位置。这时，已排序区间已没有元素，因此将元素3移动到元素4之前所在的位置，即将元素3插入了合适的位置。重复上述的步骤，即可将未排序区间剩余的元素插入到合适的位置。
02代码实现CODE

public void insertionSortPro(int[] nums) {    for(int i = 1; i < nums.length; i++) {        // 将元素nums[i]复制一份        int value = nums[i];        // 寻找元素nums[i]的插入位置        int j = i;        for(; j > 0; j--) {            if (nums[j-1] - value > 0) {                nums[j] = nums[j-1];            } else {                break;            }        }        nums[j] = value;    }}

更多相关文章

随机推荐