十大经典排序算法之插入排序

插入排序

插入排序(Insertion Sort)的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入。

1 算法步骤

将第一待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)

2 动图演示

插入排序

java code

import org.junit.Test;

/**
 * 直接插入排序
 * 关键:在前面已经排好序的序列中找到合适的插入位置
 * 步骤:
 * 1. 从第一个元素开始,该元素可以认为已经排好序。
 * 2. 取出下一个元素,在已经排好序的元素序列中从后往前扫描进行比较。
 * 3. 如果该元素(已排序) 大于新元素,则将该元素移到下一位置。
 * 4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置。
 * 5. 将新元素插入到该位置后面。
 * 6. 重复步骤2~5
 */
public class InsertionSort {

    @Test
    public void InsertionSort() {
        int[] data = {34, 21, 20, 18, 54, 76, 38};

        if (data == null || data.length < 2) {
            return;
        }

        int insertData;// 待排序元素
        int j;// 已排序列表下标
        for (int i = 1; i < data.length; i++) {
            insertData = data[i];// 要插入的变量
            for (j = i - 1; j >= 0 && insertData < data[j]; j--) {
                data[j + 1] = data[j];
                //System.out.print("   " + j);
            }
            data[j + 1] = insertData;
        }
    }

    @Test
    public void InsertionSort2() {
        int[] data = {34, 21, 54, 18, 23, 76, 38};
        for (int i = 0; i < data.length - 1; i++) {
            for (int j = i + 1; j > 0; j--) {
                if (data[j - 1] <= data[j])
                    break;
                int temp = data[j];
                data[j] = data[j - 1];
                data[j - 1] = temp;
            }           
        }
    }
}