排序算法-快速排序法(QuickSort)

2023-10-12 08:30
文章标签 算法 快速 排序 quicksort

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

 排序算法-快速排序法(QuickSort)

1、说明

快速排序法是由C.A.R.Hoare提出来的。快速排序法又称分割交换排序法,是目前公认的最佳排序法,也是使用分而治之(Divide and Conquer)的方式,会先在数据中找到一个虚拟的中间值,并按此中间值将所有打算排序的数据分为两部分。其中小于中间值的数据放在左边,而大于中间值的数据放在右边,再以同样的方式分别处理左右两边的数据,直到排序完为止。操作与分割步骤如下:

假设有n项记录R_{1},R_{2},R_{3},...,R_{n},其键值为K_{1},K_{2},K_{3},...,K_{n}

  1. 先假设K的值为第一个键值。
  2. 从左向右找出键值K_{i},使得K_{i}> K
  3. 从左向右找出键值K_{j},使得K_{j}< K
  4. 如果i< j,那么K_{i}K_{j}互换,并回到步骤2。
  5. 如果i\geqslant j,那么将KK_{j}互相,并以j为基准点分割成左、右两部分,然后针对左、右两边执行步骤1~5,直到左边键值等于右边键值为止。

2、算法分析

  1. 在最好情况和平均情况下,时间复杂度为O(nlog_{2^{}}n)。在最坏情况下就是每次挑中的中间值不是最大就是最小的,其时间复杂度为O(n^{2})
  2. 快速排序法不是稳定排序法。
  3. 在最坏情况下,空间复杂度为O(n),而在最好情况下,空间复杂度为O(log_{2^{}}n)
  4. 快速排序法是平均运行时间最快的排序法。

3、C++代码 

#include<iostream>
using namespace std;void Print(int tempData[], int tempSize) {for (int i = 0; i < tempSize; i++) {cout << tempData[i] << "  ";}cout << endl;
}void Quick(int tempData[], int tempLeft, int tempRight) {int temp;int leftIndex;int rightIndex;int t;if (tempLeft < tempRight) {leftIndex = tempLeft + 1;rightIndex = tempRight;while (true) {for (int i = tempLeft + 1; i < tempRight; i++) {if (tempData[i] >= tempData[tempLeft]) {leftIndex = i;break;}leftIndex++;}for (int j = tempRight; j > tempLeft + 1; j--) {if (tempData[j] <= tempData[tempLeft]) {rightIndex = j;break;}rightIndex--;}if (leftIndex < rightIndex) {temp = tempData[leftIndex];tempData[leftIndex] = tempData[rightIndex];tempData[rightIndex] = temp;}else {break;}}if (leftIndex >= rightIndex) {temp = tempData[tempLeft];tempData[tempLeft] = tempData[rightIndex];tempData[rightIndex] = temp;Quick(tempData, tempLeft, rightIndex - 1);Quick(tempData, rightIndex + 1, tempRight);}}
}int main() {const int size = 10;int data[100] = { 32,5,24,55,40,81,17,48,25,71 };//32  5  24  55  40  81  17  48  25  71//32  5  24  25  40  81  17  48  55  71//32  5  24  25  17  81  40  48  55  71//17  5  24  25  32  81  40  48  55  71//5  17  24  25  32  81  40  48  55  71//5  17  25  24  32  81  40  48  55  71//5  17  25  24  32  71  40  48  55  81//5  17  25  24  32  55  40  48  71  81//5  17  25  24  32  48  40  55  71  81//5  17  25  24  32  40  48  55  71  81Print(data, size);Quick(data, 0, size - 1);Print(data, size);return 0;
}

输出结果 

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



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

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

Linux如何快速检查服务器的硬件配置和性能指标

《Linux如何快速检查服务器的硬件配置和性能指标》在运维和开发工作中,我们经常需要快速检查Linux服务器的硬件配置和性能指标,本文将以CentOS为例,介绍如何通过命令行快速获取这些关键信息,... 目录引言一、查询CPU核心数编程(几C?)1. 使用 nproc(最简单)2. 使用 lscpu(详细信

一文详解如何在idea中快速搭建一个Spring Boot项目

《一文详解如何在idea中快速搭建一个SpringBoot项目》IntelliJIDEA作为Java开发者的‌首选IDE‌,深度集成SpringBoot支持,可一键生成项目骨架、智能配置依赖,这篇文... 目录前言1、创建项目名称2、勾选需要的依赖3、在setting中检查maven4、编写数据源5、开启热

MybatisX快速生成增删改查的方法示例

《MybatisX快速生成增删改查的方法示例》MybatisX是基于IDEA的MyBatis/MyBatis-Plus开发插件,本文主要介绍了MybatisX快速生成增删改查的方法示例,文中通过示例代... 目录1 安装2 基本功能2.1 XML跳转2.2 代码生成2.2.1 生成.xml中的sql语句头2

8种快速易用的Python Matplotlib数据可视化方法汇总(附源码)

《8种快速易用的PythonMatplotlib数据可视化方法汇总(附源码)》你是否曾经面对一堆复杂的数据,却不知道如何让它们变得直观易懂?别慌,Python的Matplotlib库是你数据可视化的... 目录引言1. 折线图(Line Plot)——趋势分析2. 柱状图(Bar Chart)——对比分析3

一文教你Java如何快速构建项目骨架

《一文教你Java如何快速构建项目骨架》在Java项目开发过程中,构建项目骨架是一项繁琐但又基础重要的工作,Java领域有许多代码生成工具可以帮助我们快速完成这一任务,下面就跟随小编一起来了解下... 目录一、代码生成工具概述常用 Java 代码生成工具简介代码生成工具的优势二、使用 MyBATis Gen

Java List排序实例代码详解

《JavaList排序实例代码详解》:本文主要介绍JavaList排序的相关资料,Java排序方法包括自然排序、自定义排序、Lambda简化及多条件排序,实现灵活且代码简洁,文中通过代码介绍的... 目录一、自然排序二、自定义排序规则三、使用 Lambda 表达式简化 Comparator四、多条件排序五、

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

使用animation.css库快速实现CSS3旋转动画效果

《使用animation.css库快速实现CSS3旋转动画效果》随着Web技术的不断发展,动画效果已经成为了网页设计中不可或缺的一部分,本文将深入探讨animation.css的工作原理,如何使用以及... 目录1. css3动画技术简介2. animation.css库介绍2.1 animation.cs