牛客网题型总结（2）（排序算法1）（冒泡排序与快速排序）
原创
*欢迎来到博主的专栏算法解析
博主id:reverie_ly.*
排序算法能够用来帮助我们完成一些排序的题，甚至有些题目就是让我们编写出实现某个排序算法的程序
冒泡排序
冒牌排序的原理就是让每个相邻的元素比较大小，如果不满足次序，就要将两者的顺序调换过来。直到所有元素都满足升序或逆序的顺序就停止。
原理
假设有十个元素需要排序，我们将这十个元素分为a1，a2……a10.，以升序的方式排列。
a1~a10之间一定会有一个数是最大值，无论这个数在什么位置，他一定比两边的元素要大。所以在升序的过程中，这个最大值一定会一直和右边的的数交换，直到最大值到最后一位
可以发现，无论max在什么位置，在一轮排序过后都会到最后面（满足升序）
第二轮排序时，可以忽略最右边的位置开始排序（因为最右边是max，不会有其他数比它更大），在余下的数中还会有一个值是除了max以外最大的值，我们将其称为max-mini
在这轮排序中，无论max-mini在什么位置，也会被排序到max的左边（符合升序）。
以此类推，每一轮排序过后都会有一个值被确定在一位位置上。所以我们可以发现冒泡排序算法的排序原理
1）将元素与右边的元素对比大小，符合排序要求就保留，不符合排序要求就交换
2）将当前所有元素依次和右边元素进行对比，完成一次对比称为完成一轮冒泡排序。
3）每一轮冒泡排序结束后，就会有一个当前的最大值（或最小值）被送到最右边，下次排序时将这个元素忽略。
代码
用c语言实现冒泡排序的代码如下：
#include<stdio.h>
#include<stdbool.h>
#define N 10
void bubble_sort(int* arr, int sz)
{
int i, j;
bool flag ;
for (i = 0; i < N; i++) //冒泡排序的轮数
{
flag = true;//判断当前元素是否升序
for (j = 0; j < N - 1 - i; j++) //完成一轮排序
{
if (arr[j] > arr[j + 1]) {
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;//发生交换就说明当前不符合升序
}
}
if (flag == true)//升序完成结束
return;
}
}
int main()
{
int arr[N],i,sz;
for(i=0;i<N;i++)
scanf("%d", &arr[i]);
bubble_sort(arr, N);
for (i = 0; i < N; i++) {//直观的展示结果
printf("%d ", arr[i]);
}
return 0;
}如果有程序需要用到冒泡排序算法的，只需要使用函数定义的那部分就能实现（注意修改宏常量）
快速排序
快速排序是将某个元素取出作为“标准元素”然后使
标准元素左边的所有元素小于等于标准元素，右边的所有元素大于等于标准元素。
再使用递归使得所有的元素左边都是小于等于本身，右边的元素大于等于本身。（如果想要用快速排序实现逆序排序反之），
原理
快速排序的原理如下：
将待分割的数据组的最低为称为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符合“标准元素”的要求。然后将标准元素作为分割线。再找出两边的的“标准元素”，周而复始，排序就完成了
代码
#include<stdio.h>
#define N 10
void quick_sort(int arr[], int low,int high);
int split(int arr[], int low, int high);
int main()
{
int arr[N];
for(int i=0;i<N;i++)
scanf("%d", &arr[i]);
quick_sort(arr, 0,N-1);
for (int i = 0; i < N; i++)
printf("%d ", arr[i]);
return 0;
}
void quick_sort(int arr[], int low,int high)//递归函数
{
if (low >= high) return;
int middle = split(arr,low,high);
quick_sort(arr, middle + 1, high);
quick_sort(arr, low, middle - 1);
return;
}
int split(int arr[], int low, int high)//用标准元素分割数组
{
int std_element = arr[low];
for (;;)
{
while (low < high && arr[high]>std_element)
high--;
if (low >= high) break;
arr[low++] = arr[high];
while (low < high && arr[low] < std_element)
low++;
if (low >= high)break;
arr[high--] = arr[low];
}
arr[high] = std_element;
return high;
}快速排序算法的程序实现方法不唯一。只要按照分割的方式实现即可。（即寻找“标准元素”的方法）
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
腾讯云开发者
