小白CV‘’

序言

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

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

一种是比较排序，时间复杂度O(nlogn) ~ O(n^2)，主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等；

另一种是非比较排序，时间复杂度可以达到O(n)，主要有：计数排序，基数排序，桶排序等。

一：冒泡排序（BubbleSort）

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

图. 鱼吐泡泡

冒泡排序算法的步骤：

从小到大进行排序：

1 比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置；

2 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数；

3 针对所有的元素重复以上的步骤，除了最后一个；

4 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

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

#include

// 分类 -------------- 内部比较排序

// 数据结构 ---------- 数组

// 最差时间复杂度 ---- 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平方）：

冒泡排序的改进：鸡尾酒排序（CocktailSort）

鸡尾酒排序，也叫定向冒泡排序，是冒泡排序的一种改进。此算法与冒泡排序的不同处在于从低到高,然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能。

还完成上面一个排序，采用鸡尾酒排序实现对序列{ 6, 5, 3, 1, 8, 7, 2, 4 }排序的实现过程如下：

#include

// 分类 -------------- 内部比较排序

// 数据结构 ---------- 数组

// 最差时间复杂度 ---- 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了。

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

https://baike.sogou.com/v111984.htm?fromTitle=%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F