排序算法研究之冒泡排序(bubble soft)

我准备用接下来的一段时间内系统的整理一下数据结构中常用的排序方法，这些方法在面试中出现的几率也很高，不要认为他们简单就不在意，往往面试官就喜欢通过基础问题来进行考察，打好基础真的非常非常重要！！！

所以一起来开始学习吧！欢迎讨论交流。

今天第一节我们先介绍，排序算法中最简单的冒泡排序。

1、算法思想

冒泡排序是最简单，较好理解的排序方法。
它通过每次比较数组中相邻的两个元素值，使数组中较小的值像气泡一样逐渐“上浮”到数组头部，较大的值逐渐下浮到数组尾部。（默认升序，降序为反过程）

2、优缺点

优点：简单，易于理解和实现，稳定，空间复杂度O(1)
缺点：因为要比较多轮，时间复杂度较高O(n²)，最坏情况要比较n-1轮（n是数组中元素个数）

3、关键点

（i） 两个for循环， 一个控制比较的轮数， 一个控制每轮比较的次数。注意：一轮比一轮比较的次数少
（ii）要注意排序的需求，是升序还是降序。

4、具体代码（c++）

例子：输入一个有10个元素的数组，并对其进行插入排序，最后数组为升序。

/**************************************************************************** @file Bubble_sort.cpp* @author Shawn* @date 29 Dec 2018* @remark 29 Dec 2018* @theme Bubble Sort***************************************************************************/
# include<iostream>
using namespace std;
void bubble(int[], int);int main()
{
    int array [] = {
    55,2,6,4,32,12,9,73,26,37};int len = sizeof(array) / sizeof(int);cout<<"输入的原始序列: ";for(int i=0; i<len; i++) // 输出原序列cout<<array[i]<<",";cout<<endl<<endl;cout<<" ----冒泡排序过程如下---- " << endl;bubble(array,len); // 调用排序函数return 0;
}void bubble(int a[], int size)
{
    // 冒泡排序具体的过程// 两个for循环，一个控制轮数，一个控制每轮比较的次数for(int pass=1; pass<size; pass++) // 比较的 size - 1 轮{
    for(int i=0; i<size-pass; i++) // 每轮比较的次数: size-passif(a[i+1]<a[i]){
    swap(a[i],a[i+1];}for(int j=0; j<size; j++)cout<<a[j]<<",";cout<<endl;}
}

下一讲： 插入排序