插入排序比冒泡排序快在哪里？

问题描述

问 题

1.代码

冒泡排序

/**
 * 找最小数排序1
 * 
 * 总结：冒泡排序，比较N2次，交换N2次。
 * @author Administrator
 *
 */
public class MaoPaoSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] datas = {7,8,9,2,1,3,4,5,6,10};
        
        for(int i=0;i<datas.length;i++){
            System.out.print(datas[i] + ",");
        }
        
        System.out.println();
        
        for(int i=0;i<datas.length;i++){
            for(int j=i+1;j<datas.length;j++){ //总结：每次内循环，找到最小的值。（交换之后，最小的值在最左边）
                //比较
                if(datas[i] > datas[j]){ //比较N2次
                    //交换
                    int temp = datas[i]; //交换N2次
                    datas[i] = datas[j];
                    datas[j] = temp;
                }
            }
        }
        
        for(int i=0;i<datas.length;i++){
            System.out.print(datas[i] + ",");
        }
    }

}

插入排序

/**
 * 找最小数排序3
 * @author Administrator
 *
 */
public class InsertSort {

    /**
     * @param args
     */
    public static void main(String[] args) {
        int[] datas = { 7, 8, 9, 2, 1, 3, 4, 5, 6, 10 };

        for (int i = 0; i < datas.length; i++) {
            System.out.print(datas[i] + ",");
        }

        System.out.println();

        int out,in;
        for (out = 1; out < datas.length; out++) {
            int temp = datas[out]; //初始值都一样
            in = out;
            
            while(in>0 && datas[in-1]>temp){ //每次内循环，右移比基准值大的数据
                datas[in] = datas[in-1];
                in--;
            }
            
            datas[in] = temp; //把基准值插入合适的位置
        }

        for (int i = 0; i < datas.length; i++) {
            System.out.print(datas[i] + ",");
        }
    }

}

2.问题

《java数据结构和算法》上说，插入排序比冒泡排序快一倍，因为在每一趟排序发现插入点之前，平均只有全体数据项的一半真的进行了比较（书上原话，有点不明白）。

一个是内循环是for，一个内循环是while，while怎么就比for快了一倍呢？

解决方案

插入排序那个while(in>0 && datas[in-1]>temp)循环可以提前终止啊！你看http://stackoverflow.com/ques...

这篇关于插入排序比冒泡排序快在哪里？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！