插入排序

package DataStructure;

/**
 * Created by robert on 2016/12/18.
 * 插入排序
 */
public class InsertSort extends BaseSort{

    public static void main(String[] args) {
        int[] arr = createArr(10000);
        printArr(arr);
        long startTime = System.nanoTime();
        insertSort(arr);
        System.out.println("共计耗时:"+String.valueOf(System.nanoTime()-startTime));
        printArr(arr);
    }

    public static void insertSort(int[] nums){
        int[] sortedArr = null;
        for(int i=1;i<nums.length;i++){
            sortedArr = new int[i+1];
            for(int j=0;j<=i;j++){
                if(nums[i]<nums[j]){
                    int temp = nums[j];
                    sortedArr[j] = nums[i];
                    nums[i] = temp;
                } else{
                    sortedArr[j] = nums[j];
                }
            }
            for(int k=0;k<sortedArr.length;k++){
                nums[k] = sortedArr[k];
            }
        }
    }
}

package DataStructure;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Created by robert on 2016/12/18.
 */
public class BaseSort {

    /**
     * 生成乱序数组
     * @param n
     * @return
     */
    protected static int[] createArr(int n){
        List<Integer> list = new ArrayList<Integer>(n);
        for(int i=1;i<=n;i++){
            list.add(i);
        }
        Collections.shuffle(list);
        int[] nums = new int[n];
        for(int i=0;i<nums.length;i++){
            nums[i] = list.get(i);
        }
        System.out.println("初始化数组结束");
//        printArr(nums);
        return nums;
    }

    protected static void printArr(int[] numArr) {
        for(int num:numArr){
            System.out.print(num+",");
        }
        System.out.println();
    }
}

插入排序在最好的情况下是O（n）的，在最坏的情况下是O(n²)