排序 (a) 冒泡排序、选择排序、插入排序
一、基础知识
排序的稳定性：
在排序的过程中，数组中相等元素的相对顺序保持不变，则排序是稳定的。
原地排序算法：
在原始输入数组上完成的排序算法，没有申请额外的空间。
二、冒泡排序
步骤：
比较两个相邻的元素，将值大的元素交换到右边。
（1）第一次比较：首先比较第一和第二个数，将小数放在前面，将大数放在后面。
（2）比较第2和第3个数，将小数放在前面，大数放在后面。
......
（3）如此继续，直到比较到最后的两个数，将小数放在前面，大数放在后面，重复步骤，直至全部排序完成。
（4）在上面一趟比较完成后，最后一个数一定是数组中最大的一个数，所以在比较第二趟的时候，最后一个数是不参加比较的。
（5）在第二趟比较完成后，倒数第二个数也一定是数组中倒数第二大数，所以在第三趟的比较中，最后两个数是不参与比较的。
（6）依次类推，每一趟比较次数减少依次。
时间复杂度分析：
若有n个元素，第一轮比较n-1次，第二轮比较n-2次，第三轮比较n-3次... 则，一共需要比较 n-1+n-2+n-3+...+1次，共 
次比较。所以，时间复杂度是：
。
代码实现：
package com.douma.line;
import java.util.Arrays;
public class BubbleSorter {
public void bubbleSort(int[] data) {
//一定要注意边界条件
if (data == null || data.length <= 1) return;
for (int round = 1; round <= data.length; round++) {
//外层循环： 控制冒泡的轮数
int compareTimes = data.length - round;
//每一轮比较的次数 为 数组的长度 减去 轮数
for (int i = 0; i < compareTimes; i++) {
// 比较相邻的两元素,只有大于，才会交换；小于或等于 就不做任何处理。
if (data[i] > data[i+1]) {
int tmp = data[i];
data[i] = data[i+1];
data[i+1] = tmp;
}
}
}
}
public static void main(String[] args) {
int[] data = new int[]{12,23,36,9,24,42};
new BubbleSorter().bubbleSort(data);
//System.out.println(data);
//提醒：这样打印出来的是数组的地址。
/*
* Arrays.toString() 的作用是用来很方便地输出数组
* */
System.out.println(Arrays.toString(data));
}
}
冒泡排序的特点：
- 空间复杂度是
，是原地排序算法。 - 冒泡排序是稳定的排序算法。
冒泡排序优化：
当在一轮中没有元素交换，就不需要交换了。这样可以减少比较次数。
public void bubbleSort(int[] data) {
if (data == null || data.length <= 1) return;
for (int round = 1; round <= data.length; round++) {
boolean hasSwap = false; // 优化
//外层循环： 控制冒泡的轮数
int compareTimes = data.length - round;
//每一轮比较的次数 为 数组的长度 减去 轮数
for(int i = 0; i < compareTimes; i++) {
// 比较相邻的两元素,只有大于，才会交换；小于或等于 就不做任何处理。
if (data[i] > data[i+1]) {
int tmp = data[i];
data[i] = data[i+1];
data[i+1] = tmp;
hasSwap = true; // 发生交换，设为true
}
}
if (!hasSwap) break;
// 如果不发生交换，说明该数组已经有序了。
// 既然有序了，跳出round循环，不需要进行其他轮的比较了。
// 这样优化可以减小比较的次数
}
}
三、选择排序
选择排序，从头至尾扫描序列，找出最小的一个元素，和第一个元素交换，此时最小的元素就到了排序后正确的位置。接着从剩下的元素中再找一个最小的元素，和第二个元素交换，此时第二小的元素也排到正确的位置。然后再在剩下的元素中选择一个最小的元素，继续这种选择和交换方式。直到剩下的数列的选择范围为0，那么得到一个有序序列。
步骤：
数组data中6个元素：23，12，42，36，9，24。
第一轮：
i= 0，将最小数值元素索引设为i，即minNumIndex=0。
j 从1 开始遍历，将data[j]与data[minNumIndex]进行比较，并更新minNumIndex 的值。
直到j遍历结束，此时minNumIndex = 4。将data[4] 与 data[i] 进行交换。
第二轮：
i= 1，最小数值元素索引（minNumIndex）=1。
j 从2 开始遍历，将data[j]与data[minNumIndex]进行比较，并更新minNumIndex 的值。
直到j遍历结束，此时minNumIndex = 1。将data[1] 与 data[i] 进行交换。
第三轮：
i= 2，最小值索引（minNumIndex）=2。
j 从3 开始遍历，将data[j]与data[minNumIndex]进行比较，并更新minNumIndex 的值。
直到j遍历结束，此时minNumIndex = 4。将data[4] 与 data[i] 进行交换。
第四轮：
i= 3，最小值索引（minNumIndex）=3。
j 从4 开始遍历，将data[j]与data[minNumIndex]进行比较，并更新minNumIndex 的值。
直到j遍历结束，此时minNumIndex = 5。将data[5] 与 data[i] 进行交换。
第五轮：
i= 4，最小值索引（minNumIndex）=4。
j 从5 开始遍历，将data[j]与data[minNumIndex]进行比较，并更新minNumIndex 的值。
直到j遍历结束，此时minNumIndex = 5。将data[5] 与 data[i] 进行交换。
第六轮：
i= 5，最小值索引（minNumIndex）=5。只有一个元素，不用比较了。
时间复杂度分析：
若有n个元素，第一轮比较n-1次，第二轮比较n-2次，第三轮比较n-3次... 则，一共需要比较 n-1+n-2+n-3+...+1次，共 次比较。所以，时间复杂度是： 。
代码实现：
public void sort(int[] data) {
if (data == null || data.length <= 1) return;
for (int i = 0; i < data.length; i++) {
// 控制选择排序的轮数
// （i元素之前保证有序）找到 [i, n) 中的最小元素所在的索引
// i 是未排序元素中的第一个，j是第二个
int minNumIndex = i;
for (int j = i + 1; j < data.length; j++) {
if (data[j] < data[minNumIndex]) {
minNumIndex = j;
}
}
// 将 data[i]和最小元素进行交换
swap(data, i, minNumIndex);
}
}
选择排序的特点：
- 空间复杂度是 ，是原地排序算法。
- 选择排序是不稳定的排序算法。
如：5，8，5，2，9
当第一个5和2交换时，这两个5的相对顺序变了。
所以选择排序是不稳定的，也因此它的使用场景非常受限。
四、插入排序
拿到未排序区间的第一个元素，将与对排序区间的每个元素进行比较，插入。直到未排序区间的元素为空。（简单来说就是将一个元素插入到已经排好的序列中，插入之后序列依然有序。）
步骤：
data数组有6个元素：34 ，8 ，64 ，51 ，32 ，21 。每轮处理一个元素，每个元素都需要处理，有6个元素，所以需要6轮。
第一轮：
从第一个元素开始，i=0 ，j=0，自己和自己比，不用交换。此轮结束。
即：34 ，8 ，64 ，51 ，32 ，21 。
第二轮：
从第二个元素开始，i=1，需要把data[1]插入到前面有序的数组中。
此时指针j：j从i开始遍历，并比较data[j] 和data[j-1]，如果data[j-1] > data[j]，两者交换。j向前移动，此时data[j]无法与前一个元素进行比较，不用交换，此轮结束。
即：8 ，34 ，64 ，51 ，32 ，21 。
第三轮：
从第三个元素开始，i=2，需要把data[2]插入到前面有序的数组中。
此时指针j：j从i开始遍历，并比较data[j] 和data[j-1]，即比较64和34。不用交换。此轮结束。
即：8 ，34 ，64 ，51 ，32 ，21 。
第四轮：
从第四个元素开始，i=3，需要把data[3]插入到前面有序的数组中。
比较51和64，交换两者。比较51和34，不用交换。此轮结束。
即：8 ，34 ，51 ，64 ，32 ，21 。
第五轮：
从第五个元素开始，i=4，需要把data[4]插入到前面有序的数组中。
比较32和64，交换。比较32和51，交换。比较32和34，交换。比较32和8，不用交换，此轮结束。
即：8 ，32，34 ，51 ，64 ，21 。
第六轮：
从第六个元素开始，i=5，需要把data[5]插入到前面有序的数组中。
比较21和64，交换。比较21和51，交换。比较21和34，交换。比较21和32，交换。比较21和8，不交换。此轮结束。
即：8 ，21，32，34 ，51 ，64 。
时间复杂度分析：
- 遍历一遍数组，时间复杂度为O(n)。
- 每轮遍历需要将一个元素插入到有序数组的正确位置，这个插入过程的最坏时间复杂度为O(n)。
所以时间复杂度为： 。
public void sort1(int[] data) {
if (data == null || data.length <= 1) return;
// 插入排序的轮数, 可以从第二个元素开始
for (int i = 1; i < data.length; i++) {
// 注意这里的j不能等于0
for (int j = i; j > 0; j--) {
if (data[j] < data[j - 1]) {
swap(data, j , j - 1);
} else {
break;
}
}
}
}
选择排序的特点：
- 空间复杂度是 ，是原地排序算法。
- 插入排序是稳定的排序算法。
插入排序的优化：
将原来代码中的“交换” 变成“赋值”。来减少元素的访问次数。
public void sort(int[] data) {
if (data == null || data.length <= 1) return;
// 插入排序的轮数
for (int i = 1; i < data.length; i++) {
int tmp = data[i];
int j;
for (j = i; j > 0; j--) {
if (tmp < data[j - 1]) {
// 将较大的元素总是向右移动
data[j] = data[j - 1];
} else {
break;
}
}
// 找到 i 对应的元素需要插入的位置
data[j] = tmp;
}
}
五、 比较三种算法的性能：
public class SortCompare {
private static Random random = new Random();
private static int[] genData(int n) {
int[] data = new int[n];
for (int i = 0; i < n; i++) {
data[i] = random.nextInt();
}
return data;
}
private static long time(String sortType, int[] data) {
long start = System.currentTimeMillis();
if (sortType.equals("bubble")) new BubbleSort().sort(data);
else if (sortType.equals("selection")) new SelectionSort().sort(data);
else if (sortType.equals("insertion")) new InsertionSort().sort(data);
return System.currentTimeMillis() - start;
}
// 生成k个长度为n的数组
private static long manyTimesSort(String sortType, int n, int k) {
long totalTime = 0;
for (int i = 0; i < k; i++) {
totalTime += time(sortType, genData(n));
}
return totalTime;
}
public static void main(String[] args) {
double t1 = manyTimesSor("bubble",1000,100);
double t2 = manyTimesSor("selection",1000,100);
double t3 = manyTimesSor("insertion",1000,100);
System.out.println(t1 / t2); // t1 > t2
System.out.println(t2 / t3); // t2 > t3
// 结论：插入排序性能最好，其次是选择排序，最后是冒泡排序
// 选择排序不稳定，冒泡排序的性能不太好。
// 所以用插入排序最好。
}
}
上一篇： iOS 版气泡排序
下一篇： # 冒泡排序算法的原理和实现