八大排序算法(4)-插入排序

插入排序

1.直接插入排序的算法思路：

• （1） 设置监视哨r[0]，将待插入纪录的值赋值给r[0]；
• （2） 设置开始查找的位置j；
• （3） 在数组中进行搜索，搜索中将第j个纪录后移，直至r[0].key≥r[j].key为止；
• （4） 将r[0]插入r[j+1]的位置上。

2.Java代码实现：

package com.ustc.sort;

import java.util.Arrays;

/** 
* @author 王聪
* @version 创建时间：2017年3月19日 下午10:52:34 
* 类说明 
*/
public class InsertSort {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = {3,2,5,6,7};
        System.out.println(Arrays.toString(InsertSort(a)));
    }
    
    /**
     * 插入排序
     * @param 传入数组  
     * @return 排序后的数组
     */
    public static int[] InsertSort(int[] a) {
        
        for (int i = 1; i < a.length; i++) {
            int temp = a[i];
            int current = i;
            // 如果当前插入值小于已经排序好的值，往前继续修改
            while (current > 0 && temp < a[current-1]) {
                a[current] = a[current-1];
                current--;
            }
            a[current] = temp;
        }
        
        return a;
    }

}