当前位置:网站首页>排序第三节——交换排序(冒泡排序+快速排序+快排的优化)(5个视频讲解)
排序第三节——交换排序(冒泡排序+快速排序+快排的优化)(5个视频讲解)
2022-08-09 06:50:00 【学习追求高效率】
2.3 交换排序
基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。
2.3.1冒泡排序 O(N^2)(稳定)
*** 视频讲解
冒泡排序
冒泡排序
【冒泡排序的特性总结】
- 冒泡排序是一种非常容易理解的排序
- 时间复杂度:O(N^2)
- 空间复杂度:O(1)
- 稳定性:稳定
模板
/** * 冒泡排序 * 时间复杂度:O(N^2) * 针对优化后的代码,时间复杂度在有序的情况下: * O(n) * 空间复杂度:O(1) * 稳定性:稳定 的排序 * 插入 * @param array */
public static void bubbleSort(int[] array) {
for (int i = 0; i < array.length-1; i++) {
boolean flg = false;
for (int j = 0; j < array.length-1-i; j++) {
if(array[j] > array[j+1]) {
swap(array,j,j+1);
flg = true;
}
}
if(!flg) {
break;
}
}
}
2.3.2 快速排序 O(N * logN)(稳定)
模板
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int[] array, int left, int right) {
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}
private static int partitionHoare(int[] array,int start,int end) {
int i = start;//事先存储好start下标
int key = array[start];
while (start < end) {
//为啥取等号? 不然就死循环了
while (start < end && array[end] >= key) {
end--;
}
while (start < end && array[start] <= key) {
start++;
}
swap(array,start,end);
}
swap(array,start,i);
return start;
}
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int[] array, int left, int right) {
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}
private static int partitionHoare(int[] array,int start,int end) {
int i = start;//事先存储好start下标
int key = array[start];
while (start < end) {
//为啥取等号? 不然就死循环了
while (start < end && array[end] >= key) {
end--;
}
while (start < end && array[start] <= key) {
start++;
}
swap(array,start,end);
}
swap(array,start,i);
return start;
}
上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。
区间按照基准值划分为左右两半部分的常见方式
1. Hoare版(右,左两两交换)
***视频讲解
快速排序+Hoare法
- Hoare版
2. 挖坑法
*** 视频讲解
快速排序挖坑法
3. 前后指针
写法一:
写法二:
2.3.2 快速排序优化
***视频讲解
快速排序的优化
1. 三数取中法选key
//三数取中:解决递归深度问题 基本上 有了三数取中 你的待排序序列 基本上每次都是二分N*logn
int index = midNumIndex(array,left,right);
swap(array,left,index);
/** * 三数取中 * @param array * @param left * @param right * @return */
private static int midNumIndex(int[] array,int left,int right) {
int mid = (left+right) / 2 ;
// 3 < 9
if(array[left] < array[right]) {
if(array[mid] < array[left]) {
return left;
}else if(array[mid] > array[right]) {
return right;
}else {
return mid;
}
}else {
//9 > 3
if(array[mid] < array[right]) {
return right;
}else if(array[mid] > array[left]){
return left;
}else {
return mid;
}
}
}
2. 当区间跨度小于8的时候,就用插入排序
if(right - left + 1 <= 7) {
//使用直接插入排序
insertSort2(array,left,right);
return;
}
public static void insertSort2(int[] array,int start,int end) {
//此函数是插入排序
for (int i = start+1; i <= end; i++) {
int tmp = array[i];
int j = i-1;
for(;j >= start;j--) {
//加上等号 就是不稳定
if(array[j] > tmp) {
array[j+1] = array[j];
}else {
break;
}
}
array[j+1] = tmp;
}
}
private static void quick(int[] array,int left,int right) {
//这里代表 只要一个节点了 大于号:有可能没有子树 有序 逆序
if(left >= right) {
return;
}
//小区间使用直接插入排序: 主要 优化了递归的深度
if(right - left + 1 <= 7) {
//使用直接插入排序
insertSort2(array,left,right);
return;
}
//三数取中:解决递归深度问题 基本上 有了三数取中 你的待排序序列 基本上每次都是二分N*logn
int index = midNumIndex(array,left,right);
swap(array,left,index);
int pivot = partitionHoare(array,left,right);
quick(array,left,pivot-1);
quick(array,pivot+1,right);
}
/** * 时间复杂度:O(N*logN) 【理想-》每次都是均分待排序序列】 * 最慢:O(n^2) 数据有序或者逆序 * 空间复杂度: * 最好:O(logN) * 最坏:O(N) 当N 足够大的时候 ,递归的深度就大 * 稳定性:不稳定 * @param array */
public static void quickSort1(int[] array) {
quick(array,0,array.length-1);
}
2.3.3 快速排序非递归
***视频讲解
非递归实现快速排序
/** * 非递归实现 快速排序 * @param array */
public static void quickSort(int[] array) {
Stack<Integer> stack = new Stack<>();
int left = 0;
int right = array.length-1;
//三数取中:解决递归深度问题 基本上 有了三数取中 你的待排序序列 基本上每次都是二分N*logn
int index = midNumIndex(array,left,right);
swap(array,left,index);
int pivot = partitionHole(array,left,right);
if(pivot > left+1) {
stack.push(left);
stack.push(pivot - 1);
}
if(pivot < right-1) {
stack.push(pivot + 1);
stack.push(right);
}
while (!stack.empty()) {
right = stack.pop();
left = stack.pop();
index = midNumIndex(array,left,right);
swap(array,left,index);
pivot = partition(array,left,right);
if(pivot > left+1) {
stack.push(left);
stack.push(pivot - 1);
}
if(pivot < right-1) {
stack.push(pivot + 1);
stack.push(right);
}
}
}
2.3.4 快速排序总结
边栏推荐
- Singleton DCL (double check the lock) full han mode and the hungry
- The working principle of the transformer (illustration, schematic explanation, understand at a glance)
- pycharm环境包导入到另外一个环境
- 单例模式
- C语言实现顺序栈和链队列
- 错误:为 repo ‘oracle_linux_repo‘ 下载元数据失败 : Cannot download repomd.xml: Cannot download repodata/repomd.
- 事务总结
- Leetcode 70 stairs issues (Fibonacci number)
- io.lettuce.core。RedisCommandTimeoutException命令超时
- TCP段重组PDU
猜你喜欢
The solution that does not work and does not take effect after VScode installs ESlint
当酷雷曼VR直播遇上视频号,会摩擦出怎样的火花?
idea中PlantUML插件使用
分布式理论
leetcode 之盛水问题
使用百度EasyDL实现智能垃圾箱
C# 利用iTextSharp画PDF
6 states of a thread
【Oracle 11g】Redhat 6.5 安装 Oracle11g
Teach you how to make the Tanabata meteor shower in C language - elegant and timeless (detailed tutorial)
随机推荐
The solution that does not work and does not take effect after VScode installs ESlint
codeforces Valera and Elections (这思维题是做不明白了)
当酷雷曼VR直播遇上视频号,会摩擦出怎样的火花?
线程的6种状态
Teach you how to make the Tanabata meteor shower in C language - elegant and timeless (detailed tutorial)
Variable used in lambda expression should be final or effectively final报错解决方案
Silently start over, the first page is also a new page
线程池总结
The AD in the library of library file suffix. Intlib. Schlib. Pcblib difference
集合内之部原理总结
买口罩(0-1背包)
安装flask
Distributed id generator implementation
字节也开始缩招了...
jvm线程状态
e-learning summary
分布式id 生成器实现
像天才一样思考:如何培养自己的创造力?
leetcode:55. 跳跃游戏
先序遍历,中序遍历,后序遍历,层序遍历