牛客网题型总结（2）（排序算法1）（冒泡排序与快速排序）

*欢迎来到博主的专栏算法解析

博主id:reverie_ly.*

排序算法能够用来帮助我们完成一些排序的题，甚至有些题目就是让我们编写出实现某个排序算法的程序

冒泡排序

冒牌排序的原理就是让每个相邻的元素比较大小，如果不满足次序，就要将两者的顺序调换过来。直到所有元素都满足升序或逆序的顺序就停止。

原理

假设有十个元素需要排序，我们将这十个元素分为a1，a2……a10.，以升序的方式排列。

a1~a10之间一定会有一个数是最大值，无论这个数在什么位置，他一定比两边的元素要大。所以在升序的过程中，这个最大值一定会一直和右边的的数交换，直到最大值到最后一位

可以发现，无论max在什么位置，在一轮排序过后都会到最后面（满足升序）

第二轮排序时，可以忽略最右边的位置开始排序（因为最右边是max，不会有其他数比它更大），在余下的数中还会有一个值是除了max以外最大的值，我们将其称为max-mini

在这轮排序中，无论max-mini在什么位置，也会被排序到max的左边（符合升序）。

以此类推，每一轮排序过后都会有一个值被确定在一位位置上。所以我们可以发现冒泡排序算法的排序原理

1）将元素与右边的元素对比大小，符合排序要求就保留，不符合排序要求就交换

2）将当前所有元素依次和右边元素进行对比，完成一次对比称为完成一轮冒泡排序。

3）每一轮冒泡排序结束后，就会有一个当前的最大值（或最小值）被送到最右边，下次排序时将这个元素忽略。

代码

用c语言实现冒泡排序的代码如下：

如果有程序需要用到冒泡排序算法的，只需要使用函数定义的那部分就能实现（注意修改宏常量）

快速排序

快速排序是将某个元素取出作为“标准元素”然后使

标准元素左边的所有元素小于等于标准元素，右边的所有元素大于等于标准元素。

再使用递归使得所有的元素左边都是小于等于本身，右边的元素大于等于本身。（如果想要用快速排序实现逆序排序反之），

原理

快速排序的原理如下：

将待分割的数据组的最低为称为low位，最高为为high位。

1）找到“标准元素i”，使得i左边的所有元素都小于i，i右边的所有元素都大于i。

2）将数据分割成 low~i 和 i-high 。

3）接着在 low到i 中找到“标准元素”

4）在 i到high 中找到“标准元素

5）再以"标准元素”的分割线，继续分割下去。

如此循环下去，就能使所有元素都被排序

首先是找到“标准元素”方法。

我们取出low位的元素为标准元素（high位也行，事实上任意位都行）。

并从high位开始往左找比12小的数字。将这个比标准元素小的元素放进空位中。

然后从low位开始找比12大的数放进空位（这个过程的往复的，从low找完就要从high位找）

从high位往左找比12小的数，并放进空位

接着从low位往右找比12大的数。当low位于high位相等时，将12放进这个重叠的位置。

这样就使得12符合“标准元素”的要求。然后将标准元素作为分割线。再找出两边的的“标准元素”，周而复始，排序就完成了

代码

快速排序算法的程序实现方法不唯一。只要按照分割的方式实现即可。（即寻找“标准元素”的方法）