严蔚敏--快速排序

2024-03-03 05:18
文章标签 快速 排序 严蔚敏

本文主要是介绍严蔚敏--快速排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

快速排序的基本思想:通过一趟快速排序,将待排序记录分成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,已达到整个序列有序。

要点1:枢轴的选择

通常选第一个记录作为枢轴,但是更好的方法是“三者取中”,即比较L.r[s].key,L.r[t].key和L.r[(s+t)/2].key,取三者中关键字取中的记录为枢轴,只要将该记录和L.r[s]互换即可。


要点2:一趟快速排序结束时,即low==high的位置才是枢轴记录最后的位置。


要点3:快速排序的平均时间复杂度为O(nlogn),最坏是O(n*n),最好是O(nlogn). 在所有同数量级(O(nlogn)排序算法中,其平均性能最好。但是,若记录的关键字基本有序或者有序时,快速排序蜕化成起泡排序,时间复杂度为O(n*n).


要点4:快速排序关键字的比较和交换是跳跃进行的,因此快速排序是一种不稳定的排序方法。


要点5:从空间上看,快速排序需要一个栈空间实现递归。若每一趟排序将记录序列均匀的分成长度想接近的两个子序列,则栈的最大深度为LOG2n+1(包括最外层的参量进栈),但是若每一趟排序后,枢轴位置均偏向子序列的一端,则为最坏情况,栈的最大深度为N,所以快速排序的空间复杂度为O(logn)~O(n)。

下面是快速排序的C++实现代码:

#include<iostream>
using namespace std;
int Partition(int arrayNum[],int start,int end){int pivotkey=arrayNum[start]; //用子表的第一个记录作为枢轴记录//循环条件,从表的两端交替地向中间扫描while(start<end){while(start<end && arrayNum[end]>pivotkey)将等于pivokey的元素置于左边区域end--;arrayNum[start]=arrayNum[end];//比枢轴记录小的记录移动到低端while(start<end && arrayNum[start]<=pivotkey)start++;arrayNum[end]=arrayNum[start];//比枢轴记录大的记录移动到高端}arrayNum[start]=pivotkey;//枢轴记录到位return start;//返回枢轴位置
}
void QSort(int arrayNum[],int start,int end){//递归结束条件start>=endif(start<end){int pivotloc=Partition(arrayNum,start,end);//将表一分为2QSort(arrayNum,start,pivotloc-1);//对低子表递归排序,pivotloc是枢轴位置QSort(arrayNum,pivotloc+1,end);//对高子表递归排序}
}void QuickSort(int arrayNum[]){QSort(arrayNum,0,6);
}
int main(){int arrayNum[7]={30,32,9,64,14,17,8};QuickSort(arrayNum);for(int i=0;i<7;i++)cout<<arrayNum[i]<<" ";cout<<endl;return 0;
}

改进后的快读排序算法:

#include<iostream>
using namespace std;
int Partition(int arrayNum[],int start,int end,bool &lowflag,bool &highflag){int pivotkey=arrayNum[start]; //用子表的第一个记录作为枢轴记录//循环条件,从表的两端交替地向中间扫描while(start<end){while(start<end && arrayNum[end]>=pivotkey){end--;//最后一次不要交换if(start!=end && arrayNum[end]>arrayNum[end+1]){int temp=arrayNum[end];arrayNum[end]=arrayNum[end+1];arrayNum[end+1]=temp;highflag=true;}}arrayNum[start]=arrayNum[end];//比枢轴记录小的记录移动到低端while(start<end && arrayNum[start]<=pivotkey){start++;//最后一次不要交换if(start!=end && arrayNum[start-1]>arrayNum[start]){int temp=arrayNum[start-1];arrayNum[start-1]=arrayNum[start];arrayNum[start]=temp;lowflag=true;}}arrayNum[end]=arrayNum[start];//比枢轴记录大的记录移动到高端}arrayNum[start]=pivotkey;//枢轴记录到位return start;//返回枢轴位置
}
void QSort(int arrayNum[],int start,int end){//递归结束条件start>=endif(start<end){bool lowflag=false;bool highflag=false;int pivotloc=Partition(arrayNum,start,end,lowflag,highflag);//将表一分为2if(lowflag==true)QSort(arrayNum,start,pivotloc-1);//对低子表递归排序,pivotloc是枢轴位置if(highflag==true)QSort(arrayNum,pivotloc+1,end);//对高子表递归排序}
}void QuickSort(int arrayNum[]){QSort(arrayNum,0,8);
}
int main(){int arrayNum[9]={5,4,3,2,1,6,7,8,9};QuickSort(arrayNum);for(int i=0;i<9;i++)cout<<arrayNum[i]<<" ";cout<<endl;return 0;
}



这篇关于严蔚敏--快速排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/768558

相关文章

使用Python实现快速搭建本地HTTP服务器

《使用Python实现快速搭建本地HTTP服务器》:本文主要介绍如何使用Python快速搭建本地HTTP服务器,轻松实现一键HTTP文件共享,同时结合二维码技术,让访问更简单,感兴趣的小伙伴可以了... 目录1. 概述2. 快速搭建 HTTP 文件共享服务2.1 核心思路2.2 代码实现2.3 代码解读3.

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav

Python如何快速下载依赖

《Python如何快速下载依赖》本文介绍了四种在Python中快速下载依赖的方法,包括使用国内镜像源、开启pip并发下载功能、使用pipreqs批量下载项目依赖以及使用conda管理依赖,通过这些方法... 目录python快速下载依赖1. 使用国内镜像源临时使用镜像源永久配置镜像源2. 使用 pip 的并

SpringBoot快速接入OpenAI大模型的方法(JDK8)

《SpringBoot快速接入OpenAI大模型的方法(JDK8)》本文介绍了如何使用AI4J快速接入OpenAI大模型,并展示了如何实现流式与非流式的输出,以及对函数调用的使用,AI4J支持JDK8... 目录使用AI4J快速接入OpenAI大模型介绍AI4J-github快速使用创建SpringBoot

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import

Spring排序机制之接口与注解的使用方法

《Spring排序机制之接口与注解的使用方法》本文介绍了Spring中多种排序机制,包括Ordered接口、PriorityOrdered接口、@Order注解和@Priority注解,提供了详细示例... 目录一、Spring 排序的需求场景二、Spring 中的排序机制1、Ordered 接口2、Pri

大数据小内存排序问题如何巧妙解决

《大数据小内存排序问题如何巧妙解决》文章介绍了大数据小内存排序的三种方法:数据库排序、分治法和位图法,数据库排序简单但速度慢,对设备要求高;分治法高效但实现复杂;位图法可读性差,但存储空间受限... 目录三种方法:方法概要数据库排序(http://www.chinasem.cn对数据库设备要求较高)分治法(常