排序算法是计算机科学中非常重要的一类算法。通过排序算法，我们可以对数据进行排序，从而更容易地检索、分析和处理数据。本文将介绍以下几种常见的排序算法：

  1. 冒泡排序
  2. 选择排序
  3. 插入排序

注意：
如无特殊说明，默认都是按照正序排序，即从左到右从小到大的顺序

冒泡排序

冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

排序过程很像水中的气泡，较大的气泡会优先上升，因此得名

算法步骤

  1. 比较相邻的两个元素。如果第一个比第二个大，就交换它们两个；
  2. 每一对相邻元素做同样的操作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
  3. 针对所有的元素重复以上的步骤，除了最后一个；
  4. 重复步骤 1-3，直到排序完成。
冒泡

代码实现

/**
 * 冒泡算法：
 * 一共 n-1 轮比较，每轮通过比较相邻两个数据确定一个最大值；
 * 两层 for 循环，外层是轮数，内层是比较相邻数据  
 * 【swap 中只能记录需要交换的下标，不能记录交换的数据】
 */
public static void bubbleSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    for (int n = arr.length - 1; n > 0; n--) { // 0 ~ n
        for (int i = 0; i < n; i++) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
            }
        }
    }
}

选择排序

选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据中选出最小（或最大）的一个元素，存放在数列的起始位置，直到全部待排序的数据元素排完。

注意：

  1. 将整体数据分成两部分：有序部分和无序部分
  2. 整体开始为无序状态，然后依次选出一个最值填充有序部分

算法步骤

  1. 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
  2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
  3. 重复步骤 2，直到所有元素均排序完毕。

代码实现

/**
 * 选择排序：
 * 一共 n-1 轮比较，每轮先选定最小值所在的索引位置，通过与其他位置比较最终确定；
 * 两层 for 循环，外层是轮数，内层确定最小值的位置
 * 【swap 中只能记录需要交换的下标，不能记录交换的数据】
 */
public static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }
    // 0 ~ N-1  找到最小值，在哪，放到0 位置上
    // 1 ~ n-1  找到最小值，在哪，放到1 位置上
    // 2 ~ n-1  找到最小值，在哪，放到2 位置上
    for (int i = 0; i < arr.length - 1; i++) {
        // 只能记录索引/下标，不能是对应的值
        int minIndex = i;
        // i ~ N-1 上找最小值的下标
        for (int j = i + 1; j < arr.length; j++) { 
            minIndex = arr[j] < arr[minIndex] ? j : minIndex;
        }
        swap(arr, i, minIndex);
    }
}

插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

注意：

  1. 同样将整体数据分成两部分：有序部分和无序部分
  2. 单独一个数据为有序的
  3. 从无序部分依次插入到有序部分的正确位置
  4. 过程很像打牌

算法步骤

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤 2-5。

代码实现

/**
 * 插入排序：【打牌，新来一张牌需要和前面的比较确定位置】
 */
public static void insertionSort(int[] arr) {
 if (arr == null || arr.length < 2) {
  return;
 }
 // 不只1个数
 for (int i = 1; i < arr.length; i++) { // 0 ~ i 做到有序
  for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
   swap(arr, j, j + 1);
  }
 }
}

交换方法

public static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}
//////////////////////////////////////////////////
public static void swap(int[] arr, int i, int j) {
    /**
     * 异或运算：
     *  相同为0；不同为1；
     *  0 ^ 0 = 0
     *  1 ^ 1 = 0
     *  0 ^ 1 = 1
     *  1 ^ 0 = 1
     *  可以理解为：【无进位相加】
     *
     * 小结：
     *  1> 0 ^ n = n  n ^ n = 0
     *  2> 满足交换律和结合律
     *   a ^ b = b ^ a
     *   a ^ b ^ c = a ^ (b ^ c)
     *  3> 由上面推断：N个数据异或运算的最终结果与计算过程中的异或顺序无关
     */
    arr[i] = arr[i] ^ arr[j];
    arr[j] = arr[i] ^ arr[j];
    arr[i] = arr[i] ^ arr[j];
}

小结

以上介绍了常见的排序算法：冒泡排序、选择排序、插入排序。我们发现同一个问题可以有不同的算法解决。那么不同的算法如何评价，孰优孰劣，又该如何选择？