快速排序算法
2023-09-11 14:19:25 时间
排序算法的思想呢,我看了许多,觉得比较生动的是:挖坑填坑再分治。
- 把第一个数作为基准数(也叫枢轴)挖出来,哨兵j从右往左找出比它小或者等于的数,把它挖出来,填进刚刚的坑里
- 填了一个坑,也新挖了一个坑,哨兵i从左往右,找出比基准数大的数,又挖出来,填入新的坑里
- 然后又是j继续从右往左……直到i和j相遇
- 相遇了,就把基准数填到最后一个坑里,也就是i和j相遇的位置
- 接下来分治,就是相遇点左边、右边分别快排
void QuickSort(int l,int r){ if(l>=r)return; int i=l,j=r,key=a[i]; while(i<j){ while(a[j]>=key&&i<j) j--; a[i]=a[j]; while(a[i]<=key&&i<j) i++; a[j]=a[i]; } a[i]=key; QuickSort(l, i-1); QuickSort(i+1, r); }
调用:
QuickSort(1,n); //数组a[],长度为n
另一种写法:
int Partition(int A[],int p,int q){ int x=A[p]; int i=p; for(int j=p+1;j<=q;++j) if(A[j]<=x){ ++i; int t=A[i];A[i]=A[j];A[j]=t; } int t=A[i];A[i]=A[p];A[p]=t; return i; } 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); } }
性能分析:
C为比较次数,M为移动次数。
最坏情况:$C_{max}=(n-1)+(n-2)+..+1=n(n-1)/2$,$M_{max}\leq C_{min}$,$O(n^2)$
最好情况:$C_{min}\leq O(nlgn)$,$M_{min}\leq C_{min}$,$O(nlog_2n)$
平均 $ T_{avg}(n)=kn ln(n)$
k为某个常数,n为元素个数。
辅助空间:因为是递归的,所以需要栈。(如果是全局的数组a,就不需要)
最好情况:$O(log_2n)$
最坏情况:$O(n)$
算法改进:
合理选择枢轴:三者取中(选择a[1],a[n]和a[(n+1)/2]的中位数),随机产生。
稳定性:
是非稳定性排序。如2,2',1,排序后是1,2',2。
相关文章
- 利用反射快速给Model实体赋值 使用 Task 简化异步编程 Guid ToString 格式知多少?(GUID 格式) Parallel Programming-实现并行操作的流水线(生产者、消费者) c# 无损高质量压缩图片代码 8种主要排序算法的C#实现 (一) 8种主要排序算法的C#实现 (二)
- 【算法】【排序模块】插入排序和快速排序
- 【转】算法总结-这是一份全面并且详细的排序算法学习指南
- 快速排序算法介绍
- 10大排序算法之七:计数排序【稳定】,复杂度小,不常用计数排序,除非面试官特殊申明
- C#,快速排序算法(Quick Sort)的非递归实现与数据可视化
- 排序算法--梳排序(CombSort)的原理、排序思路及代码示例
- [算法]快速排序,归并排序,堆排序的数组和单链表实现
- 排序算法系列之(一)——选择排序清新脱俗的一面
- 白话经典算法系列之六 快速排序 快速搞定 【转】
- 基于LSD的直线提取算法
- 看动画学算法之:排序-基数排序
- 数据结构 | 排序算法——冒泡排序与快速排序【史上最全】
- 几种简单的排序算法
- 14.2 拓扑排序DFS算法
- 【十大排序算法】超硬核,确定不进来看看?
- 排序算法之快速排序
- 排序算法全家桶(Java实现)