首先最基本的排序-冒泡排序
- 首先我们先了解冒泡排序的执行流程
- 从头开始比较每一对相邻的元素,如果第1个元素大于第2个元素,则交换他们的位置 执行完第一轮后,最后一个元素就是最大的元素
- 忽略"1"中找到的最后一个元素,重复执行1操作,直到全部元素有序
具体代码如下
protected void sort() {
for (int end = array.length - 1; end > 0; end--) {
for (int begin = 1; begin <= end; begin++) {
// if (array[begin] < array[begin - 1]) {
if (cmp(begin, begin - 1) < 0) {
swap(begin, begin - 1);
}
}
}
}
优化1
- 如果当前的数组已经完全有序了,就可以提前终止冒泡排序,避免不必要的开销
for (int end = array.length - 1; end > 0; end--) {
boolean sorted = true; //用来判断是否已经有序了
for (int begin = 1; begin <= end; begin++) {
// if (array[begin] < array[begin - 1]) {
if (cmp(begin, begin - 1) < 0) {
swap(begin, begin - 1);
sorted = false;
}
}
if (sorted) break;//如果有序提前跳出比较
}
优化2
- 如果数组的尾部已经局部有序,就可以记录最后一次交换的位置,减少比较次数
protected void sort() {
for (int end = array.length - 1; end > 0; end--) {
int sortedIndex = 1;//用来记录最后一次交换位置,初始值为小于等于1的值 是为了如果已经完全有序了 end-- 直接跳出排序
for (int begin = 1; begin <= end; begin++) {
// if (array[begin] < array[begin - 1]) {
if (cmp(begin, begin - 1) < 0) {
swap(begin, begin - 1);
sortedIndex = begin;
}
}
end = sortedIndex;
}
}
时间空间复杂度分析 稳定性
- 最坏平均时间复杂度:O(n^2)
- 最好时间复杂度:O(n)
- 空间复杂度:O(1) 属于In-Place (原地算法)
- 稳定性:稳定
