数据结构笔记(十二)排序算法之冒泡排序与鸡尾酒排序

发布于 / 程序猿 / 0 条评论

冒泡排序(英语:Bubble Sort,台湾另外一种译名为:泡沫排序)是一种简单的排序算法。本文介绍冒泡排序以及冒泡排序改进版本鸡尾酒排序

冒泡排序

基本知识

冒泡排序会重复地遍历要排序的数列,每次遍历时,它都会从前往后依次的比较相邻两个元素的大小,如果前者比后者大,则交换它们的位置。这样,一次遍历之后,最大的元素就在数列的末尾。采用相同的方法再次遍历时,第二大的元素就被排列在最大元素之前。重复此操作,直到整个数列都有序为止。

这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

图文演示

对序列16, 11, 2 ,14, 10, 6, 3, 12, 18, 9进行冒泡排序。

  • 第一次遍历比较相邻两个元素,得到序列最大值18

  • 第二次遍历比较相邻两个元素,得到序列第二大值16

  • 第三次遍历比较相邻两个元素,得到序列第三大值14

  • 第四次遍历比较相邻两个元素,得到序列第四大值12

  • 第五次遍历比较相邻两个元素,得到序列第五大值11

  • 继续遍历比较相邻两个元素,分别得到序列剩余的最大值。

  • 整个序列有序,2, 3, 6, 9, 10, 11, 12, 14, 16, 18

  • 维基百科图示

算法实现

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
const int maxn = 10000;
const int Max = 10000;
int a[maxn];

void display(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << a[i] << " ";
        if ((i+1) % 10 == 0)
            cout << endl;
    }
}

inline void Swap(int &a, int &b) // 交换
{
    int t = a;
    a = b;
    b = t;
}

void bubble_sort(int a[], int n) // 冒泡排序
{ 
    for (int i = 0; i < n - 1; ++i)
    {
        // 依次得到a[i...n-1]中最小的元素
        for (int j = 0; j < n - 1 - i; ++j)
        {
            if (a[j + 1] < a[j]) // 交换
                Swap(a[j + 1], a[j]);
        }
    }
}

void getTime(void f(int [], int), int a[], int n)
{
    clock_t _start, _end;
    _start = clock();
    f(a, n);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
}

int main()
{
    //srand((unsigned)time(NULL)); 
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % Max;
    //display(a, maxn);
    bubble_sort(a, maxn);
    getTime(bubble_sort, a, maxn);
    //display(a, maxn);
    return 0;
}
  • 数组4 13 18 14 10 6 0 10 5 15的排序过程,每次将数值最小的元素放到数组前面。
4 13 18 14 10 6 0 10 5 15 // 原始序列
4 13 14 10 6 0 10 5 15 18
4 13 10 6 0 10 5 14 15 18
4 10 6 0 10 5 13 14 15 18
4 6 0 10 5 10 13 14 15 18
4 0 6 5 10 10 13 14 15 18
0 4 5 6 10 10 13 14 15 18
0 4 5 6 10 10 13 14 15 18 // 有序序列
  • 实测不同规模序列程序运行时间。
大小在10000以内的数
maxn = 100   时, 0s
maxn = 1000  时, 0.001s
maxn = 10000 时, 0.111s
maxn = 10000 时, 11.564s

算法优化

对冒泡排序进行优化,提高效率。设置一个标记flag,如果一趟遍历中发生了交换,则标记flag为true,否则为false。如果有一趟没有发生交换,说明排序已经完成

void _bubble_sort(int a[], int n) // 冒泡排序优化
{
    bool flag;
    for (int i = 0; i < n - 1; ++i)
    {
        flag = false; // 初始化标记为false
        // 依次得到a[i...n-1]中最小的元素
        for (int j = 0; j < n - 1 - i; ++j)
        {
            if (a[j + 1] < a[j]) // 交换
            {
                Swap(a[j + 1], a[j]);
                flag = true; // 发生交换标记为true
            }
        }
        if (!flag) // 如果没发生交换则数列有序,结束循环
            break;
    }
}

算法分析

  • 时间复杂度

冒泡排序的时间复杂度是O(N²)。假设被排序的数列中有N个数,遍历一次的时间复杂度是O(N),总共需要遍历N-1次,因此,冒泡排序的时间复杂度是O(N²)

  • 稳定性

冒泡排序是就地排序,且它是稳定的

注意

冒泡排序是与插入排序拥有相同的时间复杂度,但是两种算法在需要的交换次数却很大地不同。在最坏的情况,冒泡排序需要O(N²)次交换,而插入排序只要最多O(N)交换。

冒泡排序如果能在内部循环第一次运行时,使用一个标记来表示有无需要交换的可能,也可以把最优情况下的复杂度降低到O(N)【算法优化版本】,在这个情况,已经排序好的数列就无交换的需要。若在每次遍历数列时,把遍历顺序反过来,也可以稍微地改进效率。有时候称为鸡尾酒排序【下文】,因为算法会从数列的一端到另一端之间穿梭往返。

冒泡排序是最容易理解和实现的排序算法之一,但是它对于包含大量的元素的数列排序效率极其低下,不推荐使用


鸡尾酒排序

基本知识

鸡尾酒排序,也就是定向冒泡排序鸡尾酒搅拌排序搅拌排序(也可以视作选择排序的一种变形),涟漪排序,或来回排序,是冒泡排序的一种变形。此算法与冒泡排序的不同处在于排序时是以双向在序列中进行排序。

算法描述

  • 先对数组从左到右进行升序的冒泡排序;
  • 再对数组进行从右到左的降序的冒泡排序;
  • 以此类推,持续的、依次的改变冒泡的方向,并不断缩小没有排序的数组范围;

图示

算法实现

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <algorithm>
using namespace std;
const int maxn = 10000;
const int Max = 10000;
int a[maxn];

void display(int a[], int n)
{
    for (int i = 0; i < n; ++i)
    {
        cout << a[i] << " ";
        if ((i+1) % 10 == 0)
            cout << endl;
    }
}

inline void Swap(int &a, int &b) // 交换
{
    int t = a;
    a = b;
    b = t;
}

void cocktail_sort(int a[], int n)
{
    int left = 0, right = n - 1;
    while (left < right)
    {
        for (int i = left; i < right; ++i) // 第一次交换
            if (a[i] > a[i+1])
                Swap(a[i], a[i+1
        right--;
        for (int i = right; i > left; --i) // 第二次交换
            if (a[i-1] > a[i])
                Swap(a[i], a[i-1]);
        left++;
    }
}


void getTime(void f(int [], int), int a[], int n)
{
    clock_t _start, _end;
    _start = clock();
    f(a, n);
    _end = clock();
    cout << (double)(_end - _start) / CLOCKS_PER_SEC << endl;
}

int main()
{
    // srand((unsigned)time(NULL)); 
    for (int i = 0; i < maxn; ++i)
        a[i] = rand() % Max;
    // display(a, maxn);
    cocktail_sort(a, maxn);
    getTime(cocktail_sort, a, maxn);
    display(a, maxn);
    return 0;
}
  • 数组16 11 2 14 10 6 3 12 18 16的排序过程,每次将数值最小的元素放到数组前面, 数值大的元素放到数组后面。
// 第一次
11 2 14 10 6 3 12 16 16 18 // 18
2 11 3 14 10 6 12 16 16 18 // 2
// 第二次
2 3 11 10 6 12 14 16 16 18 // 16
2 3 6 11 10 12 14 16 16 18 // 3
// 第三次
2 3 6 10 11 12 14 16 16 18 // 16
2 3 6 10 11 12 14 16 16 18 // 6
// 第四次
2 3 6 10 11 12 14 16 16 18 // 14 
2 3 6 10 11 12 14 16 16 18 // 10
// 第五次
2 3 6 10 11 12 14 16 16 18 // 11
2 3 6 10 11 12 14 16 16 18 // 12

算法分析

鸡尾酒排序的时间复杂度是O(N²)

鸡尾酒排序等于是冒泡排序的轻微变形。不同的地方在于先从低到高然后从高到低,而冒泡排序则仅从低到高去比较序列里的每个元素。它可以得到比冒泡排序稍微好一点的效能,原因是冒泡排序只从一个方向进行比对(由低到高),每次循环只移动一个项目。

以序列(2,3,4,5,1)为例,鸡尾酒排序只需要访问一次序列就可以完成排序,但如果使用冒泡排序则需要四次。但是在乱数序列的状态下,鸡尾酒排序与冒泡排序的效率都很差劲。


说明

文中基础知识和理论分析部分来源于维基百科,推荐阅读冒泡排序白话经典算法系列之一 冒泡排序的三种实现

The end.
2017-12-20 星期三

转载原创文章请注明,转载自: 太傅 » 数据结构笔记(十二)排序算法之冒泡排序与鸡尾酒排序
Not Comment Found