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

编程入门行业动态更新时间:2024-10-22 08:37:46

本文介绍了插入排序比冒泡排序快在哪里？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！问题描述

问题

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