1、冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大

到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有

相邻元素需要交换，也就是说该元素已经排序完成

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序

排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”

冒泡排序算法的原理如下：

1）比较相邻的元素。如果第一个比第二个大，就交换他们两个

2）对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后

的元素应该会是最大的数

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

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

列如：

数组元素>

5 1 7 2 6 4 3 16

1）由于第一个元素5比第二个元素大1，交换它们的位置。

1 5 7 2 6 4 3 16

2）对比每个相邻的元素，此时到第二个元素5与第三个元素7，不交换位置

1 5 7 2 6 4 3 16

3）对比每个相邻的元素，此时到第三个元素7与第四个元素2，交换位置

1 5 2 7 6 4 3 16

4）对比每个相邻的元素，此时到第四个元素7与第五个元素6，交换位置

1 5 2 6 7 4 3 16

5）对比每个相邻的元素，此时到第五个元素7与第六个元素4，交换位置

1 5 2 6 4 7 3 16

6）对比每个相邻的元素，此时到第六个元素7与第七个元素3，交换位置

1 5 2 6 4 3 7 16

6）对比每个相邻的元素，此时到第七个元素7与第八个元素16，不换位置

1 5 2 6 4 3 7 16

2、双冒泡排序

双向冒泡算法，极大的减少了循环排序的次数

1）传统冒泡气泡排序的双向进行，先让气泡排序由左向右进行，再来让气泡排序由右往

左进行，如此完成一次排序的动作

2）使用left与right两个旗标来记录左右两端已排序的元素位置

3）当往左递进left >=往右递进的 right时，则排序完成

例子如下所示：

排序前：45 19 77 81 13 28 18 19 77 11

往右排序：19 45 77 13 28 18 19 77 11 [81]

向左排序：[11] 19 45 77 13 28 18 19 77 [81]

往右排序：[11] 19 45 13 28 18 19 [77 77 81]

向左排序：[11 13] 19 45 18 28 19 [77 77 81]

往右排序：[11 13] 19 18 28 19 [45 77 77 81]

向左排序：[11 13 18] 19 19 28 [45 77 77 81]

往右排序：[11 13 18] 19 19 [28 45 77 77 81]

向左排序：[11 13 18 19 19] [28 45 77 77 81]

此时28>=19条件成立排序完成

3、快速排序

快速排序（Quicksort）是对冒泡排序的一种改进

快速排序的基本思想：首先选取一个记录作为枢(shu)轴，不失一般性，可选第一个记

录，依它的关键字为基准重排其余记录，将所有关键字比它大的记录都安置在它之后，而将所有关键字比它小的记录都安置在之前，由此完成一趟快速排序；之后，分别对由一趟排序分割成的两个子序列进行快速排序，在大数据情况下要使用快速排序

列如：

数组元素>

5 1 7 2 6 4 3 16

思路：

取第一个数，把小于它的数往左移动，把大于它的数右移动

1）最左侧大于5的为7，最右侧小于5的为3,7与3对调

以5为枢轴>

5 1 3 2 6 4 7 16

2）全部对调完成，此时左侧小于5，右边大于5

5 1 3 2 | 6 4 7 16

3）5移动到分割位置

1 3 2 5 6 4 7 16

4）如果把数组元素分为三部分的话 左侧<中间<右侧

1 3 2 | 5 | 6 4 7 16

此时只需对两侧再重复以上操作就可以了

5）重复以上操作

1 3 2 >

1 2 3

此时左侧

6 4 7 16 >

4 6 7 16

简单来说：定义基数，比它小的往左排，比它大的往右排

4、归并排序

归并排序（MERGESORT）

是建立在归并操作上的一种有效的排序算法,该算法是采用

分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到

完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并

成一个有序表，称为二路归并

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法

如 设有数列1 8 2 9 3 5 6 4 10

1）第一次归并后：{1 8},{2 9},{ 3 5},{ 4 6}，{10}此时两两元素排序完的归并

2）第二次归并后：{1 2 8 9}，{ 3 4 5 6} ，{10}此时两两元素归并

1与2 寻找最小数 1

8与2 寻找最小数 2

8与9寻找最小数 8

{1 2 8 9}

3）第三次归并后：{1 2 3 4 5 6 8 9} , {10}此时两两元素归并

1与3寻找到最小数1 {1}

2与3寻找最小数2 {1 2}

8与3寻找最小数3 {1 2 3}

8与4寻找最小数4 {1 2 3 4}

8与5寻找最小数5 {1 2 3 4 5}

8与6寻找最小数6 {1 2 3 4 5 6}

8 9 落下{1 2 3 4 5 6 8 9}

4）第四次归并后：{1 2 3 4 5 6 8 9 10}

思路：循环找到最小值落下