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

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。

相关文章

Python多线程实现大文件快速下载的代码实现

Python多线程实现大文件快速下载的代码实现

《Python多线程实现大文件快速下载的代码实现》在互联网时代,文件下载是日常操作之一,尤其是大文件,然而,网络条件不稳定或带宽有限时,下载速度会变得很慢,本文将介绍如何使用Python实现多线程下载... 目录引言一、多线程下载原理二、python实现多线程下载代码说明：三、实战案例四、注意事项五、总结引
阅读更多...
redis数据结构之String详解

redis数据结构之String详解

《redis数据结构之String详解》Redis以String为基础类型,因C字符串效率低、非二进制安全等问题,采用SDS动态字符串实现高效存储,通过RedisObject封装,支持多种编码方式（如... 目录一、为什么Redis选String作为基础类型？二、SDS底层数据结构三、RedisObject
阅读更多...
C#使用Spire.XLS快速生成多表格Excel文件

C#使用Spire.XLS快速生成多表格Excel文件

《C#使用Spire.XLS快速生成多表格Excel文件》在日常开发中,我们经常需要将业务数据导出为结构清晰的Excel文件,本文将手把手教你使用Spire.XLS这个强大的.NET组件,只需几行C#... 目录一、Spire.XLS核心优势清单1.1 性能碾压：从3秒到0.5秒的质变1.2 批量操作的优雅
阅读更多...
Mybatis-Plus 3.5.12 分页拦截器消失的问题及快速解决方法

Mybatis-Plus 3.5.12 分页拦截器消失的问题及快速解决方法

《Mybatis-Plus3.5.12分页拦截器消失的问题及快速解决方法》作为Java开发者,我们都爱用Mybatis-Plus简化CRUD操作,尤其是它的分页功能,几行代码就能搞定复杂的分页查询... 目录一、问题场景：分页拦截器突然 “失踪”二、问题根源：依赖拆分惹的祸三、解决办法：添加扩展依赖四、分页
阅读更多...
c++日志库log4cplus快速入门小结

c++日志库log4cplus快速入门小结

《c++日志库log4cplus快速入门小结》文章浏览阅读1.1w次，点赞9次，收藏44次。本文介绍Log4cplus，一种适用于C++的线程安全日志记录API，提供灵活的日志管理和配置控制。文章涵盖... 目录简介日志等级配置文件使用关于初始化使用示例总结参考资料简介log4j 用于Java，log4c
阅读更多...
C++归并排序代码实现示例代码

C++归并排序代码实现示例代码

《C++归并排序代码实现示例代码》归并排序将待排序数组分成两个子数组,分别对这两个子数组进行排序,然后将排序好的子数组合并,得到排序后的数组,：本文主要介绍C++归并排序代码实现的相关资料,需要的... 目录1 算法核心思想2 代码实现3 算法时间复杂度1 算法核心思想归并排序是一种高效的排序方式，需要用
阅读更多...
使用Redis快速实现共享Session登录的详细步骤

使用Redis快速实现共享Session登录的详细步骤

《使用Redis快速实现共享Session登录的详细步骤》在Web开发中,Session通常用于存储用户的会话信息,允许用户在多个页面之间保持登录状态,Redis是一个开源的高性能键值数据库,广泛用于... 目录前言实现原理：步骤：使用Redis实现共享Session登录1. 引入Redis依赖2. 配置R
阅读更多...
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（详细信
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2