共计 1666 个字符，预计需要花费 5 分钟才能阅读完成。
会通过 Java 语言实现：冒泡排序，插入排序，选择排序，归并排序，快速排序，桶排序，计数排序，基数排序，希尔排序 1.1 执行效率
本文会通过 Java 语言实现：冒泡排序，插入排序，选择排序，归并排序，快速排序，桶排序，计数排序，基数排序，希尔排序
1 分析排序算法 1.1 执行效率
最好的情况，最坏的情况，平均情况时间复杂度
时间复杂度的系数，常数，低阶
比较次数和交换次数
1.2 算法的内存消耗
算法的内存消耗我们可以通过空间复杂度来度量。
原地排序算法，就是特指空间复杂度是 O(1)的排序算法。
1.3 排序算法的稳定性
如果序列中有值相等的元素，经过排序之后，相等元素之间原有的先后顺序不变化。
2 冒泡排序
稳定排序算法，原地排序算法，时间复杂度：O(n^2)
冒泡排序操作相邻的两个数据，每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系。每次冒泡都能选出最大的或者最小的值。
[Java] 纯文本查看 复制代码
?
/**
- 冒泡排序
- @param arr
- @return
*/
public static int[] bubbleSort(int[] arr) {
if (arr == null || arr.length == 0) {return null;}
int n = arr.length;
// 总共需要循环 n 次 每次通过冒泡 得到最大的
for (int i = 0; i < n; i++) {// 因为上一次已经确定了最大的，所以需要遍历的数据就是(n-1)-i
boolean flag = true;
for (int j = 0; j < (n - 1) - i ; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = false;
}
}
// 因为冒泡 如果这次冒泡没有数据没有交换所以数据已经有序了，可以提前退出
if (flag) {break;}
}
return arr;}
3 插入排序
稳定排序算法，原地排序算法，时间复杂度 O(n^2)
根据，把位置的元素，插入在有序的集合中，插入的时候根据元素位置大小。
首先：讲数组中的数据分为两个区间，已排序区间和未排序区间。初始已排序区间只有一个元素就是数组的第一个元素。
[Java] 纯文本查看 复制代码
?
/**
* 插入排序
* @param arr
* @return
*/
public static int [] insertSort(int [] arr){if (arr==null||arr.length==0) {return null;}
int n = arr.length;
// n 从一 1 开始表示 a[0]属于有序序列
for (int i = 1; i < n; 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;
}
return arr;
}4 选择排序
不是稳定排序算法，原地排序算法，时间复杂度是 O(n^2)
每次会从未排序区间中找到最小元素，将其放到已排序区间的末尾
[Java] 纯文本查看 复制代码
?
/**
- 选择排序
- @param arr
- @return
*/
public static int [] selectionSort(int [] arr){
if (arr==null||arr.length==0) {return null;}
int n = arr.length;
int temp = 0;
int minKey = 0;
// 刚开始没有有序区间，所以从 0 开始
for (int i = 0; i < n; i++) {
minKey = i;
// 寻找无序区间最小的元素
for (int j = i+1; j < n; j++) {if (arr[j]<arr[minKey]) {minKey = j;}
}
// 交换位置
temp = arr[i];
arr[i] = arr[minKey];
arr[minKey] = temp;
}
return arr;