渐渐的到了校园招聘的时候，楼主的算法功底实在是不敢恭维；上不及数据挖掘、模式识别、机器学习等高级算法，也只有加强好自己的基本功了，对数据结构和算法书上的基本的算法做分析和实现；就先从排序算法开始吧，本文主要分析楼主学到的第一个冒泡排序算法。

一. 算法描述

    冒泡排序：依次比较相邻的数据，将小数据放在前，大数据放在后；即第一趟先比较第1个和第2个数，大数在后，小数在前，再比较第2个数与第3个数，大数在后，小数在前，以此类推则将最大的数"滚动"到最后一个位置；第二趟则将次大的数滚动到倒数第二个位置......第n-1(n为无序数据的个数)趟即能完成排序。

以下面5个无序的数据为例：

40 8 15 18 12 （文中仅细化了第一趟的比较过程）

第1趟: 8 15 18 12 40


第2趟: 8 15 12 18 40

第3趟: 8 12 15 18 40

第4趟: 8 12 15 18 40

二. 算法分析

平均时间复杂度：O(n2)

空间复杂度：O(1)  (用于交换)

稳定性：稳定

三. 算法实现

[cpp]  view plain copy
  1. //交换data1和data2所指向的整形  
  2. void DataSwap(int* data1, int* data2)  
  3. {  
  4.     int temp = *data1;  
  5.     *data1 = *data2;  
  6.     *data2 = temp;  
  7. }  
  8.   
  9. /******************************************************** 
  10. *函数名称：BubbleSort 
  11. *参数说明：pDataArray 无序数组； 
  12. *          iDataNum为无序数据个数 
  13. *说明：    冒泡排序 
  14. *********************************************************/  
  15. void BubbleSort(int* pDataArray, int iDataNum)  
  16. {  
  17.     for (int i = 0; i < iDataNum - 1; i++)   //走iDataNum-1趟  
  18.         for (int j = 0; j < iDataNum - i - 1; j++)      
  19.             if (pDataArray[j] > pDataArray[j + 1])  
  20.                 DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
  21. }  

四. 算法优化

还可以对冒泡排序算法进行简单的优化，用一个标记来记录在一趟的比较过程中是否存在交换，如果不存在交换则整个数组已经有序退出排序过程，反之则继续进行下一趟的比较。

[cpp]  view plain copy
  1. /******************************************************** 
  2. *函数名称：BubbleSort 
  3. *参数说明：pDataArray 无序数组； 
  4. *          iDataNum为无序数据个数 
  5. *说明：    冒泡排序 
  6. *********************************************************/  
  7. void BubbleSort(int* pDataArray, int iDataNum)  
  8. {  
  9.     BOOL flag = FALSE;    //记录是否存在交换  
  10.     for (int i = 0; i < iDataNum - 1; i++)    //走iDataNum-1趟  
  11.     {  
  12.         flag = FALSE;  
  13.         for (int j = 0; j < iDataNum - i - 1; j++)      
  14.             if (pDataArray[j] > pDataArray[j + 1])  
  15.             {  
  16.                 flag = TRUE;  
  17.                 DataSwap(&pDataArray[j], &pDataArray[j + 1]);  
  18.             }  
  19.           
  20.         if (!flag)    //上一趟比较中不存在交换，则退出排序  
  21.             break;  
  22.     }  
  23. }  


感觉博文还是单薄了些，欠缺一些工程应用背景；希望有朋友能够一起讨论，一起温习曾经的基础。

Logo
CSDN学习社区

CSDN联合极客时间，共同打造面向开发者的精品内容学习社区，助力成长！

更多推荐

嵌入式作业（七）：基于Ardunio的STM32串口通信

嵌入式作业（七）0作业要求1Ardunio 完成STM32的串口通信（1）安装Ardunio IDE（2）stm32串口通信2关于 stduino IDE0作业要求安装 Ardunio IDE 和相关软件支持库，在Ardunio 完成STM32板子的串口通信程序：（1）持续向串口输出“Hello world！”；（2）当接收到“stop!”时，停止输出。网上有一个国人版的MCU集成开发平台， st

avatar CSDN学习社区

JDBC详解

JDBC文章目录JDBC什么是JDBC?JDBC驱动程序:Java使用JDBC访问数据库的步骤:设置classpath:Oracle连接字符串的书写格式:简单的例子:常用数据库的驱动程序及JDBC URL:Oracle数据库:SQL Server数据库MySQL数据库Access数据库PreparedStatement接口:JNDI-数据源（Data Source）与连接池（Connection

avatar CSDN学习社区

“模式识别与机器学习”学习笔记no2.再谈感知机

接**上篇：上篇主要进行了PLA，Pocket算法的理论过程分析和在给定数据集上利用pocket算法对数据集进行分类学习，得到错分数量最少的分类面。上篇中pocket算法的过程已经进行了编程和测试，框架已经建立了起来，这一篇主要上篇中没有提到或涉及不深的几个问题。1.数据集的构造。上篇是直接使用了题目给的向量，这次来根据正态分布来产生数据集。np.random.normal函数可以根据均值和方差生

avatar CSDN学习社区