- 1MacBook安装Window10教程和坑_mac windows找不到在无人参与应答的
- 2c 语言数据结构冒泡排序算法,C++ 冒泡排序数据结构、算法及改进算法
- 3Linux服务器安全配置基线_检查是否设置口令生存周期
- 4【笔试】美团2023年秋招第1场笔试（后端&数开&软件方向）_美团后端开发笔试
- 5华为内部访谈：凡是溜须拍马的员工，一律拿掉
- 6爬虫爬取百度图片——大量、多张图片_如何爬取百度图片
- 7python日志记录_python 日志
- 8【服务器】在Linux查看运行的Python程序，并找到特定的Python程序_如何linux系统中查找python进程
- 9仅供自用，大学三年收藏夹_淘宝av
- 10每个电子工程师都埋藏着一颗游戏的心
数据结构笔记_14 交换排序（冒泡、快速）_)的核心思想是依次比较两个相邻的元素,如果大小顺序反了,就把他们交换过来,每
赞
踩
一、冒泡排序（Bubble Sorting）
基本思想是：重复地走访过要排序的元素列，依次比较两个相邻的元素，如果顺序（如从大到小、首字母从Z到A）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
演示冒泡过程：
以第一趟为例，有5个位置。
（1）先比较1，2位置上的元素：3<9，符合我们设定的从小到大的顺序，不交换；
（2）再比较2，3位置上的元素：-1<9，不交换；
（3）再比较3，4位置上的元素：9<10，不交换；
（4）再比较4，5位置上的元素：10<20，不交换；
由上：考虑使用一个外层循环控制趟数，一个内层循环控制交换哪两个位置上的元素。外层是在递增的，而内层在递减。所以，内层循环的控制变量可以使用外层循环的控制变量来表示出来。
上面5个数字，需要进行4次比较。仔细看看会发现，从第三趟排序开始，就没有发生过交换了，因为顺序已经符合我们从小到大的规定了。这时候，再往下执行是浪费资源的，所以考虑终止当前循环。怎么终止呢？考虑设置一个标识位，在每一趟执行完交换后，都检查一遍是否发生过交换。若在这一趟中发生了交换，则程序继续执行；若没有，则退出循环。
小结：
1）一共进行 数组的大小-1次 循环。
2）每一趟排序的次数在逐渐的减少。
3）优化：如果在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。
小知识：格式化时间
import java.text.SimpleDateFormat;
import java.util.Date;
public class Main{
public static void main(String[] args){
Date data1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(data1);
System.out.println("排序前的时间是:" + date1Str);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
输出：
核心代码：
public static void bubbleSort(int[] arr) { // 冒泡排序 的时间复杂度 O(n^2) int temp = 0; // 临时变量 boolean flag = false; // 标识变量，表示是否进行过交换 for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { // 如果前面的数比后面的数大，则交换 if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } // System.out.println("第" + (i + 1) + "趟排序后的数组"); // System.out.println(Arrays.toString(arr)); if (!flag) { // 在一趟排序中，一次交换都没有发生过 break; } else { flag = false; // 重置flag!!!, 进行下次判断 } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
完整代码：
package com.huey.sort; import java.text.SimpleDateFormat; import java.util.Date; public class BubbleSort { public static void main(String[] args) { // int arr[] = {3, 9, -1, 10, 20}; // // System.out.println("排序前"); // System.out.println(Arrays.toString(arr)); // 测试一下冒泡排序的速度O(n^2) // 创建要给80000个的随机的数组 int[] arr = new int[80000]; for (int i = 0; i < 80000; i++) { arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数 } // 格式化时间 Date data1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的时间是:" + date1Str); // 测试冒泡排序 bubbleSort(arr); Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序后的时间是=" + date2Str); // System.out.println("排序后"); // System.out.println(Arrays.toString(arr)); // 为了容易理解，把冒泡排序的部分演变过程在下面写出 /* * * // 第二趟排序，就是将第二大的数排在倒数第二位 * * for (int j = 0; j < arr.length - 1 - 1 ; j++) { // 如果前面的数比后面的数大，则交换 if * (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = * temp; } } * * System.out.println("第二趟排序后的数组"); System.out.println(Arrays.toString(arr)); * * * // 第三趟排序，就是将第三大的数排在倒数第三位 * * for (int j = 0; j < arr.length - 1 - 2; j++) { // 如果前面的数比后面的数大，则交换 if (arr[j] * > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } * * System.out.println("第三趟排序后的数组"); System.out.println(Arrays.toString(arr)); * * // 第四趟排序，就是将第4大的数排在倒数第4位 * * for (int j = 0; j < arr.length - 1 - 3; j++) { // 如果前面的数比后面的数大，则交换 if (arr[j] * > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } * * System.out.println("第四趟排序后的数组"); System.out.println(Arrays.toString(arr)); */ } // 将前面的冒泡排序算法，封装成一个方法 public static void bubbleSort(int[] arr) { // 冒泡排序 的时间复杂度 O(n^2) int temp = 0; // 临时变量 boolean flag = false; // 标识变量，表示是否进行过交换 for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { // 如果前面的数比后面的数大，则交换 if (arr[j] > arr[j + 1]) { flag = true; temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } // System.out.println("第" + (i + 1) + "趟排序后的数组"); // System.out.println(Arrays.toString(arr)); if (!flag) { // 在一趟排序中，一次交换都没有发生过 break; } else { flag = false; // 重置flag!!!进行下次判断 } } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
输出结果：
经多次测试，耗费时间大概在7~8s.（因电脑性能而异）
二、快速排序（Quick sort）
1、介绍
快速排序( Quick sort)是对冒泡排序的一种改进。
基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
2、联系：升级版冒泡
为何快速排序不稳定？
答：因为关键字的比较和交换是跳跃进行的。
韩顺平老师采用的以中间数为基准的方法较难理解，代码就直接放在文末。
法一：头基准
下面详解以第一个元素为基准的方法。
第一次比较，以下标为0的元素6为基准（key)，从后往前找比key 小的数字，从下标5、4，一直找到3。下标3的数字3比基准小，所以进行位置交换。
开始第二次比较，这里寻找比key 大的数，需要从前往后找，递增变量i 发现下标1的数据是第一个比大的，所以用下标1的数据12和j 指向的下标3的数据进行交换，结果如下：
上面的逻辑中，左右各执行一次比较后，i 左边的数据都是比6小的了，j 右边的数据都是比6大的了，那么中间的还不确定，怎么办？
再将 j 从后向前移动，找比6小的，再将i 从前向后移动，找比6大的。那么，何时能结束？
当i 和j 碰头了，就意味着不能再继续分组了，一轮就结束了！！！
下面分步骤逐步写代码，并进行优化。
步骤1：左滑、右滑
// arr 为待排序数组，需要对arr[low] ~ arr[high] 段排序【low、high是变化的（递归）】 public static void quickSort(int[] arr, int low, int high) { int i = low;// 只表示起始位置为low，后面还要向右边滑 int j = high;// 只表示起始位置为high，后面还要向左边滑 int key = arr[i];//基准数值 //★★★ while(arr[j] >= key) { j--;//向左滑，直到找到比基准数小的数才退出循环 } int t; t = arr[j]; arr[j] = arr[i]; arr[i] = t; while(arr[i]<=key) { i++;//往右滑，直到找到比基准数大的数才退出循环 } t = arr[i]; arr[i] = arr[j]; arr[j] = t; //第一次执行到这，j滑了一次，i也滑了一次。 //★★★ }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
写到这，代码中两个★★★之间的的代码块，已经进行了一次左滑和一次右滑，i 和 j 碰面了吗？没有！说明还没结束这一轮。我需要的结果是：比key小的数，key，比key大的数 这样的一个结果。
所以左滑、右滑需要重复执行。
用while(true)一直执行两个★★★之间的的代码块吗？不行，会滑过头，当i，j，共同指向下标2的数字7时，while(arr[j] >= key) 条件仍然成立，此时，j - -，就滑过头了。
所以只能用while(i < j)来作为条件，让它俩往中间走。
步骤2：执行完一轮（i，j碰头）
public static void quickSort(int[] arr, int low, int high) { int i = low;// 只表示起始位置为low，后面还要向右边滑 int j = high;// 只表示起始位置为high，后面还要向左边滑 int key = arr[i];//基准数值 //★★★ while(i<j) { while(arr[j] >= key) { j--;//向左滑，直到找到比基准数小的数才退出循环 } int t; t = arr[j]; arr[j] = arr[i]; arr[i] = t; while(arr[i]<=key) { i++;//往右滑，直到找到比基准数大的数才退出循环 } t = arr[i]; arr[i] = arr[j]; arr[j] = t; //第一次执行到这，j滑了一次，i也滑了一次。 } //★★★ }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
此时，我已经得到目标排列：比key小的数，key，比key大的数
步骤3：递归处理
下面，需要再对key 两边的数组进行排序，规则同上，所以，这里使用递归的方式。
public static void quickSort(int[] arr, int low, int high) { int i = low;// 只表示起始位置为low，后面还要向右边滑 int j = high;// 只表示起始位置为high，后面还要向左边滑 int key = arr[i];// 基准数值 while (i < j) { while (arr[j] >= key) { j--;// 向左滑，直到找到比基准数小的数才退出循环 } int t; t = arr[j]; arr[j] = arr[i]; arr[i] = t; while (arr[i] <= key) { i++;// 往右滑，直到找到比基准数大的数才退出循环 } t = arr[i]; arr[i] = arr[j]; arr[j] = t; // 第一次执行到这，j滑了一次，i也滑了一次。 } //★★★ // 对基准左侧的集合重复操作 quickSort(arr, low, i - 1);// key对应的下标是i // 对基准右侧的集合重复操作 quickSort(arr, i + 1, high); //★★★ }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
步骤4：考虑细节，即极限位置。
例1：3， 4，5，6，7，8
一开始 i 指向3，j 指向8。
开始执行：j 一直往左滑，滑到了指向4的位置，4比3大，还得滑。i,j 就重合指向3了。
由于满足：while (arr[j] >= key) 继续执行j - -，就滑过头了。所以需要加条件！
while (arr[j] >= key && i < j)
例2：1，2，3，4，5，8
同例一原理，改进如下：
while (arr[i] <= key && i < j)
例3：递归到key 左边只有一个数3，右边一堆数。
low、high都指向3
由于没有加结束递归的条件，它会一直在调，没有止境。所以我们得加上结束条件：
public static void quickSort(int[] arr, int low, int high) {
if (low >= high) {// 逆向思维，啥时候不停？low小于high的时候鸭！
return;
}
......
}
- 1
- 2
- 3
- 4
- 5
- 6
例4：下标为0上数字2，下标为1上数字3.
其中， i 指向2，j指向3.
满足：while (arr[j] >= key && i < j)
执行：j - -； 此时i , j 重了，都等于2。
往下执行，交换结果还是2。
往下执行，while (arr[i] <= key && i < j)，不满足，往下执行交换，交换结果还是等于2。
例5：
不满足：while (arr[j] >= key && i < j)
往下执行，交换结果是2，3。
往下执行，while (arr[i] <= key && i < j)，满足，执行 i + +，i 和 j 重了，都指向3.
往下执行交换，3跟3交换，结果还是3。
由例4、例5：不加任何条件是可以的。但加上有好处，里面的交换就不执行了，简化了复杂度。
if (i < j) {
int t;
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
- 1
- 2
- 3
- 4
- 5
- 6
最终代码：
// arr 为待排序数组，需要对arr[low] ~ arr[high] 段排序【low、high是变化的（递归）】 public static void quickSort(int[] arr, int low, int high) { if (low >= high) {// 逆向思维，啥时候不停？low小于high的时候鸭！ return; } int i = low;// 只表示起始位置为low，后面还要向右边滑 int j = high;// 只表示起始位置为high，后面还要向左边滑 int key = arr[i];// 基准数值 while (i < j) { while (arr[j] >= key && i < j) { j--;// 向左滑，直到找到比基准数小的数才退出循环 } if (i < j) { int t; t = arr[j]; arr[j] = arr[i]; arr[i] = t; } while (arr[i] <= key && i < j) { i++;// 往右滑，直到找到比基准数大的数才退出循环 } if (i < j) { int t; t = arr[i]; arr[i] = arr[j]; arr[j] = t; } // 第一次执行到这，j滑了一次，i也滑了一次。 } // 对基准左侧的集合重复操作 quickSort(arr, low, i - 1);// key对应的下标是i // 对基准右侧的集合重复操作 quickSort(arr, i + 1, high); }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
速度测试：
八千万个数！
好家伙，果然够快。
基本都在7~8s.
前面的冒泡，才八万个数，也是这速度，可以想见快排确实不戳。
法二：中基准
以中间为基准：
package com.huey.sort; import java.util.Arrays; /** * @author Huey * * 2021年2月18日 下午5:04:44 */ public class QuickSort { public static void main(String[] args) { int[] arr = { 5, 2, 8, 8, 1, 7 }; quickSort(arr, 0, arr.length - 1);// System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr, int left, int right) { int l = left;// 左下标 int r = right;// 右下标 int pivot = arr[(left + right) / 2];// pivot 中轴 int temp = 0;// 临时变量，交换时使用 // while循环的目的：让比pivot 小的放到左边，大的放右边 while (l < r) { // 在pivot 左边一直找，直到找到大于等于pivot 的值，才退出 while (arr[l] < pivot) { l += 1; } // 在pivot 右边一直找，直到找到小于等于pivot 的值，才退出 while (arr[r] > pivot) { r -= 1; } // 如果成立，说明pivot 的左右两边的值，已经为 // 左边全部是小于等于pivot 的值；右边全部是大于等于pivot 的值 if (l >= r) {// 条件成立的话，说明没有找到可交换的值，直接break break; } // 交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; // 如果交换完后发现arr[l] 和 pivot 值相等 r--，前移一下 if (arr[l] == pivot) { r -= 1; } // 如果交换完后发现arr[r] 和 pivot 值相等 l++，后移一下 if (arr[r] == pivot) { l += 1; } // 写这两步，相当于手动干预一个特殊情形。若有一个值和中值pivot相同(例如：5,2,8,8,1,7) // 会发生死循环交换，为防止死循环，在交换后就移动。 } // 退出时，已经完成了一次分割。 // 如果 l == r ，必须l++,r--否则会出现 栈溢出 if (l == r) { l += 1; r -= 1; } // l+=1;r-=1相当于把基准值去掉之后进行递归 // 向左递归 if (left < r) { quickSort(arr, left, r); } // 向右递归 if (right > l) { quickSort(arr, l, right); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
