首页  

冒泡选择和插入排序比较     所属分类 algo 浏览量 135
时间复杂度(最好 最坏 平均) 空间复杂度 稳定性 

冒泡  n    n^2  n^2  原地排序  稳定
选择  n^2  n^2  n^2  原地排序  非稳定
插入  n    n^2  n^2  原地排序  稳定

虽然3者 平均时间复杂度都是 n^2 ,不过这个 忽略了系数、常数和低阶参数
jdk 数组排序 元素个数少于某个阈值时 使用 插入排序

private static final int INSERTION_SORT_THRESHOLD = 47;
If the length of an array to be sorted is less than this constant, 
insertion sort is used in preference to Quicksort.

本机测试 1000个元素 100次 

insertSortTime=169
selectSortTime=449
bubbleSortTime=1135

insertSortTime=167
selectSortTime=449
bubbleSortTime=1131

insertSortTime=170
selectSortTime=444
bubbleSortTime=1119



测试代码 https://gitee.com/dyyx/hellocode/tree/master/src/algo/sort/BubbleSelectInsertSort.java import java.time.LocalDateTime; import java.util.Random; public class BubbleSelectInsertSort { public static void bubbleSort(int[] arr) { int len = arr.length; if (len <= 1) { return; } for (int i = 0; i < len; ++i) { // 退出冒泡的标志 boolean flag = false; for (int j = 0; j < len - i - 1; ++j) { if (arr[j] > arr[j + 1]) { // 交换 int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; // 表示有数据交换 flag = true; } } // 没有数据交换,提前退出 if (!flag) break; } } public static void selectSort(int[] arr) { int len = arr.length; if (len <= 1) { return; } for (int i = 0; i < len; i++) { int index = i; for (int j = i; j < len; j++) { // 找出每一轮的最小值 if (arr[j] < arr[index]) { index = j; } } if (index == i) { continue; } // 和已排序部分的后一个位置进行交换 int temp = arr[i]; arr[i] = arr[index]; arr[index] = temp; } } public static void insertSort(int[] arr) { int len = arr.length; if (len <= 1) { return; } for (int i = 0; i < len; i++) { int temp = arr[i]; // 从有序数组的最后一个元素开始往前找 int j = i - 1; while (j >= 0) { if (arr[j] > temp) { // 如果当前元素大于temp,则后移 arr[j + 1] = arr[j]; j--; } else { break; } } // 插入 arr[j + 1] = temp; } } private static final Random RAND = new Random(); private static int[] getTestArr() { int[] arr = {3,2,1,9,7,8,7,5,6}; return arr; } private static int[] genTestArr(int count,int bound) { if(count<=0) { count = 100; } if(bound<=0) { bound = 100; } int[] arr = new int[count]; for(int i=0;i<count;i++) { arr[i] = RAND.nextInt(bound); } return arr; } private static void printArr(int[] arr) { StringBuilder sb = new StringBuilder(); for(int i=0;i<arr.length;i++) { sb.append(arr[i]).append(" "); } System.out.println(sb.toString()); } public static void swap(int[] a, int i, int j){ int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void shuffle(int[] arr) { int length = arr.length; for ( int i = length; i > 0; i-- ){ int randInd = RAND.nextInt(i); swap(arr, randInd, i - 1); } } private static void runTest(int[] arr,int count) { long start = System.currentTimeMillis(); for(int i=0;i<count;i++) { shuffle(arr); bubbleSort(arr); } long end = System.currentTimeMillis(); long bubbleSortTime = end - start; start = System.currentTimeMillis(); for(int i=0;i<count;i++) { shuffle(arr); selectSort(arr); } end = System.currentTimeMillis(); long selectSortTime = end - start; start = System.currentTimeMillis(); for(int i=0;i<count;i++) { shuffle(arr); insertSort(arr); } end = System.currentTimeMillis(); long insertSortTime = end - start; System.out.println("insertSortTime="+insertSortTime); System.out.println("selectSortTime="+selectSortTime); System.out.println("bubbleSortTime="+bubbleSortTime); } public static void main(String[] args) throws Exception { int[] arr = getTestArr(); printArr(arr); bubbleSort(arr); printArr(arr); arr = getTestArr(); selectSort(arr); printArr(arr); arr = getTestArr(); insertSort(arr); printArr(arr); // arr = genTestArr(20,10); printArr(arr); insertSort(arr); printArr(arr); shuffle(arr); printArr(arr); System.out.println("start test \n\n"); final int COUNT1 = 999; final int COUNT2 = 1000; arr = genTestArr(1000,100); for(int i=0;i<COUNT1;i++) { runTest(arr,COUNT2); System.out.println(LocalDateTime.now()+","+i+"\n"); } } }

上一篇     下一篇
算法精粹 经典计算机科学问题的Python实现 关键术语

二叉树的几个重要性质

关于数学的名言

金庸小说人物英文名

希尔排序

快速排序