排序算法

微信公众号：小白算法
关注可了解更多算法，并能领取免费资料。问题或建议，请公众号留言;
小白算法，简单白话算法，每个人都能看懂的算法

序言

排序，顾名思义就是排列使得有序呗！！！通常意义上，我们所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

排序算法大体可分为两种：

• 一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等；
• 另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

排序算法对比一览表

一：冒泡排序（BubbleSort）

何为冒泡？看下下面这条鱼吐泡泡的样子，泡泡会从底端逐渐的浮上水面，由于水压的原因，会逐渐的变大，然后炸裂，这个算法的名字就是这么形象的理解的。冒泡排序名字的由来是因为越小(或越大)的元素会经由交换慢慢“浮”到数列的顶端。

鱼吐泡泡

冒泡排序算法的步骤：

从小到大进行排序：
1 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置；
2 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；
3 针对所有的元素重复以上的步骤，除了最后一个；
4 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

举例，采用冒泡排序实现对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }排序的实现过程如下：

#include <stdio.h>

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果能在内部循环第一次运行时,使用一个旗标来表示有无需要交换的可能,可以把最优时间复杂度降低到O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

void BubbleSort(int A[], int n)
{
    for (int j = 0; j < n - 1; j++)         // 每次最大元素就像气泡一样"浮"到数组的最后
    {
        for (int i = 0; i < n - 1 - j; i++) // 依次比较相邻的两个元素,使较大的那个向后移
        {
            if (A[i] > A[i + 1])            // 如果条件改成A[i] >= A[i + 1],则变为不稳定的排序算法
            {
                Swap(A, i, i + 1);
            }
        }
    }
}

int main()
{
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };    // 从小到大冒泡排序
    int n = sizeof(A) / sizeof(int);
    BubbleSort(A, n);
    printf("冒泡排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

上述代码的动画实现过程如下：

冒泡排序算法动态示意图
优点：冒泡排序是最容易了解和实现的排序算法之一。

缺点：对于少数元素之外的数列排序是效率低。

最后说一下冒泡排序的时间复杂度问题：

• 最佳排序：若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数C和记录移动次数M均达到最小值：Cmin=n-1,Mmin=0。初始排序就是最终需要的序列，其是冒泡排序的最好情况，时间复杂度为0(n)。
• 最差排序：最佳排序的文件的初始状态是正序的，那若初始文件是反序的，需要进行n-1趟排序，每趟排序要进行n-i(1<=i=<n-1)次的比较，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值O（n平方）： Cmax
  Mmax

参考资料：http://www.cnblogs.com/eniac12/p/5329396.html

冒泡排序的改进：鸡尾酒排序

鸡尾酒排序，也叫定向冒泡排序，是冒泡排序的一种改进。此算法与冒泡排序的不同处在于从低到高,然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能。(PS:何为鸡尾酒排序，鸡尾酒都知道是将各种酒混合在一起，伏特加倒入威士忌酒杯里，先下降，再上升)

#include <stdio.h>

// 分类 -------------- 内部比较排序
// 数据结构 ---------- 数组
// 最差时间复杂度 ---- O(n^2)
// 最优时间复杂度 ---- 如果序列在一开始已经大部分排序过的话,会接近O(n)
// 平均时间复杂度 ---- O(n^2)
// 所需辅助空间 ------ O(1)
// 稳定性 ------------ 稳定

void Swap(int A[], int i, int j)
{
    int temp = A[i];
    A[i] = A[j];
    A[j] = temp;
}

void CocktailSort(int A[], int n)
{
    int left = 0;           // 初始化左起点
    int right = n - 1;      // 初始化右起点
    while (left < right)
    {
        //从左往右开始
        for (int i = left; i < right; i++)   // 前半轮,将最大元素放到后面
        {
            if (A[i] > A[i + 1])
            {
                Swap(A, i, i + 1);
            }
        }
        right--;
        //从右往左开始
        for (int i = right; i > left; i--)   // 后半轮,将最小元素放到前面
        {
            if (A[i - 1] > A[i])
            {
                Swap(A, i - 1, i);
            }
        }
        left++;
    }
}

int main()
{
    int A[] = { 6, 5, 3, 1, 8, 7, 2, 4 };   // 从小到大定向冒泡排序
    int n = sizeof(A) / sizeof(int);
    CocktailSort(A, n);
    printf("鸡尾酒排序结果：");
    for (int i = 0; i < n; i++)
    {
        printf("%d ", A[i]);
    }
    printf("\n");
    return 0;
}

思考

为什么鸡尾酒排序比冒泡排序稍微好一点呢？

举个栗子
以序列(2,3,4,5,1)为例，采用升序排列。冒泡排序需要从左到右依次将2,3,4,5往后移动，将1往前移动；但是，鸡尾酒排序从左到右一趟，没一个变化的，然后从右向左，把1直接移动到第一位，就ok了。

下期预告：小白带你学---排序算法1的冒泡排序的内容理解到了吗？下期继续更新选择排序
该系列持续更新中，想get更多有趣的算法知识，或者提出宝贵意见，请关注微信公众号“小白算法”并联系我们，回复219，还可以免费获取著名机器学习教材《机器学习-周志华》一书，谢谢！！！