一、算法概述
1.1 算法分类
十种常见排序算法可以分为两大类：
比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
1.2 算法复杂度
1.3 相关概念
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
二、冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
2.1 算法描述
- 1、比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 2、对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 3、针对所有的元素重复以上的步骤，除了最后一个；
- 4、重复步骤1~3，直到排序完成。
2.2 动图演示
2.3 排序过程
下面以数列{20,40,30,10,60,50}为例，演示它的冒泡排序过程(如下图)。
我们先分析第1趟排序
- 当i=5,j=0时，a[0]<a[1]。此时，不做任何处理！
- 当i=5,j=1时，a[1]>a[2]。此时，交换a[1]和a[2]的值；交换之后，a[1]=30，a[2]=40。
- 当i=5,j=2时，a[2]>a[3]。此时，交换a[2]和a[3]的值；交换之后，a[2]=10，a[3]=40。
- 当i=5,j=3时，a[3]<a[4]。此时，不做任何处理！
- 当i=5,j=4时，a[4]>a[5]。此时，交换a[4]和a[5]的值；交换之后，a[4]=50，a[3]=60。
于是，第1趟排序完之后，数列{20,40,30,10,60,50}变成了{20,30,10,40,50,60}。此时，数列末尾的值最大。
根据这种方法：
- 第2趟排序完之后，数列中a[5...6]是有序的。
- 第3趟排序完之后，数列中a[4...6]是有序的。
- 第4趟排序完之后，数列中a[3...6]是有序的。
- 第5趟排序完之后，数列中a[1...6]是有序的。
第5趟排序之后，整个数列也就是有序的了。
2.4 代码实现
2.4.1 冒泡排序——常规版
/**
* @Author: huangyibo
* @Date: 2022/2/19 22:37
* @Description: 冒泡排序 常规版
* 文字描述(以升序为例)
* 1、依次比较数组中相邻两个元素大小，若 arr[j] > arr[j + 1], 则交换两个元素,
* 两两都比较一遍则称为一轮冒泡，结果是让最大的元素排到最后
* 2、重复以上步骤, 直到整个数组有序
*/
public class BubbleSort {
public static <E extends Comparable<E>> void bubbleSort(E[] arr){
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if(arr[j].compareTo(arr[j + 1]) > 0){
swap(arr, j,j + 1);
}
}
}
}
/**
* 交换数组元素
* @param arr
* @param i
* @param j
* @param <E>
*/
private static <E> void swap(E[] arr, int i, int j) {
E temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2.4.2 冒泡排序——优化版1
- 用boolean变量isSwapped记录是否发生位置交换，没有发生元素交换，则证明数组有序，直接跳出循环。
/**
* @Author: huangyibo
* @Date: 2022/2/19 22:37
* @Description: 冒泡排序 优化版1
* 用boolean变量isSwapped记录是否发生位置交换，
* 没有发生元素交换，则证明数组有序，直接跳出循环
*
* 有利于有序数组排序，完全有序数组直接变为O(n)
*/
public class BubbleSort {
public static <E extends Comparable<E>> void bubbleSort(E[] arr){
for (int i = 0; i < arr.length - 1; i++) {
//是否发生了交换
boolean isSwapped = false;
for (int j = 0; j < arr.length - 1 - i; j++) {
if(arr[j].compareTo(arr[j + 1]) > 0){
swap(arr, j,j + 1);
isSwapped = true;
}
}
//没有发生元素交换，则证明数组有序
if(!isSwapped){
break;
}
}
}
/**
* 交换数组元素
* @param arr
* @param i
* @param j
* @param <E>
*/
private static <E> void swap(E[] arr, int i, int j) {
E temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2.4.3 冒泡排序——优化版2
- 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可。
/**
* @Author: huangyibo
* @Date: 2022/2/19 22:37
* @Description: 冒泡排序 优化版2
* 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，
* 如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可
*
* 有利于有序数组排序，完全有序数组直接变为O(n)
*/
public class BubbleSort {
public static <E extends Comparable<E>> void bubbleSort(E[] arr){
for (int i = 0; i < arr.length - 1; ) {
//最后一次发生元素交换的索引位置
int lastSwappedIndex = 0;
for (int j = 0; j < arr.length - 1 - i; j++) {
if(arr[j].compareTo(arr[j + 1]) > 0){
swap(arr, j,j + 1);
lastSwappedIndex = j + 1;
}
}
//外层循环遍历赋值,
// 如果是有序数组的话，i = arr.length - 1 则直接终止了外层循环
i = arr.length - 1 - lastSwappedIndex;
}
}
/**
* 交换数组元素
* @param arr
* @param i
* @param j
* @param <E>
*/
private static <E> void swap(E[] arr, int i, int j) {
E temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2.4.4 冒泡排序——优化版3(外层for无限循环写法)
- 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可。
/**
* @Author: huangyibo
* @Date: 2022/2/19 22:37
* @Description: 冒泡排序 优化版3(外层for无限循环写法)
* 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，
* 如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可
*
* 有利于有序数组排序，完全有序数组直接变为O(n)
*/
public class BubbleSort {
public static <E extends Comparable<E>> void bubbleSort(E[] arr){
//循环比较次数
int cycles = arr.length - 1;
for ( ; ; ) {
//最后一次发生元素交换的索引位置
int lastSwappedIndex = 0;
for (int j = 0; j < cycles; j++) {
if(arr[j].compareTo(arr[j + 1]) > 0){
swap(arr, j,j + 1);
lastSwappedIndex = j;
}
}
//最后一次元素交换位置的索引为下一轮循环的最大次数
cycles = lastSwappedIndex;
//循环比较次数小于等于0，则证明数组有序
if(cycles <= 0){
break;
}
}
}
/**
* 交换数组元素
* @param arr
* @param i
* @param j
* @param <E>
*/
private static <E> void swap(E[] arr, int i, int j) {
E temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2.4.5 冒泡排序——优化版4(外层while循环写法)
- 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可。
/**
* @Author: huangyibo
* @Date: 2022/2/19 22:37
* @Description: 冒泡排序 优化版4(外层while循环写法)
* 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，
* 如果这个值小于等于0，表示整个数组有序，直接退出外层循环即可
*
* 有利于有序数组排序，完全有序数组直接变为O(n)
*/
public class BubbleSort {
public static <E extends Comparable<E>> void bubbleSort(E[] arr){
//循环比较次数
int cycles = arr.length - 1;
while (cycles > 0){
//最后一次发生元素交换的索引位置
int lastSwappedIndex = 0;
for (int j = 0; j < cycles; j++) {
if(arr[j].compareTo(arr[j + 1]) > 0){
swap(arr, j,j + 1);
lastSwappedIndex = j;
}
}
//最后一次元素交换位置的索引为下一轮循环的最大次数
cycles = lastSwappedIndex;
}
}
/**
* 交换数组元素
* @param arr
* @param i
* @param j
* @param <E>
*/
private static <E> void swap(E[] arr, int i, int j) {
E temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
