当前位置:  编程技术>c/c++/嵌入式

冒泡算法的改进具体实现

    来源: 互联网  发布时间:2014-10-23

    本文导语:  冒泡排序算法的思想: 首先将第一个记录的关键字和第二个关键字进行比较,若为逆序则将两个记录进行交换。然后比较第二个记录和第三个记录的关键字,直至第n-1个记录和第n个记录进行比较为止,一趟过后最大的元素会...

冒泡排序算法的思想:

首先将第一个记录的关键字和第二个关键字进行比较,若为逆序则将两个记录进行交换。
然后比较第二个记录和第三个记录的关键字,直至第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 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 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 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 Listt: ");

 for (int i = 0; i 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 Listt: ");

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

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

    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • JQuery中阻止事件冒泡几种方式及其区别介绍
  • C经典冒泡排序法实现代码
  • c#冒泡排序示例分享
  • shell编程中的冒泡排序问题
  • Python实现冒泡,插入,选择排序简单实例
  • jQuery中阻止冒泡事件的方法介绍
  • c++冒泡排序示例分享
  • c语言冒泡排序法代码
  • 冒泡排序的三种实现方法
  • jQuery中事件对象e的事件冒泡用法示例介绍
  • 一个小例子解释如何来阻止Jquery事件冒泡
  • 关于javascript冒泡与默认事件的使用详解
  • 深入Java冒泡排序与选择排序的区别详解
  • Java冒泡排序(Bubble Sort)实例讲解
  • 控制台显示java冒泡排序流程示例
  • Java中的数组排序方式(快速排序、冒泡排序、选择排序)
  • java冒泡排序和选择排序示例
  • php冒泡排序、快速排序、快速查找、二维数组去重实例分享
  • 用c语言实现冒泡排序,选择排序,快速排序
  • java数组排序示例(冒泡排序、快速排序、希尔排序、选择排序)


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3