简单插入排序-java实现

1、算法描述

将数据分为两部分，一部分为已排序列，另一部分为待排序列，插入排序每一步将待排序列中的一个元素插入到已排序列中的合适位置，

使得已排序列依然有序，直到待排序列没有可用数据，此时已排序列即为排序结果。

2、实现代码

package com.k6k4.example.sort;

import java.util.Random;

public class InsertSort {
    public static void main(String[] args) {

        //随机生成10个样本数据
        Random random = new Random(System.currentTimeMillis());
        int[] data = new int[11];
        for (int i = 1; i <= 10; i++) {
            data[i] = random.nextInt(100);
        }

        System.out.println("--before sort--");
        print(data);
        //sort
        sort(data);
        System.out.println("--after sort--");
        print(data);
    }

    /**
     * 排序算法
     *
     * @param data
     */
    public static void sort(int[] data) {
        int i, j;
        for (i = 2; i <= 10; i++) {
            data[0] = data[i];
            for (j = i - 1; j > 0; j--) {
                if (data[j] > data[0]) {
                    data[j + 1] = data[j];
                } else {
                    break;
                }
            }

            data[j + 1] = data[0];
        }

    }

    /**
     * 打印数组
     *
     * @param data
     */
    public static void print(int[] data) {
        StringBuffer sb = new StringBuffer();
        sb.append("[");
        for (int i = 1; i < data.length; i++) {
            if (i > 1) {
                sb.append(",");
            }
            sb.append(data[i]);
        }
        sb.append("]");
        System.out.println(sb);
    }
}

输出结果：

--before sort--
[89,7,54,68,6,49,51,64,6,33]
--after sort--
[6,6,7,33,49,51,54,64,68,89]

3、算法复杂度

O(n^2)