一、基础知识
排序的稳定性:
在排序的过程中,数组中相等元素的相对顺序保持不变,则排序是稳定的。
原地排序算法:
在原始输入数组上完成的排序算法,没有申请额外的空间。
二、冒泡排序
步骤:
比较两个相邻的元素,将值大的元素交换到右边。
(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
// 结论:插入排序性能最好,其次是选择排序,最后是冒泡排序
// 选择排序不稳定,冒泡排序的性能不太好。
// 所以用插入排序最好。
}
}