插入排序最稳定的排序算法比较的次数等于交换的次数两倍于冒泡排序的速度略快于选择排序

//package com.nowjava;


public class Main {
/**
NowJava.com 提供 
**/

    public static void main(String[] argv) throws Exception {

        int[] arr = new int[] { 34, 35, 36, 37, 37, 37, 67, 68, 69 };

        System.out.println(java.util.Arrays.toString(insertSort(arr)));

    }


    /**

     * insert sort

     * <p/>

     * the most stable sort algorithm

     * <p/>

     * times of comparing equals times of swap

     * <p/>

     * two times as fast as bubble sort

     * <p/>

     * a little faster than select sort

     */

    public static int[] insertSort(int[] arr) {

        int swapCount = 0;

        for (int i = 1; i < arr.length; i++) {

            int cursor = i;

            while (cursor > 0 && arr[cursor - 1] > arr[cursor]) {

                swap(arr, cursor--, cursor);//来自 N o w  J a v a  . c o m

                swapCount++;

            }

        }

        System.out.println("swap count(insert sort): " + swapCount);

        return arr;

    }


    /**

     * swap two element in array

     */

    private