经典排序算法

1. 排序算法简介

1.1 算法分类

• 比较类排序（非线性时间比较类排序）：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)。
• 非比较类排序 （线性时间非比较类排序）：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行。
  排序算法

1.2 算法复杂度

名词解释：
n: 数据规模
k:“桶”的个数
In-place: 占用常数内存，不占用额外内存；（固定内存）
Out-place: 占用额外内存
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。

2. 冒泡排序（Bubble Sort）

大学上过编程课的基本都写过冒泡排序的 Demo。

2.1 算法描述

从第一位开始向高位寻找最大值，往后移动，直到最后一位。

具体算法描述如下：
<1> 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
<2> 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
<3> 针对所有的元素重复以上的步骤，除了最后一个；
<4> 重复步骤1~3，直到排序完成。

2.2 算法示意图

冒泡排序

2.3 代码实例

private static void bubbleSort(Integer[] arr){
      // --- 冒泡排序 ---;
      int length = arr.length;
      for (int i = length; i >=0; i--){
          for (int j = 0; j < i-1; j++) {
              if (arr[j+1] < arr[j]) {
                  int tmp = arr[j];
                  arr[j] = arr[j+1];
                  arr[j+1] = tmp;
              }
          }
          printArr(arr);
      }
  }

2.4 算法分析

最稳定的排序算法之一，无论数据集是多少，时间复杂度是O(n) ~ O(n²)，唯一优点，不占用更多内存空前。
可以对冒泡进行改进，就是双向冒泡，时间复杂度会减半；

3. 选择排序（Selection Sort）

遍历元素，依次找到位置正确顺序的值，再交换。

3.1 算法描述

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置;
2. 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾;
   以此类推，直到所有元素均排序完毕。

3.2 算法示意图

选择排序

3.3 代码实现

private static void selecttionSort(Integer[] arr){
        logLn("--- 选择排序 ---");
        int length = arr.length;
        for (int i = 0; i < length; i++){
            int tmpIndex = i;
            for (int j = i+1; j < length; j++) {
                if (arr[tmpIndex] > arr[j]) {
                    tmpIndex = j;
                }
            }
            // 交换数据位置
            swap(arr, i, tmpIndex);
            printArr(arr);
        }
    }

3.4 算法分析

最稳定排序算法，无论数据集是多少，时间复杂度是O(n²)，数据量少可以考虑实用, 不占用更多内存空前。

4. 插入排序（Insertion Sort)

4.1 算法描述

4.2 算法分析

4.3 算法分析

4.4 算法分析