快速排序

• 快速排序（一次排序）
• • 一. 基本思想
  • 二. 代码表示
• 快速排序（整体排序）
• • 一. 基本思路
  • 二. 递归思路
• 优化

快速排序（一次排序）

一. 基本思想

当然这里也是目前为止我们能够接触到的最快的算法

图形表示如下

我们将最左边的值称为 “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// 右边的士兵先开始走 直到遇到小于key值 我们交换它们的位置以及下标while (left= 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;}

我们来看看结果是什么样子的

快速排序（整体排序）

一. 基本思路

既然我们每次可以将整个数组可以分成两个部分

我们可以将数组的左边和右边继续进行快速排序

这里我们进行递归

二. 递归思路

既然我们已经决定了要进行递归了

那么我们想想看极限条件是什么？

是不是要左值大于等于右值的时候 只剩下一个值了 是不是肯定有序了

所以说有极限条件如下

	// assertassert(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)
{// assertassert(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)
{// assertassert(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);}

我们来看看运行结果

可以完美运行

以上就是本篇博客的全部内容啦 由于博主才疏学浅 所以难免会出现纰漏 希望大佬们看到错误之后能够

不吝赐教 在评论区或者私信指正 博主一定及时修正

那么大家下期再见咯