当前位置：网站首页>Quick sort eight sorts (3) 】 【 (dynamic figure deduction Hoare, digging holes, front and rear pointer method)
Quick sort eight sorts (3) 】 【 (dynamic figure deduction Hoare, digging holes, front and rear pointer method)
2022-08-09 09:39:00 【Living_Amethyst】
目录
一、冒泡排序（Bubble Sort）
冒泡排序的原理
从左到右,相邻元素进行比较.每次比较一轮,就会找到序列中最大的一个或最小的一个.这个数就会从序列的最右边冒出来.
- 以从小到大排序为例,
- 比较相邻的元素.如果第一个比第二个大,就交换他们两个.
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数.
- 针对所有的元素重复以上的步骤,除了最后一个.
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较.
- 第一轮比较后,所有数中最大的那个数就会浮到最右边;第二轮比较后,所有数中第二大的那个数就会浮到倒数第二个位置……就这样一轮一轮地比较,最后实现从小到大排序.
什么时候最快
当输入的数据已经是正序时（都已经是正序了,我还需要你冒泡排序吗？）
什么时候最慢
当输入的数据是反序时（写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢？）
算法稳定性
冒泡排序就是把小的元素往前调或者把大的元素往后调.比较是相邻的两个元素比较,交换也发生在这两个元素之间.所以,如果两个元素相等,我想你是不会再无聊地把他们俩交换一下的;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法.
时间复杂度：O(n^2)
空间复杂度：O(1)
代码
public static void bubbleSort(int[] array){
for(int i=0; i< array.length-1 ;i++){
for(int j = 0; j < array.length-1-i;j++){
if(array[j] > array[j+1]){
swap(array,j,j+1);
}
}
}
}优化：避免已经有序的情况下无意义的循环判断
public static void bubbleSort2(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;
}
}
}二、快速排序（Quick Sort）
引言
终于我们的高手要登场了,这个被列为20世纪十大算法之一的快速排序,前面我们介绍的希尔排序相当于直接插入排序的升级,它们同属于插入排序类,堆排序相当于简单选择排序的升级,它们同属于选择排序类.而快速排序其实就是我们前面认为最慢的冒泡排序的升级,它们都属于交换排序类.即它也是通过不断比较和移动交换来实现排序的,只不过它的实现,增大了记录的比较和移动的时间,将关键字较大的记录从前面直接移到后面,关键字较小的记录从后面直接移动到前面,从而减少了总的比较次数和移动交换次数
快速排序算法
快速排序的基本思想是：任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止.
算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）.具体算法描述如下：
- 从数列中挑出一个元素,称为 “基准”（pivot）;
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）.在这个分区退出之后,该基准就处于数列的中间位置.这个称为分区（partition）操作;
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序.
// 假设按照升序对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);
}上述为快速排序递归实现的主框架,发现与二叉树前序遍历规则非常像,在写递归框架时可想想二叉树前序遍历规则即可快速写出来,后序只需分析如何按照基准值来对区间中数据进行划分的方式即可.
将区间按照基准值划分为左右两半部分的常见方式：
1、Hoare版
Hoare法是以快排的创始人Hoare命名的,也是快排最初的实现版本.其基本思想就是用两个指针分别指向待排序数组的开头和结尾.
- 如果我们取头值作为我们的key值,那么我们一定要让右指针先移动
- 如果我们取尾值作为我们的key值,那么我们一定要让左指针先移动
如图,我们取头值为key值
怎样移动and如何找基准
- right指针直到找到小于key的值才停下来
- left指针直到找到大于key的值才停下来
- 将left和right所对应的值进行交换.重复上述过程直到两者相遇
- 相遇后,将key下标的值与相遇处的值交换
- 此时相遇处就是基准
下面用动图演绎一下
代码：
//Hoare法
public static int partitionHoare(int[] array,int low,int high){
int key = low;
while(low < high){
while (low < high && array[high] >= array[key]){
high--;
}
//此时high下标就是要找的数字
while (low < high && array[low] <= array[key]){
low++;
}
//此时low下标就是要找的数字
swap(array,low,high); //low和high下标的元素交换
}
//此时low和high相遇了
swap(array,low,key);
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partition(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}需要注意的是
2.挖坑法
我们需要在key处挖一个坑（把6拿出来存在一个tmp变量里）,形成一个坑位,然后R向左找比6小的放进坑里,就又形成了一个新的坑,然后L向右找,找到比6大的,放进新的坑
我们还是用动图演绎
挖坑法的好处是更容易我们理解,我们根据这个思路写一个用挖坑法的快排
//挖坑法
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partitionHole(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}3、前后指针法
版本1
顾名思义,需要两个指针,一个在前一个在后,分别用cur表示前指针,prev表示后指针,初始时,我们规定cur在prev的后一个位置,这里我们还是选择第一个数为基准值
- prev每次都需要指向从左到它本身之间最后一个小于基准值的数
- 如果cur的值大于基准值,这时只让cur++
- 如果cur指向的位置小于基准值
- 这时我们让prev++
- 判断prev++后是否与cur的位置相等
- 若不相等,则交换cur和prev的值
- 直到cur > R后,我们再交换prev和key,这样基准值的位置也就确定了
下面我们依旧是动图演绎
代码
//前后指针法1
private static int partition(int[] array,int low,int high){
int prev = low;
int cur = low+1;
while (cur <= high){
if(array[cur] < array[low] && array[++prev]!=array[cur]){
swap(array,cur,prev);
}
cur++;
}
swap(array,prev,low);
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partition(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}
版本2
这个写法可能更好理解,但实质是一样的
//前后指针法2
private static int partition2(int[] array,int low,int high){
int d = low+1;
int tmp = array[low];
for(int i = low+1;i <= high; i++){
if(array[i] < tmp){
swap(array,i,d);
d++;
}
}
swap(array,d-1,low);
return d-1;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
int pivot = partition2(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}快速排序的优化
规模较小时的优化
每次递归的时候,数据都是再慢慢变成有序的
当数据量少且趋于有序的时候,我们可以直接使用插入排序进行优化
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
if(right-left+1 <= 10000){ //某个区间内的小规模排序直接插入排序
//进行插入排序
insertSortRange(array,left,right);
return;
}
int pivot = partitionHole(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}
public static void insertSortRange(int[] array,int low, int end){
for(int i = low+1 ; i<=end ;i++){
int tmp = array[i];
int j = i-1;
for(; j >= low ; j--){
if(array[j] > tmp){
array[j+1] = array[j];
}else{
break;
}
}
array[j+1] = tmp;
}
}但是这个优化并没有根本解决 有序情况下 递归深度太深的优化
如果想根本上解决问题,就得尽量让每次划分更均匀
三数取中法
我们用 三数取中法 选key
- 三数取中：头,尾,中间元素中 大小居中 的那一个
再把这个元素和队头元素互换,作为key
我们来看一下的代码
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
//三数取中,找到首,中,尾三个数中 中等大小的数的下标
private static int medianOfThreeIndex(int[] array, int left, int right){
int mid = left + ((right-left)>>>1);
//int mid = (right+left)/2 ;
if(array[left] < array[right]){
if(array[mid] < array[left]){
return left;
}else if(array[mid] > array[right]){
return right;
}else{
return mid;
}
}else{
if(array[mid] < array[right]){
return right;
}else if(array[mid] > array[left]){
return left;
}else{
return mid;
}
}
}
public static void quickSort(int[] array,int left,int right){
if(left >= right) return;
//1.某个区间内的小规模排序直接插入排序【优化的是区间内的比较】
if(right-left+1 <= 10000){
//进行插入排序
insertSortRange(array,left,right);
return;
}
//2.三数取中法【优化的是本身的分割】
int index = medianOfThreeIndex(array,left,right);
swap(array,left,index);
int pivot = partitionHole(array,left,right);
quickSort(array,left,pivot-1);
quickSort(array,pivot+1,right);
}非递归实现快速排序
我们需要用到栈
我们之前是在已经确定基准点之后,对剩余的区间递归进行同样的操作
我们现在创建一个栈,把剩余区间的左、右位置的下标分别放入栈中,如图是已经找到一个基准6的情况
然后弹出栈顶一个元素9给H,再弹出一个栈顶元素6给L,根据新的L和H找到新的基准,再重复上面的操作
代码
//挖坑法
public static int partitionHole(int[] array,int low,int high){
int tmp = array[low];
while(low < high) {
while (low < high && array[high] >= tmp){
high--;
}
array[low] = array[high];
while (low < high && array[low] <= tmp){
low++;
}
array[high] = array[low];
}
array[low] = tmp;
return low;
}
//快速排序（非递归）
public static void quickSortNor(int[] array,int left,int right){
Stack<Integer> stack = new Stack<>();
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.isEmpty()){
right = stack.pop();
left = stack.pop();
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);
}
}
}
快速排序总结
1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(logN)
4. 稳定性：不稳定
边栏推荐
猜你喜欢
【机器学习】网络爬虫实战详解
常用命令之思科常用基础配置
命令行查询数据库
实用小技能：一键获取Harbor中镜像信息，快捷查询镜像
Ontology development diary 04 - to try to understand some aspects of protege
通过程序发送 Gmail 邮件
Anti App so层对抗分析
Redis 回击 Dragonfly：13 年后，Redis 的架构依然是同类最佳
How much do you know about the mobile APP testing process specifications and methods?
mysql简单安装
随机推荐
有返回值的函数
oracle查看表空间占用情况并删除多余表所占空间
6.Map接口与实现类
5.Set接口与实现类
"The camera can't be used" + win8.1 + DELL + external camera + USB drive-free solution
Ontology Development Diary 03 - When debugging is in progress
Tigase插件编写——注册用户批量查询
EndNote使用指南
真·鸡汤文
latex中复杂公式换行等号对齐
字符串
接口测试主要测试哪方面？需要哪些技能？要怎么学习？
命令行查询数据库
Arrays类、冒泡排序、选择排序、插入排序、稀疏数组！
性能测试包括哪些方面？分类及测试方法有哪些？
图表示学习(Graph Representation Learning)笔记
喜迎排名18
免费下载天地图全国基础地理信息矢量数据的一种方法
网络安全入门基础：IP地址
What does the test plan include?What is the purpose and meaning?