冒泡排序法
1. 冒泡排序
基本思想：每一趟排序均从未排序元素开始，将未排序元素与其相邻元素进行比较，若不符合排序要求则进行交换后继续比较下一个元素与其相邻元素的大小，若符合排序要求则继续比较下一个元素与其相邻元素的大小。第一趟排序结束后，最小或最大元素来到数组的最后一个元素处，第二趟排序结束后，最小或最大元素来到数组的倒数第二个元素处，...如此反复循环直到所有元素均进行排序处理。
举例说明：未排序数组array[7]={5,3,12,9,1,6,8}，从前往后冒泡并以升序形式进行排序。
（1）第一趟排序：对未排序元素区间[0,6]进行排序，未排序区间的下边界为bound=6，定义一个索引cur指向未排序区间中的元素，cur初始指向未排序区间的开始处即cur=0。数组为array[7]={5,3,12,9,1,6,8}
开始第一趟的比较（比较条件为cur<bound=6）：
①cur=0，array[cur]=5，5比3大故进行交换，数组变为array[7]={3,5,12,9,1,6,8}；
②cur++即cur=1，array[cur]=5，5没12大故不进行交换，数组仍为array[7]={3,5,12,9,1,6,8}；
③cur++即cur=2，array[cur]=12，12比9大故进行交换，数组变为array[7]={3,5,9,12,1,6,8}；
④cur++即cur=3，array[cur]=12，12比1大故进行交换，数组变为array[7]={3,5,9,1,12,6,8}；
⑤cur++即cur=4，array[cur]=12，12比6大故进行交换，数组变为array[7]={3,5,9,1,6,12,8}；
⑥cur++即cur=5，array[cur]=12，12比8大故进行交换，数组变为array[7]={3,5,9,1,6,8,12}；
⑦cur++即cur=6，此时cur!<bound，故第一趟比较结束，此时未排序区间最大值12来到了数组的下边界bound处。
（2）第二趟排序：对未排序元素区间[0,5]进行排序，未排序区间的下边界为bound=5，定义一个索引cur指向未排序区间中的元素，cur初始指向未排序区间的开始处即cur=0。数组为array[7]={3,5,9,1,6,8,12}
开始第二趟的比较（比较条件为cur<bound=5）：
①cur=0，array[cur]=3，3没5大故不进行交换，数组仍为array[7]={3,5,9,1,6,8,12}；
②cur++即cur=1，array[cur]=5，5没12大故不进行交换，数组仍为array[7]={3,5,9,1,6,8,12}；
③cur++即cur=2，array[cur]=9，9比1大故进行交换，数组变为array[7]={3,5,1,9,6,8,12}；
④cur++即cur=3，array[cur]=9，9比6大故进行交换，数组变为array[7]={3,5,1,6,9,8,12}；
⑤cur++即cur=4，array[cur]=9，9比8大故进行交换，数组变为array[7]={3,5,1,6,8,9,12}；
⑥cur++即cur=5，此时cur!<bound，故第二趟比较结束，此时未排序区间中最大值9来到了数组的下边界bound处。
（3）第三趟排序：对未排序元素区间[0,4]进行排序，未排序区间的下边界为bound=4，定义一个索引cur指向未排序区间中的元素，cur初始指向未排序区间的开始处即cur=0。数组为array[7]={3,5,1,6,8,9,12}
开始第三趟的比较（比较条件为cur<bound=4）：
①cur=0，array[cur]=3，3没5大故不进行交换，数组仍为array[7]={3,5,1,6,8,9,12}；
②cur++即cur=1，array[cur]=5，5比1大故进行交换，数组变为array[7]={3,1,5,6,8,9,12}；
③cur++即cur=2，array[cur]=5，5没6大故不进行交换，数组仍为array[7]={3,1,5,6,8,9,12}；
④cur++即cur=3，array[cur]=6，6没8大故不进行交换，数组仍为array[7]={3,1,5,6,8,9,12}；
⑤cur++即cur=4，此时cur!<bound，故第三趟比较结束，此时未排序区间最大值8来到了数组的下边界bound处。
（4）第四趟排序：对未排序元素区间[0,3]进行排序，未排序区间的下边界为bound=3，定义一个索引cur指向未排序区间中的元素，cur初始指向未排序区间的开始处即cur=0。数组为array[7]={3,1,5,6,8,9,12}
开始第四趟的比较（比较条件为cur<bound=3）：
①cur=0，array[cur]=3，3比1大故进行交换，数组变为array[7]={1,3,5,6,8,9,12}；
②cur++即cur=1，array[cur]=3，3没5大故不进行交换，数组仍为array[7]={1,3,5,6,8,9,12}；
③cur++即cur=2，array[cur]=5，5没6大故不进行交换，数组仍为array[7]={1,3,5,6,8,9,12}；
④cur++即cur=3，此时cur!<bound，故第四趟比较结束，此时未排序区间最大值6来到了数组的下边界bound处。
（5）第五趟排序：对未排序元素区间[0,2]进行排序，未排序区间的下边界为bound=2，定义一个索引cur指向未排序区间中的元素，cur初始指向未排序区间的开始处即cur=0。数组为array[7]={1,3,5,6,8,9,12}
开始第五趟的比较（比较条件为cur<bound=2）：
①cur=0，array[cur]=1，1没3大故不进行交换，数组仍为array[7]={1,3,5,6,8,9,12}；
②cur++即cur=1，array[cur]=3，3没5大故不进行交换，数组仍为array[7]={1,3,5,6,8,9,12}；
③cur++即cur=2，此时cur!<bound，故第五趟比较结束，此时未排序区间最大值5来到了数组的下边界bound处。
（6）第六趟排序：对未排序元素区间[0,1]进行排序，未排序区间的下边界为bound=1，定义一个索引cur指向未排序区间中的元素，cur初始指向未排序区间的开始处即cur=0。数组为array[7]={1,3,5,6,8,9,12}
开始第刘趟的比较（比较条件为cur<bound=1）：
①cur=0，array[cur]=1，1没3大故不进行交换，数组仍为array[7]={1,3,5,6,8,9,12}；
②cur++即cur=1，此时cur!<bound，故第六趟比较结束，此时未排序区间最大值3来到了数组的下边界bound处。
此时，未排序区间元素只剩下一个，即表示整个数组已经有序。
总结：对于数组元素个数为7的乱序数组，需要7-1趟排序，第i趟又需要7-i次比较（i=1,2,...6）。总结概括为：对于元素个数为n的数组，共需要进行n-1趟排序，第i趟排序又需要n-i次比较（i=1,2,...6）。
从前往后冒泡并以升序的方式排序，代码实现如下：//0.交换两个数的值
void Swap(int* x,int* y)
{
int tmp=*x;
*x=*y;
*y=tmp;
}
//1.冒泡排序(从前往后冒泡)
void BubbleSortEx(int array[],size_t size){
//当size<=1时不需要排序
if(size<=1)
return;
//定义一个bound边界，[0,bound)表示无序，[bound,size)表示有序
size_t bound=size-1;
//排序需要的趟数
for(;bound>0;bound--)
{
size_t cur=0;
//每趟需要的比较次数
for(;cur<bound;cur++)
{
if(array[cur]>array[cur+1])
{
Swap(&array[cur],&array[cur+1]);
}
}
}
}其实也可以从后往前冒泡，思路有从前往后冒泡类似，大家可以自行梳理思路。代码实现如下：
//0.交换两个数的值
void Swap(int* x,int* y)
{
int tmp=*x;
*x=*y;
*y=tmp;
}
//1.冒泡排序(从后往前冒泡)
void BubbleSort(int array[],size_t size)
{
//当size<=1时，则不需要排序直接返回
if(size<=1)
return;
//定义一个bound边界，[0,bound)表示有序，[bound,size)表示无序
size_t bound=0;
for(;bound<size;bound++)
{
//从后向前冒泡（也可以从前向后冒泡）
size_t cur=size-1;
for(;cur>bound;cur--)
{
//以升序的方式排序
if(array[cur]<array[cur-1])
{
Swap(&array[cur],&array[cur-1]);
}
}
}
}相关阅读
概述排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部的排序记
一、堆排序算法原理和动态图解 将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走(其实就是将
原理：每次比较两个相邻的元素，将较大的元素交换至右端。 思路：每次冒泡排序操作都会将相邻的两个元素进行比较，看是否满足大小关系要
前言这些一个系列的文章，主要是自己学习算法和数据结构的一些笔记整理。从最简单开始，一步步深入，都是自己学习过程中的领悟。对于程
1、冒泡排序 最简单的一种排序算法。假设长度为n的数组arr，要按照从小到大排序。则冒泡排序的具体过程可以描述为：首先从数组的第一