C语言冒泡排序

LNB0X

冒泡排序

定义

冒泡排序（Bubble Sort）是最简单和最通用的排序方法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序 。由此可得，在排序过程中，大的数据往下沉，小的数据往上浮，就像气泡一样，于是将这种排序算法形象地称为冒泡排序。

大致过程

如数组5 4 3 2 1
第一轮
(5 4 3 2 1)
4 5 3 2 1
4 3 5 2 1
4 3 2 5 1
4 3 2 1 5
第二轮
(4 3 2 1 5)
3 4 2 1
3 2 4 1
3 2 1 4
第三轮
(3 2 1 4)
2 3 1
2 1 3
第四轮
(2 1 3)
12

小结

设总的元素个数为n，那么由上边的排序过程可以看出：  

（1）总计需要进行（n-1）轮排序，也就是（n-1）次大循环  

（2）每轮排序比较的次数逐轮减少  

（3）如果发现在某趟排序中，没有发生一次交换， 可以提前结束冒泡排序。（优化）  

实现

        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }