数据结构--排序算法(冒泡排序快速排序鸽巢排序)

2023-11-01 04:32
文章标签 算法 快速 数据结构 排序 冒泡排序 鸽巢

本文主要是介绍数据结构--排序算法(冒泡排序快速排序鸽巢排序)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

插入排序以及选择排序请查阅我往期博客：http://blog.csdn.net/sayhello_world/article/details/61927082


冒泡排序：

思想：两两交换，大的放到后面。重复size-1次


代码实现：

[cpp]  view plain copy
  1. //冒泡排序  
  2. void Bubble_Sort(int array[],int size)  
  3. {  
  4.     for(int idx= 0; idx < size;++idx)  
  5.     {  
  6.        for(int index= 0; index < size-1-idx;++index)  
  7.        {  
  8.            if(array[index]> array[index+1])  
  9.            {  
  10.               std::swap(array[index],array[index+1]);  
  11.            }  
  12.        }  
  13.     }  
  14. }  


冒泡排序的优化：

思想：对冒泡排序常见的改进方法是加入一标志性变量flag，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。

代码实现：

[cpp]  view plain copy
  1. //冒泡排序优化  
  2. void Bubble_Sort2(int array[], int size)  
  3. {  
  4.     bool flag = true;  
  5.     while (flag)  
  6.     {  
  7.         flag = false;  
  8.         for (int index = 0; index < size - 1; ++index)  
  9.         {  
  10.             if (array[index] > array[index + 1])  
  11.             {  
  12.                 std::swap(array[index], array[index + 1]);  
  13.                 flag = true;  
  14.             }  
  15.         }  
  16.     }  
  17. }  

 

快速排序：

递归：

快速排序第一种方法：

思想：选取一个数字为比较值，用右值和他比较，如果右值比他小就将他给左边，左边加一。

若左边比他大，就将他给右边，右边减一。如此当left==right时，说明此比较值的地方就应该在此，然后递归，先排此地点的左边再排此地点的右边。

 

优化：可以写一个函数为查找最左边下标，最右边下标以及中间下标的中间值，在数组范围内比较数组下标第一个，最后一个，和中间值得元素，尽可能将值为中间的元素当成key值，这样可以提高效率。（因为递归时左和右都有将近一半的数据）

代码：

[cpp]  view plain copy
  1. //三数取中法  
  2. int FindMidIndex(int array[],int left,int right)  
  3. {  
  4.     int mid= right - ((right- left) >> 1);  
  5.     if(array[left]<= array[mid])  
  6.     {  
  7.    
  8.        if(array[right]< array[left])  
  9.            return left;  
  10.        if(array[right]> array[mid])  
  11.            return mid;  
  12.        else  
  13.            return right;  
  14.     }  
  15.     if(array[left]> array[mid])  
  16.     {  
  17.        if(array[right]> array[mid])  
  18.            return mid;  
  19.        if(array[right]> array[left])  
  20.            return left;  
  21.        else  
  22.            return right;  
  23.     }  
  24.     return 0;  
  25. }  
  26.    


全过程



时间复杂度：O（NlogN）

空间复杂度：O（1）

稳定性：不稳定

代码实现：

[cpp]  view plain copy
  1. int Quick_Pass1(int array[],int left,int right)  
  2. {  
  3.     //设置一个比较的值尽量让比较值为较为中间的值  
  4.     int keyIdx= FindMidIndex(array,left,right);  
  5.     std::swap(array[keyIdx],array[right]);  
  6.    
  7.     int temp= array[right];  
  8.    
  9.     while(left < right)  
  10.     {  
  11.        //如果这时左边比比较值大左边给右边右边前移  
  12.        while(left < right&& array[left]< temp)  
  13.            left++;  
  14.        if(left < right)  
  15.        {  
  16.            array[right]= array[left];  
  17.            right--;  
  18.        }  
  19.    
  20.        //如果右边比比较值小则右边的数值给左边，左边后移  
  21.        while(left < right&& array[right]>= temp)  
  22.            right--;  
  23.        if(left < right)  
  24.        {  
  25.            array[left]= array[right];  
  26.            left++;  
  27.        }  
  28.     }  
  29.     //最后一个他俩相等的时候把中间比较值给过来返回中间的下标  
  30.     array[left]= temp;  
  31.     returnleft;  
  32. }  

快速排序第二种方法：


思路：给两个指针，第一个为Cur，第二个为prev，比较值为key，当Cur小于等于right时就一直循环。（这里如果没有等于就会少比较一次）当cur下标的元素小于比较值得时候，并且++prev！=cur ,就让array[cur]和array[prev]交换。当走完了之后，最后一个数据array[right]应该和array[++prev]交换，因为没有比较最后一个（cur下标的元素小于比较值，这里没有等于），也就少换了一个。

一趟之后：


代码实现：

[cpp]  view plain copy
  1. //设置一个Pre与Cur 当Cur<=right的时候，就循环  
  2. //当遇到Cur<key且Pre下一个不为Cur时,就让array[Cur]与array[Pre]交换  
  3. //找小于key的数与大于key的数字交换  
  4. int Quick_Pass2(intarray[],intleft,intright)  
  5. {  
  6.     int cur= left;  
  7.     int prev= cur - 1;  
  8.     int keyIdx= FindMidIndex(array,left,right);  
  9.     std::swap(array[keyIdx],array[right]);  
  10.     int key= array[right];  
  11.    
  12.     while(cur <= right)  
  13.     {  
  14.        //这里不用<=是因为防止重复数据若出现重复复数据会交换很多次  
  15.        if(array[cur]< key && ++prev!= cur)  
  16.            std::swap(array[cur],array[prev]);  
  17.    
  18.        ++cur;  
  19.     }  
  20.     std::swap(array[++prev],array[right]);  
  21.     return prev;  
  22. }  

递归优化：

我们可知，当数据量较小的时候直接插入排序比较高效，所以当数据量较小的时候我们可以选择插入排序，当数据量较大的时候我们选择快速排序。

代码实现：

[cpp]  view plain copy
  1. //递归快速排序  
  2. void Quick_Sort(intarray[],intleft,intright)  
  3. {  
  4.     if(right - left<16)  
  5.     {  
  6.        Insert_Sort(array,right-left+1);  
  7.     }  
  8.    
  9.     else  
  10.     {  
  11.        //先找到第一个数字应该放的点  
  12.        intpos= Quick_Pass1(array,left,right);  
  13.        //排这个数的左边的范围  
  14.        Quick_Sort(array,left,pos-1);  
  15.        //排这个数右边的范围  
  16.        Quick_Sort(array, pos+ 1,right);  
  17.     }  
  18. }  


快速排序非递归：

思路：递归转换为非递归一般用栈。我们向栈中保存数组下标，通过循环来进行排序。

代码实现：

[cpp]  view plain copy
  1. //非递归快速排序  
  2. void Quick_Sort_Nor(intarray[],intleft,intright)  
  3. {  
  4.     stack<int> s;  
  5.     s.push(right);  
  6.     s.push(left);  
  7.    
  8.     while(!s.empty())  
  9.     {  
  10.        left= s.top();  
  11.        s.pop();  
  12.        right= s.top();  
  13.        s.pop();  
  14.    
  15.        intdiv= Quick_Pass2(array,left,right);  
  16.        //此时可能会出现越界的问题如果最后一个就为最大值或者第一个就为最小值  
  17.        if(div - 1 > left)  
  18.        {  
  19.            //因为上面是先读取左再读取右  所以这里为先压右再压左  
  20.            s.push(div - 1);  
  21.            s.push(left);  
  22.        }  
  23.    
  24.        if(div + 1 < right)  
  25.        {  
  26.            s.push(right);  
  27.            s.push(div + 1);  
  28.        }  
  29.     }  
  30. }  

鸽巢排序：

思路：如果遇见数据量大，数据杂乱度较高的一组数据。我们可以通过重新建立一个数组，此数组中存储数字出现的次数，下标加上最小的一个数字，此数字就为存入的数字。

最终只需要在新数组中存放存储数字即可。

时间复杂度：O（M+N）（M为存元素数目的区间，N为原数组区间）

空间复杂度：O（N）（N为区间大小）

实现代码：

[cpp]  view plain copy
  1. //鸽巢排序  
  2. //思路:把数据存到一个数组里数组里存放次数据出现的次数  
  3. void Count_Sort(intarray[],intsize)  
  4. {  
  5.     int maxValue= array[0];  
  6.     int minValue= array[0];  
  7.    
  8.     for(int idx= 0; idx < size;++idx)  
  9.     {  
  10.        if(array[idx]> maxValue)  
  11.            maxValue= array[idx];  
  12.        if(array[idx]< minValue)  
  13.            minValue= array[idx];  
  14.     }  
  15.    
  16.     int range= maxValue - minValue+ 1;  
  17.     int* count = newint[range];  
  18.     memset(count, 0, sizeof(int)*range);  
  19.    
  20.     for(int idx= 0; idx < size;++idx)  
  21.     {  
  22.        count[array[idx]]++;  
  23.     }  
  24.    
  25.     size_t index = 0;  
  26.     for(int i= 0; i < range;++i)  
  27.     {  
  28.        for(int j= 0; j < count[i];++j)  
  29.        {  
  30.            array[index++]= minValue+i;  
  31.        }  
  32.     }  
  33.    
  34.     delete[]count;  
  35. }  

这篇关于数据结构--排序算法(冒泡排序快速排序鸽巢排序)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/320514。

相关文章

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

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

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

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

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam
阅读更多...
Linux如何快速检查服务器的硬件配置和性能指标

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

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

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

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

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种快速易用的Python Matplotlib数据可视化方法汇总(附源码)

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

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

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

Java List排序实例代码详解

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

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

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言：法一：Arrays.sort()法二：冒泡排序法三：选择排序法四：反转排序法五：直接插入排序前言：几种常用的Java数组排序
阅读更多...
使用animation.css库快速实现CSS3旋转动画效果

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

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

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2