乾坤大挪移——冒泡法排序，良心之作，拒绝入坑

冒泡 冒泡，不管学什么语言，冒泡排序是必经的。
在学C语言时每次都要花好久来想，然后写程序，而且下次再写还是花好久才行，花了一个多小时，写了这个博客，希望入门的小白不要入坑了，好好看看，真的挺简单的。
内有C语言 c++ python Java的源码，希望对大家有所帮助。

冒泡就像是水里的气泡，大的气泡就飘起来，小的就沉下去（在编程里当然也可以反过来）。好下面来看看他是怎么操作的。
现在从小到大排序为例
原理： 比较两个相邻的元素，较大的数慢慢往后排，较小的数慢慢往前排。每一趟遍历，将一个最大的数移到序列末尾。

想一下，有n个数要遍历几遍？两个数遍历一遍，三个数遍历两遍，n个数就是n-1遍。
以这个为例，有小到大排序：

现在有六个数，所以用 5 次大循环进行两两比较
循环一

• 2 5不用交换，往下走
• 5 8不交换，继续
• 8 1交换，顺序为 2 5 1 8 6 4 继续
• 8 6交换 顺序为 2 5 1 6 8 4 继续
• 8 4交换 顺序为 2 5 1 6 4 8 第一轮完成，找到了最大的那个并把他放到了最后

现在最后一个数已经确定了，是最大的，所以下一轮循环就不用比较到他了。

循环二

• 2 5不用交换，往下走
• 5 1交换， 2 1 5 6 4 8 继续
• 5 6不交换，继续
• 6 4交换 顺序为 2 1 5 4 6 8 ok现在找到了第二大的，并把他放到了倒数第二个位置，下次循环就不用比较已经找出来的6和8了
  循环三
• 2 1交换 1 2 5 4 6 8继续
• 2 5不换 继续
• 5 4 交换1 2 4 5 6 8找到了第三大的5，并把他放到了倒数第三个位置

可以看出现在已经排序完成，但计算机并不知道，他还在继续他的循环。

循环四

• 1 2不换 继续
• 2 4不换 顺序没变

循环五

• 1 2不换 顺序不变

可以看下下面的动态图，让思路更清晰

1. 有n数排序，就要循环n-1次，这称之为大循环
2. 每经历一次大循环都要对数组里面的数进行比较交换，所以每次大循环后还有一次小循环。
3. 每次小循环都比上一次小循环少遍历（或者说是比较）一个数，因为每次大循环都会找到一个最大的，并把他放到后面。

下面来进行编程实现

// C语言版
#include
void swap(int *a,int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main(){
	int arr[6]={2,5,8,1,6 ,4};
	int i, j, temp,len=6;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
            	swap(&arr[j], &arr[j + 1]);
            }
    for (i = 0; i < len; i++){
    	printf("%d ",arr[i]);
	}
}

#include
int main(){
	int arr[6]={2,5,8,1,6 ,4};
	int i, j, temp,len=6,d;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1]) {
            	d=arr[j];
            	arr[j]=arr[j+1];
            	arr[j+1]=d;
            }
    for (i = 0; i < len; i++){
    	printf("%d ",arr[i]);
	}
}

• C语言是从0开始计数的，所以第一个数是a[0]，也就是2，最后一个是a[5]，也就是4，循环n-1遍，for (i = 0; i < 5; i++)——>>（0 1 2 3 4）循环五遍
• 每次小循环都是从第一个数开始的，所以要for (j = 0; j < len - 1 - i; j++)，为什么是len-1-i呢？因为循环了前面 i 次后，就找出来了i个大的数，并按顺序放到了最后，所以这次小循环就不用与他比较了。

#python
def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

//C++
template<typename T>
void bubble_sort(T arr[], int len) {
    int i, j;
    for (i = 0; i < len - 1; i++)
        for (j = 0; j < len - 1 - i; j++)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}

//Java
 * 冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。
 * 如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置，重复n 次，
 * 就完成了 n 个数据的排序工作。
 **/
public class BubbleSort {
    public void bubbleSort(Integer[] arr, int n) {
        if (n <= 1) return;       //如果只有一个元素就不用排序了
 
        for (int i = 0; i < n; ++i) {
            // 提前退出冒泡循环的标志位,即一次比较中没有交换任何元素，这个数组就已经是有序的了
            boolean flag = false;
            for (int j = 0; j < n - i - 1; ++j) {        //此处你可能会疑问的j
                // 数组下标又是从0开始的，i下标后面已经排序的个数就得多减1，总结就是i增多少，j的循环位置减多少
                if (arr[j] > arr[j + 1]) {        //即这两个相邻的数是逆序的，交换
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) break;//没有数据交换，数组已经有序，退出排序
        }
    }
 
    public static void main(String[] args) {
        Integer arr[] = {2, 4, 7, 6, 8, 5, 9};
        SortUtil.show(arr);
        BubbleSort bubbleSort = new BubbleSort();
        bubbleSort.bubbleSort(arr, arr.length);
        SortUtil.show(arr);
    }