排序算法——冒泡排序

基本原理

1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个
2. 对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数
3. 针对所有的元素重复以上步骤，除了最后一个
4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

动态图演示

代码实现

package com.company;
import java.util.Arrays;
public class Main {

    public static void main(String[] args) {
        int[] data = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
        bubbleSort(data);
        System.out.println("冒泡排序结果：" + Arrays.toString(data));
    }
  
    public static void bubbleSort(int[] data) {
        // 控制排序次数
        for(int i = 0; i < data.length - 1; i++) {
            // 此处为算法优化点，可以去掉； 设置一个标记，若为true，则表示此次循环没有需要进行交换的，也就是说待排序序列已经是有序的了
            boolean sortFlag = true;
            // 开始从第0个元素排序，相邻两个元素排序
            for(int j = 0; j < data.length - 1 - i; j++) {
                if(data[j] > data[j + 1]) {
                    sortFlag = false;
                    // 交换元素
                    // 第一种交换写法，通过加减运算
                    data[j] = data[j] + data[j + 1];
                    data[j + 1] = data[j] - data[j + 1];
                    data[j] = data[j] - data[j + 1];
                    // 第二种交换写法，通过异或(^)运算
//                    data[j] = (data[j] ^ data[j + 1]);
//                    data[j + 1] = data[j + 1] ^ data[j];
//                    data[j] =  data[j + 1] ^ data[j];
                    // 第三种交换写法，通过借助临时变量完成
//                    int temp = data[j];
//                    data[j] = data[j + 1];
//                    data[j + 1] = temp;

                }
            }
            if(sortFlag) {
              break;
            }
        }
    }
}

在交换元素的时候有三种方式：

• 通过元素间的加减运算交换——-代码中第一种写法
• 通过元素间的异或(^)运算交换——–代码中第二种写法
• 通过借助临时变量交换——–代码中第三种写法

其中前两种写法在运行效率上高于第三种，因为在运行过程中减少了内存分配的开销。