当前位置: 开发笔记 > 数据库 > 正文

冒泡算法的改进具体实现

作者：Y死一般的痛过 | 来源：互联网 | 2021-09-05 06:33

这篇文章主要介绍了冒泡算法的改进具体实现，有需要的朋友可以参考一下

冒泡排序算法的思想：

首先将第一个记录的关键字和第二个关键字进行比较，若为逆序则将两个记录进行交换。
然后比较第二个记录和第三个记录的关键字，直至第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 len-1-i; j++)
  {
   if (L->elem[j+1] 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 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 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;
}

算法
sql

推荐阅读

sql
新浪笔试题

1:有如下一段程序：packagea.b.c;publicclassTest{privatestaticinti0;publicintgetNext(){return ... [详细]

蜡笔小新 2024-12-27 19:32:17
数据库
优化ListView性能

本文深入探讨了如何通过多种技术手段优化ListView的性能，包括视图复用、ViewHolder模式、分批加载数据、图片优化及内存管理等。这些方法能够显著提升应用的响应速度和用户体验。 ... [详细]

蜡笔小新 2024-12-28 10:36:30
insert
深入理解 SQL 视图、存储过程与事务

本文详细介绍了SQL中的视图、存储过程和事务的概念及应用。视图为用户提供了一种灵活的数据查询方式，存储过程则封装了复杂的SQL逻辑，而事务确保了数据库操作的完整性和一致性。 ... [详细]

蜡笔小新 2024-12-27 17:40:42
sql
深入解析HTML中的标签及其应用场景

本文详细介绍了HTML中标签的使用方法和作用。通过具体示例，解释了如何利用标签为网页中的缩写和简称提供完整解释，并探讨了其在提高可读性和搜索引擎优化方面的优势。 ... [详细]

蜡笔小新 2024-12-27 17:05:37
sql
数据库内核开发入门 | 搭建研发环境的初步指南

本课程将带你从零开始，逐步掌握数据库内核开发的基础知识和实践技能，重点介绍如何搭建OceanBase的开发环境。 ... [详细]

蜡笔小新 2024-12-27 16:38:48
insert
MyBatis 动态 SQL 详解与应用

本文深入探讨 MyBatis 中动态 SQL 的使用方法，包括 if/where、trim 自定义字符串截取规则、choose 分支选择、封装查询和修改条件的 where/set 标签、批量处理的 foreach 标签以及内置参数和 bind 的用法。 ... [详细]

蜡笔小新 2024-12-27 16:20:10
sql
使用C#开发SQL Server存储过程的指南

本文介绍如何利用C#在SQL Server中创建存储过程，涵盖背景、步骤和应用场景，旨在帮助开发者更好地理解和应用这一技术。 ... [详细]

蜡笔小新 2024-12-27 14:24:17
sql
探索适用于Spring Boot的Web版SQL管理工具

本文探讨了适用于Spring Boot应用程序的Web版SQL管理工具，这些工具不仅支持H2数据库，还能够处理MySQL和Oracle等主流数据库的表结构修改。 ... [详细]

蜡笔小新 2024-12-27 14:21:10
insert
网站与MySQL数据库的连接与交互

本文详细介绍了如何通过多种编程语言（如PHP、JSP）实现网站与MySQL数据库的连接，包括创建数据库、表的基本操作，以及数据的读取和写入方法。 ... [详细]

蜡笔小新 2024-12-27 14:09:23
sql
MyBatis：深入解析与应用

在当前众多持久层框架中，MyBatis（前身为iBatis）凭借其轻量级、易用性和对SQL的直接支持，成为许多开发者的首选。本文将详细探讨MyBatis的核心概念、设计理念及其优势。 ... [详细]

蜡笔小新 2024-12-27 12:17:16
sql
DataGridView 保存时，为什么当前单元格的值无法保存？

在使用 DataGridView 时，如果在当前单元格中输入内容但光标未移开，点击保存按钮后，输入的内容可能无法保存。只有当光标离开单元格后，才能成功保存数据。本文将探讨如何通过调用 DataGridView 的内置方法解决此问题。 ... [详细]

蜡笔小新 2024-12-27 09:27:14
sql
在 Linux 系统中部署 PostgreSQL 数据库

本文详细介绍了如何在 Linux 平台上安装和配置 PostgreSQL 数据库。通过访问官方资源并遵循特定的操作步骤，用户可以在不同发行版（如 Ubuntu 和 Red Hat）上顺利完成 PostgreSQL 的安装。 ... [详细]

蜡笔小新 2024-12-27 03:46:27
sql
如何在PostgreSQL中查看数据表

本文将指导您使用pgAdmin工具连接到PostgreSQL数据库，并展示如何浏览和查找其中的数据表。通过简单的步骤，您可以轻松访问所需的表结构和数据。 ... [详细]

蜡笔小新 2024-12-26 19:55:24
insert
利用存储过程构建年度日历表的详细指南

本文将介绍如何使用SQL存储过程创建一个完整的年度日历表。通过实例演示，帮助读者掌握存储过程的应用技巧，并提供详细的代码解析和执行步骤。 ... [详细]

蜡笔小新 2024-12-26 18:20:17
insert
使用 SQLiteJDBC 和 HikariCP 实现 Java 程序连接 SQLite 数据库

本文介绍了如何通过 Maven 依赖引入 SQLiteJDBC 和 HikariCP 包，从而在 Java 应用中高效地连接和操作 SQLite 数据库。文章提供了详细的代码示例，并解释了每个步骤的实现细节。 ... [详细]

蜡笔小新 2024-12-26 17:34:42

Y死一般的痛过

这个家伙很懒，什么也没留下！

Tags | 热门标签

RankList | 热门文章