快速排序算法——C/C++

快速排序算法——C/C++快速排序1、算法思想快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。2、实现原理2.1、设置两个变量low、high,排序开始时:low=0,high=size-1。2.2、整个数组找基准正确位置,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面…

大家好,又见面了,我是你们的朋友全栈君。

快速排序

1. 算法思想

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

2. 实现原理

2.1、设置两个变量 low、high,排序开始时:low=0,high=size-1。
2.2、整个数组找基准正确位置,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面

  1. 默认数组的第一个数为基准数据,赋值给key,即key=array[low]。
  2. 因为默认数组的第一个数为基准,所以从后面开始向前搜索(high–),找到第一个小于key的array[high],就将 array[high] 赋给 array[low],即 array[low] = array[high]。(循环条件是 array[high] >= key;结束时 array[high] < key)
  3. 此时从前面开始向后搜索(low++),找到第一个大于key的array[low],就将 array[low] 赋给 array[high],即 array[high] = array[low]。(循环条件是 array[low] <= key;结束时 array[low] > key)
  4. 循环 2-3 步骤,直到 low=high,该位置就是基准位置。
  5. 把基准数据赋给当前位置。

2.3、第一趟找到的基准位置,作为下一趟的分界点。
2.4、递归调用(recursive)分界点前和分界点后的子数组排序,重复2.2、2.3、2.4的步骤。
2.5、最终就会得到排序好的数组。

3. 动态演示

在这里插入图片描述

在这里插入图片描述

4. 完整代码

三个函数
基准插入函数:int getStandard(int array[],int low,int high)
(返回基准位置下标)
递归排序函数:void quickSort(int array[],int low,int high)
主函数:int main()

#include <stdio.h>
#include <stdlib.h>
void display(int* array, int size) { 

for (int i = 0; i < size; i++) { 

printf("%d ", array[i]);
}
printf("\n");
}
int getStandard(int array[], int i, int j) { 

// 基准数据
int key = array[i];
while (i < j) { 

// 因为默认基准是从左边开始,所以从右边开始比较
// 当队尾的元素大于等于基准数据 时,就一直向前挪动 j 指针
while (i < j && array[j] >= key) { 

j--;
}
// 当找到比 array[i] 小的时,就把后面的值 array[j] 赋给它
if (i < j) { 

array[i] = array[j];
}
// 当队首元素小于等于基准数据 时,就一直向后挪动 i 指针
while (i < j && array[i] <= key) { 

i++;
}
// 当找到比 array[j] 大的时,就把前面的值 array[i] 赋给它
if (i < j) { 

array[j] = array[i];
}
}
// 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置
// 把基准数据赋给正确位置
array[i] = key;
return i;
}
void QuickSort(int array[], int low, int high) { 

// 开始默认基准为 low
if (low < high) { 

// 分段位置下标
int standard = getStandard(array, low, high);
// 递归调用排序
// 左边排序
QuickSort(array, low, standard - 1);
// 右边排序
QuickSort(array, standard + 1, high);
}
}
// 合并到一起快速排序
// void QuickSort(int array[], int low, int high) { 

// if (low < high) { 

// int i = low;
// int j = high;
// int key = array[i];
// while (i < j) { 

// while (i < j && array[j] >= key) { 

// j--;
// }
// if (i < j) { 

// array[i] = array[j];
// }
// while (i < j && array[i] <= key) { 

// i++;
// }
// if (i < j) { 

// array[j] = array[i];
// }
// }
// array[i] = key;
// QuickSort(array, low, i - 1);
// QuickSort(array, i + 1, high);
// }
// }
int main() { 

int array[] = { 
49, 38, 65, 97, 76, 13, 27, 49, 10};
int size    = sizeof(array) / sizeof(int);
// 打印数据
printf("%d \n", size);
QuickSort(array, 0, size - 1);
display(array, size);
// int size = 20;
// int array[20] = {0}; // 数组初始化
// for (int i = 0; i < 10; i++) { // 数组个数
// for (int j = 0; j < size; j++) { // 数组大小
// array[j] = rand() % 1000; // 随机生成数大小 0~999
// }
// printf("原来的数组:");
// display(array, size);
// QuickSort(array, 0, size - 1);
// printf("排序后数组:");
// display(array, size);
// printf("\n");
// }
return 0;
}

5. 结果展示

(递归调用,不好展示每次排序结果)
在这里插入图片描述

6. 算法分析

时间复杂度:

  1. 最好: O ( n l o g 2 n ) O(n log_{2} n) O(nlog2n)
  2. 最坏: O ( n 2 ) O(n^2) O(n2)
  3. 平均: O ( n l o g 2 n ) O(n log_{2} n) O(nlog2n)

空间复杂度: O ( n l o g 2 n ) O(n log_{2} n) O(nlog2n)

稳定性:不稳定

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/152562.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 以太坊 如何挖矿_以太坊asic矿机

    以太坊 如何挖矿_以太坊asic矿机以太坊(ETH)是什么?它是公链之王,有人说它可能会超越比特币(BTC),其应用非常广泛,在以太坊世界里挖矿可以得到奖励,那么怎么挖矿?一下是以太坊的挖矿教程,相信看完教程后,你也能迅速的开始自己的挖矿之旅!我来详细道来。开始挖矿前的准备工作:1、硬件需求:系统要求.Windows7/8/10系统—–显卡要求.AMD或NVIDIA显卡,至少拥有4GB显存。2、软件准备:首先需要一款挖矿软件。Claymore’sDualMiner是原版挖矿软件需要掌握基础知识才可以使

    2022年10月15日
  • win10 专业工作站 激活码_通用破解码

    win10 专业工作站 激活码_通用破解码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • 写给大忙人看的 – Java中从MinIO服务器中下载文件(3)[通俗易懂]

    写给大忙人看的 – Java中从MinIO服务器中下载文件(3)[通俗易懂]前面两章介绍了MinIO文件服务器的环境搭建,以及在Java中上传文件至MinIO文件服务器中,现在,一起来看下如何从MinIO文件服务器中下载文件吧1、获取文件对象我们在MinIO工具类中,获取文件对象的方法,即获取文件的输入流对象/***获取文件**@parambucketNamebucket名称*@paramobjectName文件名称*@return二进制流*/@SneakyThrowspublicInputStreamge

  • es6类型转换_es6转换es5

    es6类型转换_es6转换es5>虽然我觉得没什么用,但是记一下吧[TOC]####1.新建项目项目目录结构:![](https://box.kancloud.cn/1e80da2d1c4c01681a65023089a9f18a_229x108.png)####2.src中的**index.js**为你写的es6语法代码我们例子写:“`letb=1;console.log(b);constname=”…

  • Linux防火墙关闭命令

    1.启动防火墙systemctlstartfirewalld2.禁用防火墙systemctlstopfirewalld3.设置开机启动systemctlenablefirewalld4.停止并禁用开机启动sytemctldisablefirewalld5.重启防火墙firewall-cmd–reload在linus上部署了项目,有时候会发现防火墙会拦截浏览器上发起的请求,这时候只需要执行第2个命令,把防火墙关闭即可…

  • PSTools[通俗易懂]

    PSTools[通俗易懂]howtogetthePSTools?fromhere:http://technet.microsoft.com/en-us/sysinternals/bb897553.aspxAfterdownloadthePSToos,youcanextratehPSToos,thenkyouwillgetasetofPCtools.thatcotain

    2022年10月22日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号