Java算法学习之路---直接插入排序

浏览: 76 发布日期: 2016-08-18 分类: intellij-idea

刚想写写插入排序算法,突然发现有点生疏,百度了一下,了解其基本思想之后,就开始coding了。

直接插入排序算法思路是:
待排序记录 R1,R2,… ,Rn–1, Rn
第一步:将无序表打第一个元素作为一个有序表。
第二步:将R2加入到有序表中,使有序表依旧有序
.........
第 n 步: (R1,R2,… ,Rn–1), Rn.
以此类推。
直接插入排序算法的时间复杂度,最好的情况是待排序记录是有序的,O(N),最坏打情况是记录从大到小排列,O(N2)。

贴出我的代码

    //这是我写的一个排序方法和输出方法
   public static void sort(int[] data) {
        for (int index = 1; index <= data.length - 1; index++) {
            int temp = data[index];
            int j = index - 1;
            for (; j >= 0 && temp < data[j]; j--) {
                data[j + 1] = data[j];
            }
            data[j + 1] = temp;
        }
    }


    public static void print(int[] data) {
        for (int out : data) {
            System.out.print(out + "\t");
        }
        System.out.println();
    }

以下是用一个测试类来测试结果

package DirectInsert;

/**
 * Created by linxs on 16-6-14.
 */
public class TestSort {
    public static void main(String[] args) {
        int[] data = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
        Sort.print(data);
        Sort.sort(data);
        Sort.print(data);
    }
}

代码比较简单,就不多做赘述了,最后看运行结果。

返回顶部