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

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

欢马劈雪     最近更新时间:2020-01-02 10:19:05

391
提示:您可在线编辑运行本教程的实例 - 运行实例,去试试!
插入排序最稳定的排序算法比较的次数等于交换的次数两倍于冒泡排序的速度略快于选择排序


//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 
展开阅读全文