快速排序是最坏情况时间复杂度为O(n2),最优时间复杂度为O(nlgn),平均时间复杂度为O(nlgn)。
最坏情况出现在每一层划分子问题时,分别包含了n-1个元素和0个元素,此时的时间复杂度为O(n2),与插入排序相同;在数组已经有序时其时间复杂度依旧为O(n2),此时插入排序的时间复杂度为O(n)。
快速排序使用了分治思想,将数组A[p..r]划分为两个子数组A[p..q-1]和A[q+1..r],使A[p..q-1]中的元素都小于A[q],A[q+1..r]中的元素都大于A[q],不断进行递归这个过程,直到数组中只存在一个元素,此时,数组已经有序。
QUICKSORT(A,p,r)
if p < r //当数组中只剩一个元素时,退出递归,数组已经有序
q = PARTITION(A,p,r)
QUICKSORT(A,p,q-1) //对小于等于A[q]的元素进行递归
QUICKSORT(A,q+1,r) //对大于A[q]的元素进行递归
划分数组:
PARTITION(A,p,r)
x = A[r] //将A[r]选取为“主元”
i = p - 1 //因为可能不存在小于等于A[r]的元素,所以i的值由p-1开始
for j = p to r-1
if A[j] <= x
i = i + 1 //小于等于x的元素增加一个
exchange A[i] with A[j] //i+1后,i指向了一个大于x的元素,此时,j指向的是一个小于等于x的元素,交换这两个元素的位置,使其符合规则
exchange A[i+1] with A[r] //r前所有元素比较完后,将A[r]置于正确位置:两个子数组的交界处
return i + 1 //返回"主元"的位置
在整个for循环过程中,数组被划分为了四个区域:
1.小于等于A[r],元素位于[p,i]
2.大于等于A[r],元素位于(i,j)
3.未划分区域 [j,r)
【《算法导论》读书笔记--快速排序】4.主元 [r,r]
Demo:
#include
#include
using namespace std;
void swap(int *a,int *b)
{
int tmp;
tmp = *a;
*a = *b;
*b = tmp;
}int partition(int *A,int p,int r)
{
int i = p - 1;
int x = A[r];
for(int j = p;
j < r;
j++)
{
if(A[j] <= x)
{
i++;
swap(A[j],A[i]);
}
}
swap(A[r],A[i+1]);
return (i + 1);
}void quicksort(int *A,int p,int r)
{
if( p < r )
{
int q = partition(A,p,r);
quicksort(A,p,q-1);
quicksort(A,q+1,r);
}
}int main()
{
int A[10];
for(int i = 0;
i < 10;
i++)
cin>>A[i];
quicksort(A,0,9);
for(int i = 0;
i < 10;
i++)
cout << A[i] <<" ";
getchar();
system("pause");
return 0;
}
推荐阅读
- 人工智能|干货!人体姿态估计与运动预测
- 分析COMP122 The Caesar Cipher
- 技术|为参加2021年蓝桥杯Java软件开发大学B组细心整理常见基础知识、搜索和常用算法解析例题(持续更新...)
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- Python机器学习基础与进阶|Python机器学习--集成学习算法--XGBoost算法
- 数据结构与算法|【算法】力扣第 266场周赛
- 数据结构和算法|LeetCode 的正确使用方式
- leetcode|今天开始记录自己的力扣之路
- 人工智能|【机器学习】深度盘点(详细介绍 Python 中的 7 种交叉验证方法!)
- 网络|简单聊聊压缩网络