快速排序(排序中篇)

2024-06-02 21:12
文章标签 快速 排序 中篇

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

1.快速排序的概念及实现

2.快速排序的时间复杂度

3.优化快速排序

4.关于快速排序的细节

5.总代码

1.快速排序的概念及实现

1.1快速排序的概念

快速排序的单趟是选一个基准值,然后遍历数组的内容把比基准值大的放右边,比基准值小的放在左边,下面的动图可以简单了解是这么排序的。

选第一个6作为基准,然后让俩个变量作为下标值去遍历数组,L要选出一个比key(6)要大的值然后停下,R要找到一个比key要小的值然后停下,最后把L和R停下的位置对应的值进行交换,交换完后有继续走,直到L与R相遇,最后把碰面的地方对应的值与key交换,完成一次单趟的快排 ,这样key的左边都是比key小的值,而右边都是比key大的值,与之前比较变得相对有序。

走完单趟后,后面就会以key的左右边重读第一次操作,就是把数组以key为分界线分为俩个数组(逻辑上),再选出一个基准值,使得基准值的俩边要么比key大要么比key小,这样就会想到递归,一直分到后面就会出现只有一个值的数组,或者不存在的(后面会提到),递归完后的数组就是排好序的了。

1.2快速排序的实现

代码:

#include<stdio.h>
void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void QuickSort(int* a,int left, int right)
{if (left >= right)return;int begin = left;int end =right;int keyi = left;while (begin< end){while (begin < end && a[keyi] <= a[end]){end--;}while (begin < end && a[keyi] >= a[begin]){begin++;}swap(&a[begin], &a[end]);}swap(&a[keyi], &a[begin]);keyi = begin;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);
}
int main()
{int arr[] = { 11,7,5,9,6,1,4,3,8,8,8,101 };int size = sizeof(arr) / sizeof(arr[0]);QuickSort(arr,0,size-1);for (int i = 0; i < size; i++){printf("%d ", arr[i]);}return 0;
}

代码分析:

创建begin和end来作为L和R去遍历数组,while循环执行的条件是begin<end(这个是begin和end相遇的情况)与基准值比end下标对应的值小,满足就end--(就是往前走),begin就去找比基准值大的值才会执行条件,否则就begin++(往后走),但俩个while都执行完,就说明L与R都停下来了,就可以进行交换,交换完后while循环结束,出循环后就交换基准值与相遇地方对应的值,然后递归去keyi两边的数组排序,则keyi+-1就是它们的新边界,最前面的if判断是否存在可以排序,因为一个和不存在是排不了的。

下图是不存在的情况:

2.快速排序的时间复杂度

本文只是简单计算快速排序的时间复杂度。

 

3.优化快速排序 

3.1三数取中

快速排序遇到有序的数组就会出现问题,时间复杂度会变为O(N^2).

 基准值到最后还是原来的位置,则递归时,每次只会去掉第一个元素,不会像对半分那种,这样每层大约n个,层数也为n个,时间复杂度就为O(N^2),速度会慢很多,所以基准值不应该每次取第一个,可以用随机函数来获取一个拟随机数作为key值,但是也是有可能是最小或者最大(在排升序或者降序会慢),所以用三数取中的方法来定key,但是得到key值还是要和第一个值交换一下,保证上面的代码逻辑不变,假如下标为3的值适合作key就把它和第一个交换。

在有序的情况下插入排序都比快速排序快很多,而且在数据量大的时候会发生栈溢出,是一直递归开辟空间而导致的。

三数取中就是在数组中找到一个值不是最大也不是最小。

三数取中代码实现:

int GetMidi(int*a,int left, int right)
{int midi = (left + right) / 2;if (a[midi] < a[right]){if (a[midi] > a[left]){return midi;}else{if (a[left] > a[right])return right;elsereturn left;}}else//a[midi]>a[right]{if (a[midi] > a[left]){if (a[right] > a[left])return right;elsereturn left;}elsereturn midi;}
}

代码分析:

就是在数组的最左右边及它们和一半值共三个数,然后比较三个值找到处于中间值的下标,这个值一定不是最小或者最大,比较数组的值返回下标,这样尽管处理有序数组也不会有栈溢出的风险,也能提高运行速率。

 3.2小区间优化

因为在二叉树中知道越到后面递归的次数越多,最下面的一层是占总的约一半,而快速排序也有这样的问题,在区间小的时候递归会非常多,所以在小区间就可以用其他的排序方法来代替,但区间小于一个范围时可以采用插入排序来排。

代码实现:

void QuickSort(int* a,int left, int right)
{if (left >= right)return;if ((right - left + 1) < 10){InsertSort(a+left, right - left + 1);}else{int begin = left;int end = right;int keyi = GetMidi(a, left, right);while (begin < end){while (begin < end && a[keyi] <= a[end]){--end;}while (begin < end && a[keyi] >= a[begin]){++begin;}swap(&a[begin], &a[end]);}swap(&a[keyi], &a[begin]);keyi = begin;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}}

这里需要注意的是用插入排序时参数应该是a+left而不是a,因为在递归过程中数组已经被分成很多个区间了(逻辑上),插入排序的是指定位置且指定大小排。 

4.关于快速排序的细节

在代码实现里是让R先走的,R停下来才到L走,都停下来才交换,最后在交换L和key的值,为什么key的值一定比L与R相遇的位置对应的值小呢?

下面是分析:

1.L遇R:R先走然后找到了比key小的值停下来了,L开始走,但是没有找到比key大的值,最后于R相遇,此时相遇的地方对应的值是比key小的。

2.R遇L:R找到比key小的值停下来,L也遇到比key大的值停下来了,然后交换,此时R继续走,但是没有找到比key小的值了,就会一直走与L相遇,此时L所在的位置是上一次交换完的位置,也就是说L的位置的值原本是在R上一次停下来的位置对应的值,而这个值是一定比key小的,不然R是不会停下来的。

综上可知,最后L所在的位置是一定小于key对应的值的。

5.总代码:

#include<stdio.h>
#include<stdlib.h>
#include<time.h>void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void InsertSort(int* a, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = a[end + 1];while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];end--;}elsebreak;}a[end + 1] = tmp;}
}
int GetMidi(int*a,int left, int right)
{int midi = (left + right) / 2;if (a[midi] < a[right]){if (a[midi] > a[left]){return midi;}else{if (a[left] > a[right])return right;elsereturn left;}}else//a[midi]>a[right]{if (a[midi] > a[left]){if (a[right] > a[left])return right;elsereturn left;}elsereturn midi;}
}
void QuickSort(int* a,int left, int right)
{if (left >= right)return;if ((right - left + 1) < 10){InsertSort(a+left, right - left + 1);}else{int begin = left;int end = right;int keyi = GetMidi(a, left, right);while (begin < end){while (begin < end && a[keyi] <= a[end]){--end;}while (begin < end && a[keyi] >= a[begin]){++begin;}swap(&a[begin], &a[end]);}swap(&a[keyi], &a[begin]);keyi = begin;QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}}void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){// Öظ´²»¶àa1[i] = rand() + i;// Öظ´½Ï¶à//a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin5 = clock();QuickSort(a1, 0, N - 1);int end5 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("QuickSort:%d\n", end5 - begin5);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{int arr[] = { 11,7,5,9,6,1,4,3,8,8,8,101 };int size = sizeof(arr) / sizeof(arr[0]);//TestOP();//InsertSort(arr, size);QuickSort(arr,0,size-1);for (int i = 0; i < size; i++){printf("%d ", arr[i]);}return 0;
}

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



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

相关文章

使用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对数据库设备要求较高)分治法(常