概述
选择排序
特点：强调选择，周期性的选择出最小或最大的数。
算法复杂度：O(N^2)
private static void swap(int[] arr, int i, int minIndex) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
private static void selectSortArr(int[] arr) {
if (Objects.isNull(arr) || arr.length < 2) {
return;
}
/**
* 1. 从i-n个位置选择出最小的数的位置
* 2. 交换i和最小数位置的数
*/
for (int i = 0; i < arr.length; i++) {
int minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
swap(arr, i, minIndex);
}
}
冒泡排序
特点：强调相邻数据比较，周期性的两两比较。
算法复杂度：O(N^2)
private static void bubbleSort(int[] arr) {
if (Objects.isNull(arr) || arr.length < 2) {
return;
}
/**
* 0 ~ n-1上相邻两个数比较，大的往后
*/
int n = arr.length;
for (int i = n - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
}
插入排序
特点：强调把无序的数插入有效的数中，周期性的把无序的数插入有序的数中。
算法复杂度：O(N^2)
private static void insertSort1(int[] arr) {
if (Objects.isNull(arr) || arr.length < 2) {
return;
}
// 0-n, 保证插入之前的有序，插入后也有序
int n = arr.length;
for (int i = 1; i < n; i++) {
// 保证0-j有序，从右往左比较
for (int pre = i - 1; pre >= 0 && arr[pre] > arr[pre + 1]; pre--) {
swap(arr, pre, pre + 1);
}
}
}
为何算法复杂度是O(N^2)呢，实际上如果是一个已经排好序的数组，复杂度只有O(N)，但是如果数组正好是倒叙的则是O(N ^2)。
如果某个算法流程的复杂程度会根据数据状况不同而不同，那么你必须安装最差情况来估计。
很明显，在最差情况下，如果arr长度为N，插入排序的每一步常数操作的数量，还是如等差数列一般，所以，总的常量操作数量= a*(N^2) + b*N+c。
所以插入排查的时间复杂度是O(N^2)。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/99954.html
