C++_快速排序
2020-02-16 16:01:05来源:博客园 阅读 ()
C++_快速排序
快速排序:二十世纪十大算法之一 !
快速排序的基本实现
快速排序是一种基于交换的高效排序算法,它采用了分治法的思想。步骤如下:
- 从数列中选出一个数作为基准数(枢轴,Pivot)
- 将数组进行划分(Partition),将比基准数大的元素移至枢轴右侧,将比基准数小的元素移至枢轴左侧。
- 对左右两区间分别进行第二步的划分操作,知道每个子区间只有一个元素。
快排最重要的步骤就是划分了(Partition)。划分的过程用通俗的语言讲就是“挖坑”和“填坑”。
图片较小,请原谅
代码:
int partition(int arr[], int left, int right) //找基准数进行划分
{
int low = left + 1; //区间下端
int high = right; //区间上端
int pivot = left; //枢轴下标
int cur = pivot+1; //存储位置下标
for(int i=low; i<=high; i++) //从下端到上端的遍历
{
if(arr[i] < arr[pivot])
{
swap(arr[i], arr[cur]); //交换现在的值和存储位置的值
cur++; //将存储位置变为下一位
}
}
swap(arr[pivot], arr[cur-1]); //将枢轴移至数组正确位置
return cur-1; //返回枢轴位置
}
void quick_sort(int arr[], int left, int right)
{
if (left >= right)
return;
int mid = partition(arr, left, right); //获取枢轴位置
quick_sort(arr, left, mid - 1); //下端区间递归
quick_sort(arr, mid + 1, right); //上端区间递归
}
时间复杂度分析
快排的时间复杂度在最坏情况下是 O(n2),平均的时间复杂度是 O(n log n)。
怎么理解呢?其实很简单。假设数列中有n个数,则遍历一次的时间复杂度为 O(n),需要遍历至少 log (n + 1)次,最多 n次。
+Q1:为什么最少是 log (n + 1)次?
+A1:快速排序是采用分治法进行遍历的,所以可以看成一棵二叉树,它遍历的次数就是二叉树的深度。而根据二叉树的定义,它的深度至少为 log (n + 1)。因此快速排序的遍历次数至少是 log (n + 1)次。
+Q2:为什么最多是 n次遍历?
+A2:这个应该比较好理解。仍然将快速排序看作一棵二叉树,二叉树的最大深度为 n。所以快速排序的遍历次数最多是 n次。
快速排序的稳定性
快速排序是不稳定的算法,它不满足稳定排序算法的定义。 算法稳定性:假设在数列中存在 a[i] = a[j],若在排序之前,a[i] 在 a[j] 前面,并且排序后,a[i]仍然在 a[j]前面,则这个排序是稳定的!
That's all!Thank you for watching !
快速排序优化已更新!传送门
原文链接:https://www.cnblogs.com/Hello-World-Blog/p/12318017.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
下一篇:母牛的故事
- C++ 转换函数搭配友元函数 2020-06-10
- C++ 自动转换和强制类型转换(用户自定义类类型) 2020-06-10
- C++ rand函数 2020-06-10
- C++ 友元函数 2020-06-10
- C++ 运算符重载 2020-06-10
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash