快速排序（一次排序）
一. 基本思想
当然这里也是目前为止我们能够接触到的最快的算法
图形表示如下
我们将最左边的值称为 “KEY 值”
这里我们从右边开始 依次往左遍历 如果找到小于KEY下标数 就交换它们的值
并且将key的下标赋值给right
之后我们从左边开始 依次往右遍历 如果找到大于KEY下标的数 就交换它们的值
并且将key的下标赋值给left
我们想想看 什么时候结束呢？
当然是left < right 的时候
二. 代码表示
我们这里有代码表示如下
int quicksort1(int* arr, int left, int right) { // assert(arr) assert(arr); // 设置左右两个小人 int keyi = left; int tmp = 0; while (left<right) { // 右边的士兵先开始走 直到遇到小于key值 我们交换它们的位置以及下标 while (left<right && arr[right] >= arr[keyi]) { right--; } tmp = arr[right]; arr[right] = arr[keyi]; arr[keyi] = tmp; keyi = right; // 右边的士兵走完了 然后左边的士兵开始走 while (left < right && arr[left]<=arr[keyi]) { left++; } tmp = arr[left]; arr[left] = arr[keyi]; arr[keyi] = tmp; keyi = left; } return keyi; }
我们来看看结果是什么样子的
快速排序（整体排序）
一. 基本思路
既然我们每次可以将整个数组可以分成两个部分
我们可以将数组的左边和右边继续进行快速排序
这里我们进行递归
二. 递归思路
既然我们已经决定了要进行递归了
那么我们想想看极限条件是什么？
是不是要左值大于等于右值的时候 只剩下一个值了 是不是肯定有序了
所以说有极限条件如下
// assert assert(arr); // 考虑边界条件 if (left>=right) { return; }
那么我们接下来就可以考虑左右两边怎么排了
我们来看看我们的数组
是不是从左到右分成三个部分
分别是
left~keyi-1；
keyi；
keyi+1~right；
所以说我们就可以有以下代码
quicksort(arr, 0, keyi - 1); quicksort(arr, keyi + 1,right);
之后我们来试试 整体排序的效果咋样
可以完成
优化
我们假设 排序的数组就是一个有序的
quicksort(arr, 0, keyi - 1); quicksort(arr, keyi + 1,right);
那么我们这里左边就排完了 开始排右边
像这样子
那这样是不是我们的算法就变得很复杂了啊
到这里的时间复杂度就变成了O（N^2）
那么针对有序数组的这个问题 我们能不能做出一个优化呢？
答案是有的
那就是三数取中
我们找到最左边 左右边 还有中间三个数中的中间值
然后让这个值和left交换
之后再进行排序 是不是就能变成很优了啊
那么我们这里再来写个函数 三数取中
int GetMinIndex(int* arr, int left, int right) { // assert assert(arr); int mid = (left + right) / 2; // 返回其中的中间值 if (arr[left]>=arr[right]) { if (arr[right]>=arr[mid]) { return mid; } else if (arr[mid] >= arr[left]) { return left; } else { return right; } } else // arr[right] > arr[left] { if (arr[left]>arr[mid]) { return left; } else if (arr[mid] > arr[right]) { return right; } else { return mid; } } }
之后再来写进函数里面
void quicksort(int* arr, int left, int right) { // assert assert(arr); // 三数取中 int mid = GetMinIndex(arr, left, right); int tmp = 0; // 改变key值 tmp = arr[left]; arr[left] = arr[mid]; arr[mid] = tmp; // 考虑边界条件 if (left>=right) { return; } // 如果不满足边界条件开始排序了 int keyi = quicksort1(arr, left, right); // 开始排序数组的左边和右边 quicksort(arr, 0, keyi - 1); quicksort(arr, keyi + 1,right); }
我们来看看运行结果
可以完美运行
双指针法实现一趟快排
我们这里首先设置两个指针
一个pre 指向第一个元素 也就是key值
一个cur指向最后的元素
类似这样子
比如说 cur走到了2 然后2小于key值
这个时候pre就得++ 然后交换cur和pre指向的值
当cur走到7 9 下面的时候就直接++ 不做任何操作
如果说cur的坐标大于 数组的元素-1的时候结束循环
这个时候我们再将prev和key值交换一下就可以了
最后结果表示如下
快排的非递归实现
这个时候就要用到我们的数据结构 栈了
我们首先先将我们需要排序的数组左右下标传递进去
之后我们开始进行一个循环操作
如果栈不为空 我们就执行这个循环
首先我们以这个数组的左边为例
通过第一趟排序 可以将整个数组分为三个部分
我们将中值设置为div
那么左边就是
left~ div-1
右边就是
div+1~right
那么到这里我们的终止条件就很好判断了
left<div-1
div+1<right
那么这里我们先将 0 ~ 9 出栈
之后将它分割的两边
6~9
0~4 依次进栈
如图
再之后我们将0~4进行出栈
判断有没有达到边界条件再进行压栈
整体代码表示如下
以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够
不吝赐教 在评论区或者私信指正 博主一定及时修正
那么大家下期再见咯
