选择排序，冒泡排序，插入排序，快速排序及其优化

目录

1 选择排序

1.1 原理

1.2 具体步骤 

1.3 代码实现

1.4 优化

2 冒泡排序

2.1 原理

2.2 具体步骤

2.3 代码实现

2.4 优化

3 插入排序

3.1 原理

3.2 具体步骤 

3.3 代码实现

3.4 优化

4. 快速排序 

4.1 原理

4.2 具体步骤

4.3 代码实现 

4.4 优化 

为了讲解方便，以下排完序后，统一为升序

1 选择排序

1.1 原理

核心思想是通过不断地选择未排序序列中的最小元素，然后将其放到已排序序列的末尾（或未排序列的起始位置）。

 

1.2 具体步骤 

1. 初始状态：所有元素初始都为未排序状态

2 在未排序元素中，找到最小的那个元素的下标

3 与未排序的第一个元素（已排序的末尾元素）交换位置

4 循环 2 ~ 3，直到所有元素都变为已排了的元素

1.3 代码实现

代码实现的关键点：找下标，换位置，以及循环条件。同时也是容易出错的点。

#include<stdio.h>void sort(int* p, int n)
{for (int i = 0; i < n - 1; i++) // < n 也可以，只是无意义的重复，效率更低{int min = i;   // 找出的最小值，最后要放的位置的下标int j = i;for (j = i + 1; j < n; j++)  // 可以=i，只是=i，无意义。{if (p[min] > p[j])min = j;	//  for循环结束后，j会++  if (n - 1 == j)break;}// 交换数据int temp = p[i];p[i] = p[min];p[min] = temp;}
}int main()
{int arr[] = { 9,6,8,-1,0,5,2,8 };int sz = sizeof(arr) / sizeof(arr[0]);sort(arr, sz);  // 选择排序for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

1.4 优化

 原来一趟只找出最小值，现在一趟既找出最小值，也找出最大值，循环的次数就减半了。

#include<stdio.h>void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}void sort(int* p, int n)
{// 循环趟数减半，可以了就要停止，不然就会继续换，反而无序for (int i = 0; i <= n / 2 + 1; i++) {int min = i;   // 找出的最小值的下标int max = n -i - 1; // 找出的最大值的下标int j = i;for (j = i; j < n - i; j++) {if (p[min] > p[j])min = j;if (p[max] < p[j])max = j;if (n - 1 - i == j)break;}// 交换数据// 当最小值与最大值恰好位置相反，换两次=没换if (!(p[min] == p[n - 1 - i] || p[i] == p[max])){swap(&p[i], &p[min]);swap(&p[n - 1 - i], &p[max]);}else{swap(&p[i], &p[n - 1 - i]);}}
}int main()
{int arr[] = { 9,6,8,-1,0,5,2,8 };int sz = sizeof(arr) / sizeof(arr[0]);sort(arr, sz);  // 选择排序优化for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

2 冒泡排序

2.1 原理

核心思想是通过重复交换相邻元素来实现排序。

类比选择排序，相当于从右往左开始排，每次在未排序中找出最大值，放在已排序的前一个位置。

 

2.2 具体步骤

1. 从左往右相邻元素比较，让大的数不断右移

2. 循环1，直至每个已排序的元素 = 所有元素的个数

2.3 代码实现

关键点：循环条件的控制，以及交换（大的靠右）

#include<stdio.h>void sort(int arr[], size_t sz)
{for (int i = 0; i < sz - 1; i++){// 在这里j可以 < sz - 1;// 在本段代码中交换位置是有条件的// < sz - 1;进去了也不会执行// 选择排序从哪开始到哪结束就必须是那样// 不可能在再在排了序中挑最大最小值for (int j = 0; j < sz - 1 - i; j++){if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}int main()
{int arr[] = { 9,6,8,-1,0,5,2,8 };size_t sz = sizeof(arr) / sizeof(arr[0]);sort(arr, sz);  // 冒泡排序for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

2.4 优化

如果我们一开始拿到的数组就是有序的话，我们还是不得不执行那循环套循环，效率就很低。我们可以先假设已达到了有序状态，如果交换了，就通过修改flag的值来办，这样就可以提前跳出循环了。

#include<stdio.h>void sort(int arr[], size_t sz)
{for (int i = 0; i < sz - 1; i++){// 假设已经到达了有序状态int flag = 1;for (int j = 0; j < sz - 1 - i; j++){if (arr[j] > arr[j + 1]){int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;// 交换了，说明无序flag = 0;}}if (flag){break;}}
}int main()
{int arr[] = { 9,6,8,-1,0,5,2,8 };size_t sz = sizeof(arr) / sizeof(arr[0]);sort(arr, sz);  // 冒泡排序优化for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

3 插入排序

3.1 原理

核心思想是构建有序序列。将未排序的元素逐个插入到已排序的部分。

左边是已排序的，右边是未排序的。未排序的从左到右第一个，放到已排序列中开始交换，大的就右移，移到不能再移。

 

3.2 具体步骤 

1. 初始化：左边第一个是已排序的，右边都是未排序的。

2 交换位置：未排序的第一个进入排序中，比较大小，大的右移，移到不能再移

3 循环 1 ~ 2，直到遍历数组中的所有元素

3.3 代码实现

关键点： 交换位置的意识，递推的意识

#include<stdio.h>void sort(int arr[], size_t sz)
{// 外层每一次循环都会让已排序的元素+1for (int i = 1; i < sz; i++){int j = i;while (j >= 1 && arr[j] < arr[j - 1]){// 交换位置arr[j - 1] = arr[j] ^ arr[j - 1];arr[j] = arr[j] ^ arr[j - 1];arr[j - 1] = arr[j] ^ arr[j - 1];j--;}}
}int main()
{int arr[] = { 9,6,8,-1,0,5,2,8 };size_t sz = sizeof(arr) / sizeof(arr[0]);sort(arr, sz);  // 插入排序for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

3.4 优化

所谓优化算法就更接近于通俗意义上的插入，找到该插入的的地方，再进行插入。即对插入的位置实行二分查找。

#include<stdio.h>// 返回值是该数插入进去后的下标
int find(int arr[], int sz)
{//    1 2 4 5 7 8 9   6int left = 0;int right = sz - 1;while (left < right){// 防止陷入死循环if (left == right)break;int mid = right + (left - right) / 2;if (arr[mid] > arr[sz]){right = mid - 1;}else if (arr[mid] < arr[sz]){left = mid + 1;}else{right = left;break;}}if (arr[sz] < arr[right]){return right;}else{return right + 1;}
}void sort(int arr[], size_t sz)
{for (int i = 1; i < sz; i++){// 本质：二分查找 + 交换int temp = arr[i]; // 将要排序的数暂时储存起来// 二分查找找到应该插入的下标int final_local = find(arr, i);// 该右移的右移for (int j = i - 1; j >= final_local; j--){arr[j + 1] = arr[j];}arr[final_local] = temp;}
}int main()
{int arr[] = { 9,6,8,-1,0,5,2,8 };size_t sz = sizeof(arr) / sizeof(arr[0]);sort(arr, sz);  // 插入排序优化for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

4. 快速排序 

4.1 原理

核心思想是分治法。一分为二，左边比某个基准数小，右边比某个基准数大，左边右边又一分为二，直至不可再分

 

4.2 具体步骤

  1. 从数列中随便挑一个数作为基准数（我选的是最后一个数）;

  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。

  3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序；

4.3 代码实现 

关键点：递归的思想，函数要被调用，要写得一般一些

#include<stdio.h>
/*
函数功能：将最后一个元素作为基准数小于它的放左边，大于它的放右边
返回值：基准数最后的位置
*/
int partition(int arr[], int start, int end)
{// 遍历基准元素前的所有元素for (int i = end - 1; i >= start; i--){if (arr[i] > arr[end]){int temp = arr[i];arr[i] = arr[end - 1];arr[end - 1] = arr[end];arr[end] = temp;end -= 1;}}return end;//  2 1 3 2
}void QuickSort(int arr[], int start, int end)
{if (start < end){// 函数最后返回的是排过后基准元素的位置int pivot = partition(arr, start, end);// 递推式的一分为二QuickSort(arr, start, pivot - 1);QuickSort(arr, pivot + 1, end);}
}int main()
{int arr[] = { 9,6,8,-1,0,5,2,8 };size_t sz = sizeof(arr) / sizeof(arr[0]);// 以后还要调用，需写得一般一些QuickSort(arr, 0, sz - 1);  // 快速排序for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

4.4 优化 

快速排序的效率在于其平均时间复杂度为O(nlogn)，这使其成为实际应用中非常受欢迎的一种排序算法。然而，在最坏的情况下，其时间复杂度会退化到O(n^2)，这通常发生在每次选择的基准都是最大或最小元素时。为了避免这种情况，可以采用随机选择基准或者三数取中等策略来优化快速排序的性能。下面演示随机选择的优化

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
/*
函数功能：将最后一个元素作为基准数小于它的放左边，大于它的放右边
返回值：基准数最后的位置
*/
int partition(int arr[], int start, int end)
{int end_temp = end;end = rand() % (end - start) + start + 1;// 把左边大的甩到右边for (int i = end - 1; i >= start; i--){if (arr[i] > arr[end]){int temp = arr[i];arr[i] = arr[end - 1];arr[end - 1] = arr[end];arr[end] = temp;end -= 1;}}// 把右边小的甩到左边for (int i = end + 1; i <= end_temp; i++){if (arr[i] < arr[end]){int temp = arr[i];arr[i] = arr[end + 1];arr[end + 1] = arr[end];arr[end] = temp;end += 1;}}return end;//  2 1 3 2
}void QuickSort(int arr[], int start, int end)
{if (start < end){// 函数最后返回的是排过后基准元素的位置int pivot = partition(arr, start, end);// 递推式的一分为二QuickSort(arr, start, pivot - 1);QuickSort(arr, pivot + 1, end);}
}int main()
{srand((unsigned int)time(NULL));int arr[] = { 9,6,8,-1,0,5,2,8 };size_t sz = sizeof(arr) / sizeof(arr[0]);// 以后还要调用，需写得一般一些QuickSort(arr, 0, sz - 1);  // 快速排序for (int i = 0; i < sz; i++){printf("%d ", arr[i]);}return 0;
}

感谢观看！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/2815307.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

源码和包管理器安装U-Boot tools

源码和包管理器安装U-Boot tools

源码和包管理器安装U-Boot tools U-Boot&#xff08;Universal Bootloader&#xff09;是一个开源的嵌入式系统引导加载程序&#xff0c;用于引导嵌入式系统&#xff0c;如单板计算机、嵌入式开发板等。U-Boot 提供了一种灵活的引导解决方案&#xff0c;支持多种处理器架构和嵌…
阅读更多...
使用pyannote-audio实现声纹分割聚类

使用pyannote-audio实现声纹分割聚类

使用pyannote-audio实现声纹分割聚类 1 简单介绍 pyannote.audio是用Python编写的用于声纹分割聚类的开源工具包。在PyTorch机器学习基础上&#xff0c;不仅可以借助性能优越的预训练模型和管道实现声纹分割聚类&#xff0c;还可以进一步微调模型。 它的主要功能有以下几个&…
阅读更多...
ISP代理是什么？跨境账号养号为什么要选择它？

ISP代理是什么？跨境账号养号为什么要选择它？

在跨境出海业务中&#xff0c;代理IP对于您的在线任务至关重要&#xff0c;尤其是对于那些运行多个帐户的人来说。为您的帐户选择正确类型的代理对于确保帐户安全非常重要&#xff0c;劣质的IP容易使账号遭受封号风险。IPFoxy的多种代理IP类型应用范围各有侧重&#xff0c;其中…
阅读更多...
【GO开发工程师】grpc进阶#golang

【GO开发工程师】grpc进阶#golang

【GO开发工程师】grpc进阶#golang 推荐个人主页&#xff1a;席万里的个人空间 文章目录 【GO开发工程师】grpc进阶#golang1、protobuf2、grpc2.1、gRPC 的 Metadata机制2.2、grpc拦截器 1、protobuf syntax "proto3"; // 指定使用的 protobuf 版本为 proto3 import…
阅读更多...
vue-router4 (六) 命名视图

vue-router4 (六) 命名视图

命名视图可以使得同一级&#xff08;同一个组件&#xff09;中展示更多的路由视图&#xff0c;而不是嵌套显示&#xff0c; 命名视图可以让一个组件中具有多个路由渲染出口&#xff0c;这对于一些特定的布局组件非常有用。 应用场景&#xff1a; 比如点击login切换到组件A&am…
阅读更多...
Random，随机函数

Random，随机函数

黑马程序员学习笔记 nextInt(n)&#xff1a; 只生成0~(n-1)之间的数字&#xff0c;不包括n 主要代码就三个; package com.zhang.random;import java.util.Random;public class RandomDemo1 {public static void main(String[] args) {//目标&#xff1a;掌握使用Random生成随…
阅读更多...
进制转换md5绕过 [安洵杯 2019]easy_web1

进制转换md5绕过 [安洵杯 2019]easy_web1

打开题目 在查看url的时候得到了一串类似编码的东西&#xff0c;源码那里也是一堆base64&#xff0c;但是转换成图片就是网页上我们看见的那个表情包 ?imgTXpVek5UTTFNbVUzTURabE5qYz0&cmd 我们可以先试把前面的img那串解码了 解码的时候发现长度不够&#xff0c;那我们…
阅读更多...
算法沉淀——动态规划之子序列问题（下）（leetcode真题剖析）

算法沉淀——动态规划之子序列问题（下）（leetcode真题剖析）

算法沉淀——动态规划之子序列问题 01.最长定差子序列02.最长的斐波那契子序列的长度03.最长等差数列04.等差数列划分 II - 子序列 01.最长定差子序列 题目链接&#xff1a;https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/ 给你一个整数数…
阅读更多...
springboot+vue实现oss文件存储

springboot+vue实现oss文件存储

前提oss准备工作 进入阿里云官网&#xff1a;阿里云oss官网 注册 搜OSS&#xff0c;点击“对象存储OSS” 第一次进入需要开通&#xff0c;直接点击立即开通&#xff0c;到右上角AccessKey管理中创建AccessKey&#xff0c;并且记住自己的accessKeyId和accessKeySecret&#…
阅读更多...
【数据结构与算法】回溯法解题20240229

【数据结构与算法】回溯法解题20240229

【数据结构与算法】回溯法解题20240229 一、46. 全排列1、以[1,2,3]为例&#xff0c;抽象成树形结构2、回溯三部曲 二、LCR 084. 全排列 II1、以[1,1,2]为例&#xff0c;抽象成树形结构 三、面试题 08.07. 无重复字符串的排列组合四、面试题 08.08. 有重复字符串的排列组合 一、…
阅读更多...
Java面试资料集合，只需一篇文章吃透Java多线程技术

Java面试资料集合，只需一篇文章吃透Java多线程技术

前言 受到疫情影响我从过完年一直呆在家里&#xff0c;索性学点知识方便以后跳槽涨薪&#xff0c;于是从二月份开始学习阿里P8架构师纯手打的一份Java面经手册&#xff0c;没想到5月初我成功从我们三线的一个小公司跳槽进了腾讯&#xff0c;虽然等级不高&#xff0c;但是涨薪还…
阅读更多...
【力扣hot100】刷题笔记Day15

【力扣hot100】刷题笔记Day15

前言 今天要刷的是图论&#xff0c;还没学过&#xff0c;先看看《代码随想录》这部分的基础 深搜DFS理论基础 深搜三部曲 确认递归函数、参数确认终止条件处理目前搜索节点出发的路径 代码框架 void dfs(参数) {if (终止条件) {存放结果;return;}for (选择&#xff1a;本节点…
阅读更多...
Git教程-Git的基本使用

Git教程-Git的基本使用

Git是一个强大的分布式版本控制系统&#xff0c;它不仅用于跟踪代码的变化&#xff0c;还能够协调多个开发者之间的工作。在软件开发过程中&#xff0c;Git被广泛应用于协作开发、版本管理和代码追踪等方面。以下是一个详细的Git教程&#xff0c;我们将深入探讨Git的基本概念和…
阅读更多...
npm ERR! code ERESOLVE

npm ERR! code ERESOLVE

1、问题概述&#xff1f; 执行npm install命令的时候报错如下&#xff1a; tangxiaochuntangxiaochundeMacBook-Pro stf % npm install npm ERR! code ERESOLVE npm ERR! ERESOLVE unable to resolve dependency tree npm ERR! npm ERR! While resol…
阅读更多...
C++ Primer 总结索引 | 第八章：IO库

C++ Primer 总结索引 | 第八章：IO库

1、IO类 1、已经使用过的IO类型和对象 都是 操纵char数据的。默认情况下&#xff0c;这些对象 都是关联到 用户的控制台窗口的 但是 不能仅从控制台窗口 进行IO操作&#xff0c;应用程序 需要 读写命名文件&#xff0c;使用IO操作 处理string中的字符 会很方便&#xff0c;此…
阅读更多...
Netty入门指南：从零开始的异步网络通信

Netty入门指南：从零开始的异步网络通信

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 Netty入门指南&#xff1a;从零开始的异步网络通信 前言Netty简介由来&#xff1a;发展历程&#xff1a;异步、事件驱动的编程模型&#xff1a; 核心组件解析通信协议高性能特性异步编程范式性能优化与…
阅读更多...
Linux零基础快速入门

Linux零基础快速入门

Linux的诞生 Linux创始人:林纳斯 托瓦兹 Linux 诞生于1991年&#xff0c;作者上大学期间 因为创始人在上大学期间经常需要浏览新闻和处理邮件&#xff0c;发现现有的操作系统不好用,于是他决心自己写一个保护模式下的操作系统&#xff0c;这就是Linux的原型&#xff0c;当时他…
阅读更多...
【MySQL】DCL

【MySQL】DCL

DCL英文全称是Data Control Language(数据控制语言)&#xff0c;用来管理数据库用户、控制数据库的访问权限。 1. 管理用户 在MySQL数据库中&#xff0c;DCL&#xff08;数据控制语言&#xff09;是用来管理用户和权限的语句集合。通过DCL语句&#xff0c;可以创建、修改、删…
阅读更多...
leetcode 重复的子字符串

leetcode 重复的子字符串

前要推理 以abababab为例&#xff0c;这里最主要的就是根据相等前后缀进行推导 s [ 0123 ] 如 t【 0123 】 f 【01 23 】 后两个分别是前后缀&#xff0c;第一个是总的字符串&#xff0c;然后可以推导 //首先还是算出…
阅读更多...
Spring的定时任务不生效、不触发，一些可能的原因，和具体的解决方法。

Spring的定时任务不生效、不触发，一些可能的原因，和具体的解决方法。

1 . 未在启动类上加 EnableScheduling 注解 原因&#xff1a;未在Spring Boot应用主类上添加EnableScheduling注解或未在XML配置文件中配置定时任务的启用。解决方法&#xff1a;确保在应用的配置类上添加EnableScheduling注解&#xff0c;启用定时任务。 2 . cron 表达式书写…
阅读更多...
最新文章

Copyright @ 2022~2023