冒泡算法的改进具体实现

冒泡排序算法的思想：

首先将第一个记录的关键字和第二个关键字进行比较，若为逆序则将两个记录进行交换。
然后比较第二个记录和第三个记录的关键字，直至第n-1个记录和第n个记录进行比较为止，一趟过后最大的元素会沉入最底部。
然后进行第二趟排序，对前 n-1 个记录进行同样1、2的操作，结果就是关键字次大的记录被安排到n-1位置上。
依次进行第 i 趟排序，对前 n-i 个记录进行同样的1、2的操作，直到一趟没有进行过任何比较的操作，排序结束。
先看一下基础冒泡算法：


代码如下:

int BubbleSort(MergeType* L)
{
 int i, j;
 for (i = 0; i <= L->len-1; i++)
 {  
  for (j = 0; j < L->len-1-i; j++)
  {
   if (L->elem[j+1] < L->elem[j])
   {
    SWAP(L->elem[j+1], L->elem[j] ); 
   }
  } 
 }

return 0;
}

这里的MergeType类型如下：


代码如下:

typedef struct _SQLIST{
    int* elem;
    int len;   //实际长度
    int size;  //分配空间
}SqList, *pSqList;

typedef _SQLIST MergeType;

核心思想是每次选出最大的数沉入底部，直至没有数据可比较。

首先计算一下它的时间复杂度，这里以最坏的情况来计算的话：

（n-1）+（n-2）+……+ 1 + 0 = n*（n-1）/ 2  = O(n^2)

最好的情况就是已经排序好，不需要进行比较
首先看到其不足之一：就是频繁交换元素。如何避免，可以存放在一个合适的位置，精简算法一：


代码如下:

int BubbleSortEx(MergeType* L)
{
 int i = 0, j = 0;
 int max, temp;
 for (i = 0; i <= L->len-1; i++)
 {  
  temp = L->elem[0];
  max = 0;
  for (j = 1; j < L->len-i; j++)
  {   
   if (L->elem[j] > temp)
   {
    temp = L->elem[j];
    max = j;
   }
  }
  //printf("%d:%d \n", max, temp);
  swap(L->elem[L->len-1-i], L->elem[max] );   
 }

return 0;
}

看到这里每次仍然需要频繁的进行赋值操作，当然只是微不足道的，但是赋值也会增加cpu执行的时间，所以精简算法二:


代码如下:

int BubbleSortEx(MergeType* L)
{
 int i, j , max;
 for (int i = 0; i <= L->len-1; i++)
 {  
  max = 0;
  for (j = 1; j < L->len-i; j++)
  {   
   if (L->elem[j] > L->elem[max])
   {
    max = j;
   }
  }
  //printf("%d:%d \n", max, L->elem[max]);
  swap(L->elem[L->len-1-i], L->elem[max] );   
 }

return 0;
}

这里的两个swap是不一样的，当然也可以使用一样的，看如下具体的实现：


代码如下:

#define SWAP(a, b) \
{                 \
 int temp = (a); \
 (a) = (b);        \
 (b) = temp;     \
}

代码如下:

inline void swap(int& a, int& b)
{
 int temp = a;
 a = b;
 b = temp;
}

第一个是采用宏替换，当然主要是增加预处理的时间，主要是用宏会出现意想不到的错误
第二个是函数，这里使用了引用，可以减少指针使用的形参变量副本的创建，但是这里使用了inline，所以还是替换

测试程序：


代码如下:

int PrintList(MergeType *L);
int ScanfList(MergeType *L, const int nScanfType = -1);

int SortTest()
{
 printf("--- %s ---\n", __FUNCTION__);
 MergeType pList;
 MergeType pT;

pList.elem = (int*)malloc(sizeof(int)*10);
 pList.len  = 10;
 pList.size  = 10;

ScanfList(&pList); /*输入数据*/

BubbleSortEx(&pList);/*冒泡排序*/

PrintList(&pList);/*输出数据*/

free(pList.elem);
 pList.elem = NULL;

return 0;
}

数据输入：


代码如下:

int ScanfList(MergeType *L, const int nScanfType)
{
 if (!L->elem)
 {
  return -1;
 }

printf("Old List\t: ");

for (int i = 0; i <= L->len; i++ )
 {
  if( i == L->len )
  {
   printf("\n");
   break;
  }
  switch (nScanfType)
  {
  case 0:
   {
    break;
   }
  default:
   L->elem[i] = 11 * i - i * i;
   break;
  }  
  printf("%d ", L->elem[i]);
 }
 return 0;
}

数据输出：


代码如下:

int PrintList(MergeType *L)
{ 
 if (!L->elem)
 {
  return -1;
 }

printf("Sort List\t: ");

for (int i = 0; i <= L->len; i++ )
 {
  if (i == L->len)
  {
   printf("\n");

break;
  }
  printf("%d ", L->elem[i]);
 }
 return 0;
}

赞 (0)

相关推荐

  • C++ 基本算法 冒泡法、交换法、选择法、实现代码集合

    1.冒泡法: 这是最原始,也是众所周知的最慢的算法了.他的名字的由来因为它的工作看来象是冒泡: 复制代码 代码如下: #include <iostream.h> void BubbleSort(int* pData,int Count) { int iTemp; for(int i=1;i<Count;i++) { for(int j=Count-1;j>=i;j--) {if(pData[j]<pData[j-1]) { iTemp = pData[j-1]; pData[

  • c# 冒泡排序算法(Bubble Sort) 附实例代码

    c# 冒泡排序算法(Bubble Sort) 附实例代码

    冒泡排序(Bubble Sort) 冒泡排序算法的运作如下: 1.比较相邻的元素.如果第一个比第二个大,就交换他们两个.2.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应该会是最大的数.3.针对所有的元素重复以上的步骤,除了最后一个.4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较. 平均时间复杂度 复制代码 代码如下: /// <summary> /// 冒泡排序 /// </summary> /// <param

  • python冒泡排序算法的实现代码

    1.算法描述:(1)共循环 n-1 次(2)每次循环中,如果 前面的数大于后面的数,就交换(3)设置一个标签,如果上次没有交换,就说明这个是已经好了的. 2.python冒泡排序代码 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- def bubble(l):    flag = True    for i in range(len(l)-1, 0, -1):        if flag:             flag = False

  • java冒泡排序算法代码

    复制代码 代码如下: /** * 原理: * 进行n次循环,每次循环从后往前对相邻两个元素进行比较,小的往前,大的往后 *  * 时间复杂度: * 平均情况:O(n^2) * 最好情况:O(n) * 最坏情况:O(n^2) * * 稳定性:稳定 **/public class 冒泡排序 { public int[] bubbleSort(int[] a, int n) {        for (int i = 0; i < n; i++) {            int flag = 0; 

  • 基于php冒泡排序算法的深入理解

    交换排序的基本思想:两两比较待排序的数据,如果发生逆序,则交换之,直到全部数据都排好序为止.•冒泡排序的基本思想:1.从后往前,扫描所有的数据,如果相邻的两个数发生逆序,则互换.--第1趟冒泡2.从后往前,扫描最后一个到第2个数据,如果相邻的两个数发生逆序,则互换.--第2趟冒泡3.如此依次进行,直到进行n-1趟冒泡,或者在某趟冒泡中,没有逆序的情况即可提前结束. 复制代码 代码如下: <script>var arr = [15,8,7,9,10,0]; var _len = arr.leng

  • 深入理解PHP几个算法:PHP冒泡、PHP二分法、PHP求素数、PHP乘法表

    PHP几个算法整理 涉及到以下几个示例.PHP冒泡PHP二分法PHP求素数PHP乘法表 PHP冒泡法 示例 复制代码 代码如下: //PHP冒泡  从小到大function maopao(&$arr){  if(!empty($arr))  {    for($i=0;$i<count($arr);$i++)      {        if($arr[$i]>$arr[$j])        {          //开始交换          $temp = $arr[$i];  

  • C++ 冒泡排序数据结构、算法及改进算法

    程序代码如下: 复制代码 代码如下: // BubbleSort.cpp : 定义控制台应用程序的入口点.//#include "stdafx.h"#include <cmath>#include <iostream>using namespace std;#define  MAXNUM 20template<typename T>void Swap(T& a, T& b){    int t = a;    a = b;    b

  • 冒泡算法的改进具体实现

    冒泡排序算法的思想: 首先将第一个记录的关键字和第二个关键字进行比较,若为逆序则将两个记录进行交换.然后比较第二个记录和第三个记录的关键字,直至第n-1个记录和第n个记录进行比较为止,一趟过后最大的元素会沉入最底部.然后进行第二趟排序,对前 n-1 个记录进行同样1.2的操作,结果就是关键字次大的记录被安排到n-1位置上.依次进行第 i 趟排序,对前 n-i 个记录进行同样的1.2的操作,直到一趟没有进行过任何比较的操作,排序结束.先看一下基础冒泡算法: 复制代码 代码如下: int Bubbl

  • PHP冒泡算法详解（递归实现）

    实现 复制代码 代码如下: /*     冒泡算法(递归实现) */ function maoPao($array, $index=0) {     $count = count($array);     if(($count-1) <= $index)         return $array; for($i=$count-1; $i>$index; $i-- )     {         if($array[$i] < $array[$i-1])         {       

  • 冒泡算法的三种JavaScript表示

    以前学习冒泡算法,总是弄不清楚n和n-1等一些变量的关系,原因是没有弄明白它的真正含义,今天写了一个冒泡算法的JS小程序,终于弄明白了. 复制代码 代码如下: var R1=new Array(); R1[1]=35; R1[2]=55; R1[3]=65; R1[4]=20; R1[5]=30; R1[6]=25; R1[7]=0; R1[8]=7; R1[9]=5; R1[10]=3; var R2=new Array(35,55,65,20,30,25,0,7,5,3); var R3=n

  • Python编程二分法实现冒泡算法+快速排序代码示例

    本文分享的实例主要是Python编程二分法实现冒泡算法+快速排序,具体如下. 冒泡算法: #-*- coding: UTF-8 -*- #冒泡排序 def func(lt): if type(lt).__name__ !='list' and type(lt).__name__ !='tuple': return if type(lt).__name__ == 'tuple': return list(lt) for i in range(1,len(lt)-1): for j in range

  • 详解易语言的冒泡算法

    详解易语言的冒泡算法

    我们做一些游戏脚本软件时候,经常要用到这个算法,比如求解离自己身边最近的怪物优先攻击,就要用到这个算法,冒泡算法可以快速的把一组数据按照从大到小,或者从小到大的顺序进行快速排序. 冒泡算法的核心就是,从第一位开始把数据提取出来,跟余下的数据逐一进行比大或者小(看你是按照从大到小,还是从小到大顺序进行排),大或者小的数交换位置,第一位比较完毕后,再从二个位开始把数据提取出来,跟余下的数据进行比较,依次进行. 下面给出易语言源码 .版本 2 .支持库 spec .子程序 子程序_按照从小到大排序 .

  • JavaScript冒泡算法原理与实现方法深入理解

    本文实例讲述了JavaScript冒泡算法.分享给大家供大家参考,具体如下: 在面试中经常会遇到面试官问到冒泡算法.今天总结一下. ###概念 有一组数,依次比较两个相邻的数,如果他们的顺序(如从大到小或从小到大等)错误就把他们交换过来. 我们先假设这一组数是有顺序的,那么我们找出它的规则. 我们按照从小到大的顺序依次交换长方形,得到以下的结果. 第一轮交换结果:CBAD     交换次数:3次 第二轮交换结果:BACD     交换次数:3次 第三轮交换结果:ABCD     交换次数:3次

  • asp.net 冒泡算法的理解

    复制代码 代码如下: /*您真的理解冒泡排序吗?还是背下来了呢?冒泡排序真的只有一种方法吗? * 有些东西别想太复杂,简简单单的解决不是更好? * 虽然方法不一样,思想都是大同小异,希望读者仔细体会...... * */ using System; namespace Sort { public class Sort { //冒泡排序 一 //是不是很不好理解?没关系,看看下一种方法,绝对好理解 public void BubbleSort(int[] a) { //定义一个临时变量,为了交换位

  • 浅析直接插入排序与折半插入排序

    首先看一下例子,将数据一个个的插入到一个列表中,插入后这个列表就排序好了 注意:这个列表是递增的,而且内存空间已分配好,只是没有填充真正的数据,如下代码: 复制代码 代码如下: int InsertSort(MergeType *L, int data){ int j; if (!L->len) {  L->elem[++L->len] = data;  return 0; } for (j = L->len-1; j >= 0; --j) {  if (data <

  • C 语言基础教程(我的C之旅开始了)[八]

    19. 基本数据类型:复数类型和虚数类型 C99 新增了复数类型(_Complex)和虚数类型(_Imaginary).简单来说,C99 提供了三种复数类型:float _Complex,double _Complex,和 long double _Complex.对于 float _Complex 类型的变量来说,它包含两个 float 类型的值,一个用于表示复数的实部(real part),另一个用于表示虚部(imaginary part).类似地,double _Complex 包含两个

随机推荐