分类信息网站建设,在wordpress中 怎么把主题删掉,哪家网站做的比较好,完整的网页设计代码引言
排序算法c实现系列第6弹——快速排序
文章末尾还有本菜已实现的其他排序算法文章的链接。不过#xff0c;排序算法这个系列还没更完#xff0c;争取本周末搞完#xff01;之后还会有堆排序、桶排序等的代码实现#xff0c;感兴趣的佳人可以点个赞收藏#xff…引言
排序算法c实现系列第6弹——快速排序
文章末尾还有本菜已实现的其他排序算法文章的链接。不过排序算法这个系列还没更完争取本周末搞完之后还会有堆排序、桶排序等的代码实现感兴趣的佳人可以点个赞收藏如果我有幸获得佳人们一个关注感激涕零呜呜呜呜呜呜呜呜...
算法介绍
快速排序Quick Sort是一种常见且高效的排序算法它和归并排序算法一样都是基于分治法Divide and Conquer的思想。快速排序的核心思想是选择一个基准元素将数组分成两部分使得左边的元素都小于等于基准元素右边的元素都大于等于基准元素然后再对左右两部分分别进行递归排序最终实现整个数组的排序。
算法步骤
下面是快速排序的主要步骤 选择基准元素从待排序数组中选择一个基准元素。通常选择第一个元素、最后一个元素或者中间元素作为基准元素。在本文中我们选择第一个元素为基准元素。 分区操作将数组重新排列将小于基准元素的所有元素移到基准元素的左边将大于基准元素的所有元素移到基准元素的右边基准元素本身则放置在最终的位置上。这个操作称为分区Partition操作。 比如说 有子数组a[p:r]下标从p到r。以a[p]为基准元素将a[p:r]划分成3段a[p:q-1]a[q]和a[q1:r]使a[p,q-1]中任意一个元素小于等于a[q],而a[q1:r]中任何一个元素大于等于a[q],下标q在划分过程中确定 分区操作的具体过程可以看代码和下方的图片。这里简单描述令 i 指向序列最左侧数据不算基准元素j 指向最右侧数据。 i 自前往后或者说自左往右寻找大于基准元素的值找到后停止查找 j 自后往前自右往左寻找小于基准元素的值找到后停止 将 arr[i] 与 arr[j] 交换。 交换完毕后重复步骤1、2、3直到分区操作完成 递归排序对分区后的左右两个子数组进行递归排序。对左子数组和右子数组分别重复步骤1和步骤2直到子数组的大小为1或者0此时子数组已经有序。接上边的例子即通过递归调用快速排序算法分别对a[p:q-1]和a[q1:r]进行排序
具体举例展示假设有数组a[] {4,8,7,1,3,5,6,2} 以第一个元素a[0]为基准元素可以得到a[q]4; a[p: q-1][1,2,3]; a[q1:r][7,5,6,8]下图是具体过程展示建议拿该图用作代码的辅助理解 时间复杂度
快速排序的平均时间复杂度为 O(nlogn)最坏情况下的时间复杂度为O(n^2)最好情况下的时间复杂度为O(nlogn)。
最坏的情况出现在序列已按递增或递减顺序排列即数组已经有序。条件每次选序列中第一个元素为基准元素
最好的情况出现在每次选择的基准元素都能将数组分为两个 n/2 区域再进行递归。
同时快速排序是一种原地排序算法不需要额外的辅助空间。
代码实现
#includebits/stdc.h
using namespace std;
templatetypename T
int partition(T arr[], int l, int r) {int i l, j r 1;T key arr[l];// 记忆边界问题一定要小心while (true) {//ir 没有原因假如有则ir可进入循环待下一轮i为r1可能出现数组越界while (arr[i] key i r) {} // 两个while循环中与key比较都不加原因见代码下方 while (arr[--j] key) {}if (i j) break; // 等号 必须有如果a[j]起初刚好是小于key的而a[i]一路找过来没找到大于key的最后停在a[j]处swap(arr[i], arr[j]);}arr[l] arr[j];arr[j] key;return j;
}
templatetypename T
void quick_sort(T arr[], int l, int r) {// 思路是先按大小交换获得pilot的下标从而好将问题分解为两部分if (l r) {int k partition(arr, l, r);quick_sort(arr, l, k - 1);quick_sort(arr, k 1, r);}}int main() {int arr[] {61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62};int len (int) sizeof(arr) / sizeof(*arr);quick_sort(arr, 0, len - 1);for (int i 0; i len; i) {cout arr[i] ;}cout endl;float arrf[] {17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.7, 5.4};int lenf sizeof(arrf) / sizeof(*arrf);quick_sort(arrf, 0, lenf - 1);for (int i 0; i lenf; i) {cout arrf[i] ;}return 0;
}while循环等号解释
在快速排序的分区操作中加等号可能导致出现问题的原因是在找到小于等于基准值的元素时如果加了等号则可能会导致相等的元素被交换从而影响排序的稳定性。快速排序是一种不稳定的排序算法意味着相等元素的相对位置在排序后可能会改变加上等号可能会导致相等元素的顺序被打乱。
举个例子假设原始数组为[2, 3, 2, 1]如果在分区操作中加上等号即将arr[i] key改为arr[i] key那么在分区操作后可能会得到[2, 1, 2, 3]这样的结果相等的元素2的相对位置发生了改变。而如果不加等号则可能会得到[1, 2, 2, 3]这样的结果保持了相等元素的相对位置不变。
因此为了保证快速排序的稳定性一般会选择不加等号的方式来实现分区操作。
运行结果展示 其他排序算法实现
经典排序算法之希尔排序|c代码实现||什么是希尔排序|如何代码实现 经典排序算法之归并排序|递归和迭代法代码均提供|c代码实现|什么是归并排序|如何代码实现 经典排序算法之希尔排序|c代码实现||什么是希尔排序|如何代码实现
经典排序算法之插入排序|c实现|什么是插入排序|如何代码实现-CSDN博客
排序算法之选择排序|c实现-CSDN博客
经典排序算法之冒泡排序|c代码实现-CSDN博客
