冒泡选择和插入排序比较
所属分类 algo
浏览量 768
时间复杂度(最好 最坏 平均) 空间复杂度 稳定性
冒泡 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 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
上一篇
下一篇
算法精粹 经典计算机科学问题的Python实现 关键术语
二叉树的几个重要性质
关于数学的名言
金庸小说人物英文名
希尔排序
快速排序