内部排序之二:冒泡排序和选择排序

2024-09-02 06:08

本文主要是介绍内部排序之二:冒泡排序和选择排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

前言

   之所以把冒泡排序和选择排序放在一起,是因为二者的实现代码很相似,而且都是最基本的排序方式,非常容易理解和实现。当然,如果仅仅是为了讲述这两种排序方式,那也根本没必要写这篇博文了。和上篇博文一样,我会在冒泡排序和选择排序原始代码的基础上给出一些改进和优化,这才是本文的重点所在。

原始冒泡排序

   冒泡排序的思想很简单,如果要求排序后序列中元素按照从小到大的顺序排列,则冒泡排序的步骤如下:

   1、依次比较序列中相邻的两个元素,将较大的放在后面,这样一趟比较后,最大的元素就放在了最后的一个位置;

   2、再依次比较相邻的两个元素,将第二大的元素最终放到倒数第二个位置;

   3、依次循环,直到最小的元素放在了第一个位置,排序完成。

   根据以上思想,很容易写出代码:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
冒泡排序后的顺序为从小到大
*/
void Bubble_Sort( int *arr, int len) 
     int i,j,exchange; 
     for (i=0;i<len-1;i++) 
         for (j=0;j<len-i-1;j++) 
             if (arr[j] > arr[j+1]) 
            
                 exchange = arr[j]; 
                 arr[j] = arr[j+1]; 
                 arr[j+1] = exchange; 
            
}

改进冒泡排序


   我们回过头来再来看上面冒泡排序的思想,无论原始序列的排序是怎样的(哪怕已经是从小到大排好的),它都要进行n-1趟比较,每趟比较又要进行n-i-1次相邻元素间的比较(i为从0开始计的第i趟比较),而实际上,很有可能还没有进行第n-1趟比较,已经完成了排序,这时候后面的几趟比较就显得多余了,基于此,我们可以做如下改进:设置一个标志位,如果某一趟有元素发生交换,则为true,继续下一趟比较,否则,说明排序已经完成,则标志位为false,退出循环。代码实现如下:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
冒泡排序后的顺序为从小到大
*/
void Bubble_Sort( int *arr, int len) 
     int i,j,exchange; 
     bool flag = true ;   //增设标志位,判断是否已经完成排序 
     for (i=0; i<len-1 && flag; i++) 
    
         flag = false
         for (j=0;j<len-i-1;j++) 
             if (arr[j] > arr[j+1]) 
             {   //如果本趟比较没有数据发生交换,说明排序已经完成 
                 //则flag一直为false,从而退出循环,不再进行下一趟的比较 
                 exchange = arr[j]; 
                 arr[j] = arr[j+1]; 
                 arr[j+1] = exchange; 
                 flag = true
            
    
}

直接选择排序

   直接选择排序的思想也很简单,以排序从小到大为例,如下:

   1、从第一个元素开始,选出一个最小的元素与第一个元素互换;

   2、继续从第二个元素开始,向后选出最小的元素,与第二个元素互换;

   3、依次循环执行,直到最大的元素放在了最后一个位置上,排序完成。

   我们可以将第一个元素分别与后面的元素进行比较,遇到更小的,就交换,这样一趟比较下来,第一个元素保存就是最小值,而后再从第二个元素开似乎,依次与后面的元素比较,遇到更小的,就交换,这样,第二趟比较下来,第二个元素保存的就是第二小的值。。。依次循环执行,直到完成排序。按照这样的思路,实现代码如下:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/*
第一种形式的选择排序
选择排序后的顺序为从小到大
*/
void Select_Sort1( int *arr, int len) 
     int i,j; 
     for (i=0;i<len;i++) 
         for (j=i+1;j<len;j++) 
             if (arr[i] > arr[j]) 
            
                 int exchange = arr[i]; 
                 arr[i] = arr[j]; 
                 arr[j] = exchange; 
            
}

改进选择排序


   但是我们上篇文章中提到过,在排序中应该尽量避免较多的和元素互换操作,而这里每比较一次,如果遇到更小的,就要互换一次元素。为了减少元素互换操作,我们可以在每次比较后不直接进行交换,将较小的元素的位置序号记录下来,这样一趟比较之后,就会得到最小元素的位置,如果最小值的位置发生了改变,再将该位置的元素与第一个元素互换,依次类推。。。这样每一趟比较完成后最多只需执行一次元素互换的操作。实现代码如下:

双击代码全选
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*
第二种形式的选择排序,减少了元素互换的操作
选择排序后的顺序为从小到大
*/
void Select_Sort2( int *arr, int len) 
     int i,j,min; 
     for (i=0;i<len;i++) 
    
         min = i;    //用来记录每一趟比较的最小值的位置 
         for (j=i+1;j<len;j++) 
             if (arr[min] > arr[j]) 
                 min = j;     //仅记录最小值的位置 
         //如果最小值的位置发生了变化, 
         //则最后执行一次元素互换的操作 
         if (min != i) 
        
             int exchange = arr[i]; 
             arr[i] = arr[min]; 
             arr[min] = exchange; 
        
    
}

总结

   冒泡排序和选择排序都是最基本的排序算法,平均时间复杂度都为O(n*n),排序元素个数较少时,适合使用,遇到大数据量时,最好选用其他排序算法。

完整源码

   完整的C语言实现代码下载地址:http://download.csdn.net/detail/mmc_maodun/6970951

来源: csdn   作者:兰亭风雨  
源自:http://tech.ddvip.com/2014-03/1394804403209162.html

这篇关于内部排序之二:冒泡排序和选择排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

如何选择适合孤独症兄妹的学校?

在探索适合孤独症儿童教育的道路上,每一位家长都面临着前所未有的挑战与抉择。当这份责任落在拥有孤独症兄妹的家庭肩上时,选择一所能够同时满足两个孩子特殊需求的学校,更显得尤为关键。本文将探讨如何为这样的家庭做出明智的选择,并介绍星贝育园自闭症儿童寄宿制学校作为一个值得考虑的选项。 理解孤独症儿童的独特性 孤独症,这一复杂的神经发育障碍,影响着儿童的社交互动、沟通能力以及行为模式。对于拥有孤独症兄

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

C#实战|大乐透选号器[6]:实现实时显示已选择的红蓝球数量

哈喽,你好啊,我是雷工。 关于大乐透选号器在前面已经记录了5篇笔记,这是第6篇; 接下来实现实时显示当前选中红球数量,蓝球数量; 以下为练习笔记。 01 效果演示 当选择和取消选择红球或蓝球时,在对应的位置显示实时已选择的红球、蓝球的数量; 02 标签名称 分别设置Label标签名称为:lblRedCount、lblBlueCount

透彻!驯服大型语言模型(LLMs)的五种方法,及具体方法选择思路

引言 随着时间的发展,大型语言模型不再停留在演示阶段而是逐步面向生产系统的应用,随着人们期望的不断增加,目标也发生了巨大的变化。在短短的几个月的时间里,人们对大模型的认识已经从对其zero-shot能力感到惊讶,转变为考虑改进模型质量、提高模型可用性。 「大语言模型(LLMs)其实就是利用高容量的模型架构(例如Transformer)对海量的、多种多样的数据分布进行建模得到,它包含了大量的先验

hdu 1285(拓扑排序)

题意: 给各个队间的胜负关系,让排名次,名词相同按从小到大排。 解析: 拓扑排序是应用于有向无回路图(Direct Acyclic Graph,简称DAG)上的一种排序方式,对一个有向无回路图进行拓扑排序后,所有的顶点形成一个序列,对所有边(u,v),满足u 在v 的前面。该序列说明了顶点表示的事件或状态发生的整体顺序。比较经典的是在工程活动上,某些工程完成后,另一些工程才能继续,此时

cross-plateform 跨平台应用程序-03-如果只选择一个框架,应该选择哪一个?

跨平台系列 cross-plateform 跨平台应用程序-01-概览 cross-plateform 跨平台应用程序-02-有哪些主流技术栈? cross-plateform 跨平台应用程序-03-如果只选择一个框架,应该选择哪一个? cross-plateform 跨平台应用程序-04-React Native 介绍 cross-plateform 跨平台应用程序-05-Flutte

如何选择SDR无线图传方案

在开源软件定义无线电(SDR)领域,有几个项目提供了无线图传的解决方案。以下是一些开源SDR无线图传方案: 1. **OpenHD**:这是一个远程高清数字图像传输的开源解决方案,它使用SDR技术来实现高清视频的无线传输。OpenHD项目提供了一个完整的工具链,包括发射器和接收器的硬件设计以及相应的软件。 2. **USRP(Universal Software Radio Periphera

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

如何编写Linux PCIe设备驱动器 之二

如何编写Linux PCIe设备驱动器 之二 功能(capability)集功能(capability)APIs通过pci_bus_read_config完成功能存取功能APIs参数pos常量值PCI功能结构 PCI功能IDMSI功能电源功率管理功能 功能(capability)集 功能(capability)APIs int pcie_capability_read_wo