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

前言

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

原始冒泡排序

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

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

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

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

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

/*
冒泡排序后的顺序为从小到大
*/
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,退出循环。代码实现如下:

/*
冒泡排序后的顺序为从小到大
*/
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、依次循环执行,直到最大的元素放在了最后一个位置上,排序完成。

更多精彩内容:http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

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

/*
第一种形式的选择排序
选择排序后的顺序为从小到大
*/
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;
            }
}

改进选择排序

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

/*
第二种形式的选择排序,减少了元素互换的操作
选择排序后的顺序为从小到大
*/
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博客 兰亭风雨

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索排序
, 冒泡排序
, 代码
, 元素
, 选择
, 选择排序
, 序列
, 冒泡排序 noj
, 冒泡排序java日期
, 冒泡排序python
, 冒泡排序代码
, c++冒泡排序
, java冒泡排序
从小到大
,以便于您获取更多的相关知识。

时间: 2024-10-22 10:52:17

内部排序:冒泡排序和选择排序的相关文章

C#的四种排序算法:冒泡排序、选择排序、插入排序和希尔排序

插入|排序|算法 本文介绍了C#的四种排序算法:冒泡排序.选择排序.插入排序和希尔排序 冒泡排序 using System: namespace BubbleSorter { public class BubbleSorter { public void Sort(int [] list) { int i,j,temp: bool done=false: j=1: while((j<list.Length)&&(!done)) { done=true: for(i=0:i<li

冒泡排序与选择排序的不同、快速排序与选择排序的结合

冒泡排序可以说是最简单的排序了.我们学习C语言循环的时候都会提到. 可见这是一种浅而易懂的排序算法! 但不见得这种算法就没用处.首先,他很容易理解,这样在各种教材中比较适合拿来"开门见山".其次是他很稳定. 若明确知道即将排的数字很混乱,随机性很强,则用冒泡排序也未偿不可. 谁让他始终是O(n^2)呢. 冒泡排序法代码:  1void BubbleSort(int a[],int l) 2{ 3    for(int i = 0; i< l;++i) 4    { 5      

Go语言实现冒泡排序、选择排序、快速排序及插入排序的方法_Golang

本文实例讲述了Go语言实现冒泡排序.选择排序.快速排序及插入排序的方法.分享给大家供大家参考.具体分析如下: 算法是程序的灵魂,而排序算法则是一种最基本的算法.排序算法有许多种,这里介绍4中排序算法:冒泡排序,选择排序,快速排序和插入排序,以从小到大为例. 一.冒泡排序 冒泡排序的原理是,对给定的数组进行多次遍历,每次均比较相邻的两个数,如果前一个比后一个大,则交换这两个数.经过第一次遍历之后,最大的数就在最右侧了:第二次遍历之后,第二大的数就在右数第二个位置了:以此类推. 复制代码 代码如下:

C++实现八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序等_C 语言

本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是算法实现文件Sort.h,代码如下: /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ #include <iostream> template<class T> void swap_value(T &a, T &b) { T t

JavaScript 冒泡排序和选择排序的实现代码_javascript技巧

废话不多说了,直接给大家贴代码了,具体代码如下所述: var array = [1,2,3,4,5]; // ---> 服务 //效率 ---> 针对一个有序的数组 效率最高 //标志 true false for(var j = 0; j < array.length - 1;j++ ){ //- j 每次排序完成之后 后面减少比较的次数 var isTrue = true; //如果数组本身就是升序,则直接输出 for(var i = 0; i < array.length -

常见的五类排序算法图解和实现(选择类:简单选择排序,锦标赛排序,树形选择排序,堆排序)

选择类的排序算法 简单选择排序算法 采用最简单的选择方式,从头到尾扫描待排序列,找一个最小的记录(递增排序),和第一个记录交换位置,再从剩下的记录中继续反复这个过程,直到全部有序. 具体过程: 首先通过 n –1 次关键字比较,从 n 个记录中找出关键字最小的记录,将它与第一个记录交换. 再通过 n –2 次比较,从剩余的 n –1 个记录中找出关键字次小的记录,将它与第二个记录交换. 重复上述操作,共进行 n –1 趟排序后,排序结束. 如图   过程图解 令 k=i:j = i + 1: 目

排序高级之选择排序_选择排序

选择排序(Selection sort)是一种简单直观的排序算法.它的工作原理如下.首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕. 选择排序的主要优点与数据移动有关.如果某个元素位于正确的最终位置上,则它不会被移动.选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换.在所有的完全依靠交换去移动元素的排序方

数据结构例程——选择排序之直接选择排序

本文是[数据结构基础系列(9):排序]中第6课时[选择排序之直接选择排序]的例程. #include <stdio.h> #define MaxSize 20 typedef int KeyType; //定义关键字类型 typedef char InfoType[10]; typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType; //排序的记录类型定义 void Sele

深入Java冒泡排序与选择排序的区别详解_java

冒泡排序它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.代码如下: 复制代码 代码如下: public class nums {     public static void main(String[] args){         int []nums = {5,4,3,2,1};         for(int i = 0; i < nums.length; i++){