编程珠玑:快速排序

2023-11-23 05:30
文章标签 快速 编程 排序 珠玑

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

为什么80%的码农都做不了架构师?>>>   hot3.png

前言

    编程珠玑一书对快速排序讲得较为透彻,最早的快排是单向的,慢慢演化成双向的,也就是目前的版本。从此书能看到这种演化的必要性。我想这是我最后一次看快排,原理搞懂了就不会忘了。

快速排序思想

    1962年,由C.A.R.Hoare创造出来。该算法核心思想就一句话:“排序数组时,将数组分成两个小部分,然后对它们递归排序”。然而采取什么样的策略将数组分成两个部分是关键,想想看,如果随便将数组A分成A1和A2两个小部分,即便分别将A1和A2排好序,那么A1和A2重新组合成A时仍然是无序的。所以,我们可以在数组中找一个值,称为key值,我们在把数组A分解为A1和A2前先对A做一些处理,让小于key值的元素都移到其左边,所有大于key值的元素都移到其右边。这样递归排序A1和A2,数组A就排好了。

举例

    我们要排序的数组如下:

55 41 59 26 53 58 97 93

    我们选取第一个元素作为key值,即55.(一般都是选取第一个元素)。假如我们有一种办法可以将数组做一步预处理,让小于key值的元素都位于其左边,大于key值的元素都位于其右边,预处理完数组如下:

41 26 53 55 59 58 97 93
    这样数组就被key值划分成了两段,A[0...2]小于key,A[4...7]大于key,可见key值本身已排好序,接下来对A[0...2]和A[4...7]分别进行递归排序,那么整个数组就排好序了。预处理做的工作再次澄清下:找一个key值,把key位放到某位置A[p],使小于key值的元素都位于A[p]左边,大于key值的元素都位于A[p]的右边。到此,我们的快排模型就成型了。
/*l, u 代表待排序部分的下界和上界*/
void qsort(l, u)
{/*递归结束条件是待排序部分的元素个数小于2*/if(l >= u){return;}/*此处进行预处理,预处理后key值位于位置p*/qsort(l, p-1);qsort(p+1, u);
}

     接下来看如何做预处理。我们选取A[0]做为key值, p作为key值的位置。我们从A[1]开始遍历后面的数组,用变量i指示目前的位置,每次找到小于key的值都与A[++p]交换。开始时p=0.

55 41 59 26 53 58 97 93
i = 1,A[i]位置为41, 即A[i] < key, swap(++p , i),即p = 1:

55 41 59 26 53 58 97 93
i = 2,A[i]位置为59,A[i] > key,不做任何改变。
i = 3,A[i]位置为26,A[i] < key,swap(++p, i), 即p = 2:

55 41 26 59 53 58 97 93
i = 4,A[i]位置为53,A[i] < key,swap(++p, i),p = 3:

55 41 26 53 59 58 97 93
i = 5,A[i]位置为58,A[i] > key,不做任何改变。
i = 6,A[i]位置为97,A[i] > key,不做任何改变.
i = 7,A[i]位置为93,A[i] > key,不做任何改变.结束循环。此时p为key的最终位置。还需一步把key值填入p位置。

最后swap(l, p)即把Key值放到最终位置上了。至于为什么要交换l,p的位置,可以另拿一组数据试一下:55,41,59,26,99,58,97,93。

完整的程序1

/*l, u 代表待排序部分的下界和上界*/
void qsort(int l, int u)
{/*递归结束条件是待排序部分的元素个数小于2*/if(l >= u){return;}int p = l;for(int i = l+1; i <= u; i++){if(A[i] < A[l]){swap(++p, i);}}swap(l, p);qsort(l, p-1);qsort(p+1, u);
}

这就是第一代快速排序算法,正常情况下其复杂度为nlogn,但在考虑一种极端情况:n个相同元素组成的数组。在n-1次划分中每次划分都需要O(n)的时间,所以总的时间为O(n^2)。使用双向划分就可以避免这个问题。

双向划分快速排序


/*l, u 代表待排序部分的下界和上界*/
void qsort(int l, int u)
{/*递归结束条件是待排序部分的元素个数小于2*/if(l >= u){return;}key = A[l]for(int i = l, j = u+1; i <= j;){do i++ while(i <= u && A[i] < key));do j-- while(A[j] > key);if(i > j){break;}swap(i, j);}swap(l, j);qsort(l, j-1);qsort(j+1, u);
}




转载于:https://my.oschina.net/renhc/blog/94644

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



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

相关文章

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器:探测开放端口2.简易 HTTP 服务器:10 秒搭个网页3.局域网游戏:多人联机对战4.

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

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

Java并发编程必备之Synchronized关键字深入解析

《Java并发编程必备之Synchronized关键字深入解析》本文我们深入探索了Java中的Synchronized关键字,包括其互斥性和可重入性的特性,文章详细介绍了Synchronized的三种... 目录一、前言二、Synchronized关键字2.1 Synchronized的特性1. 互斥2.

springboot security快速使用示例详解

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

Python异步编程中asyncio.gather的并发控制详解

《Python异步编程中asyncio.gather的并发控制详解》在Python异步编程生态中,asyncio.gather是并发任务调度的核心工具,本文将通过实际场景和代码示例,展示如何结合信号量... 目录一、asyncio.gather的原始行为解析二、信号量控制法:给并发装上"节流阀"三、进阶控制

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