目录
背景
快速排序
复杂度
快速排序的优化
背景
快速排序是图灵奖获得者 Tony Hoare设计提出的
快速排序被誉为20世纪十大算法之一
希尔排序是直接插入排序的升级,属于插入排序
堆排序是简单选择排序的升级,属于选择排序类
快速排序是冒泡排序的升级,属于交换排序类
快速排序是增加了记录的比较和移动的距离,将关键字较大的记录从前面直接移到后面,关键字较小的记录从后边直接移到前面,从而减少了比较次数和移动交换的次数
快排的基本思想是,通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则可以对这两部分记录继续进行排序,以达到整个序列有序的目的

快排的时间复杂度:
在最优的情况下为nlogn
最坏的情况下为n方
平均情况:nlogn
空间复杂度:logn
由于关键字的比较和交换是交换式的,因此,快排是一种不稳定的排序方法
#include
void swap(int k[], int low, int high)
{
int temp;
temp = k[low];
k[low] = k[high];
k[high] = temp;
}
int Partition(int k[], int low, int high)
{
int point;
point = k[low];
while( low < high )
{
while( low < high && k[high] >= point )
{
high--;
}
swap(k, low, high);
while( low < high && k[low]
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?
立即登录/注册


微信扫码登录