经典排序有以下几种：
O(n²)：冒泡排序、插入排序、选择排序 基于比较
O(nlogn)：归并排序、快速排序 基于比较
O(n)：捅排序、计数排序、基数排序
如何分析排序算法
1，最好时间复杂度，最坏时间复杂度，平均时间复杂度
2，时间复杂度的系数，常数，低阶
3，比较次数和交换次数
排序算法内存消耗
排序算法稳定性
冒泡排序
public static void sort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
Utils.exchange(arr, j, j + 1);
}
}
}
}
可以优化如果没有交换跳出循环
public static void sort2(int[] arr) {
for (int i = 0; i < arr.length; i++) {
boolean flag = false;//提前退出排序标志
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
Utils.exchange(arr, j, j + 1);
flag = true;//表示有数据交换
}
}
if (!flag)//没有数据交换提前退出
break;
}
}
冒泡排序性能分析
是原地排序算法么？
冒泡排序只涉及到相邻两个元素交换，空间复杂度是O(1)，所有是原地排序
是稳定排序算法么？
冒泡排序中只有比较才会交换顺序，所以我们控制在相等时不交换元素顺序即可，所以冒泡排序是稳定排序算法
时间复杂度是多少？
最好的情况下数据为有序，我们只需要进行一次冒泡即可，时间复杂度为O(n)
最坏的情况下数据为倒序，我们需要进行n次冒泡操作，时间复杂度为O(n²)
平均时间复杂度为O(n²)
插入排序
public static void sort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int value = arr[i];
int j = i - 1;
//查找插入位置
for (; j >= 0; j--) {
if (arr[j] > value) {
arr[j + 1] = arr[j];
} else {
break;
}
}
arr[j+1] = value;//插入数据
}
}
插入排序性能分析
是原地排序算法么？
空间复杂度是O(1)，是原地排序
是稳定排序算法么？
对于相同的值，我们可以把后面出现的元素插入到之前出现元素的后面，所以是稳定排序算法
时间复杂度是多少？
最好的情况下数据为有序，我们只需要遍历一次，时间复杂度为O(n)
最坏的情况下数据为倒序，相当于每次都是在数组的第一个位置插入元素，时间复杂度为O(n²)
平均时间复杂度为O(n²)
选择排序
//选择排序：从待数组中选择出一个最小放入排序数组中以此类推
public static void sort(int[] arr) {
int minIndex;
for (int i = 0; i < arr.length; i++) {
minIndex = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
Utils.exchange(arr, i, minIndex);
}
}
选择排序性能分析
是原地排序算法么？
空间复杂度是O(1)，是原地排序
是稳定排序算法么？
不是稳定的排序算法
时间复杂度是多少？
最好的情况下数据为有序，复杂度为O(n²)
最坏的情况下数据为倒序，复杂度为O(n²)
平均时间复杂度为O(n²)
