【编程基础】排序算法

发表于 2020-06-08 更新于 2023-02-01 分类于数据结构本文字数： 4.6k 阅读时长 ≈ 17 分钟

算法衡量方法

在历史中，科学家经常能够得出一些结论，这跟他们猜想，然后不停的做实验证明结果是一样的。一个结论只需要一个错误的推论即可推翻，但是再多的正确实验结果都不能绝对的证明结论就是对的。而关乎算法效率的衡量，可以简单的认为，f(n) = x某种函数关系，我们即可得出算法中关于输入的 数量n 与时间的大致关系，不一定需要特别准确的表示，但是能够近乎的表示即可。比方说一个计算，我们需要三次遍历一个数组中的值：

for (int i = 0; i < n; i++) {
  for (int j = i+1; j < n; j++) {
    for (int k = j+1; k < n; k++) {
      if (a[i] + a[j] + a[k] == 0) {
        // 某种操作
      }
    }
  }
}

然后我们可以开发一个时间计数器，然后通过随机生成不同规模长度的数组来计算他的运行效率：

for (int n = 250; true; n+=n) {
  long startDateTime = System.currentTimeMillis();
  for (int i = 0; i < n; i++) {
    for (int j = i+1; j < n; j++) {
      for (int k = j+1; k < n; k++) {
        if (a[i] + a[j] + a[k] == 0) {
          // 某种条件和操作
        }
      }
    }
  }
  System.out.println("n = " + n + "，耗时：" + (System.currentTimeMillis() - startDateTime) / 1000 + "秒")
}

然后我们可以利用粗糙的数学基础，将图画出来（我是没画出来…）。最后得出，时间复杂度 O(n) = n^3 （我们通常使用 O(n) 来表示事件复杂度）。那这个需要怎么大致出结论呢，大概认为一个 for循环 就是一个 n。关于常用的数量级分类：

描述

增长数量级

示例

常数

1

普通的语句，如 c = a + b

对数

logN

二分查找

线性

N

遍历数组找出最大值

线性对数

NlogN

归并排序

平方

N^2

双层循环，如冒泡算法检查所有的元素树

立方

N^3

平方再套多一层检查其他条件

指数

2^N

穷举查找，检查所有的子集

排序操作

日常开发中，排序的场景可谓贯穿每一个需求，比如订单按照支付日期倒序展示、产品按照上传时间倒序等等。在计算机发展这么多年以来，也出现过很多排序的方法，作为算法入门，排序绝对是无法跳过的。整理下目前著名的排序方法：

选择排序（其实也就是俗称的冒泡）；
插入排序（类比扑克牌的做法）；
希尔排序（对插入排序的优化）；
归并排序；
快速排序；
堆排序

选择排序

选择排序，就是依次迭代数组中，剩余未处理的元素，将最大的或者最小的放在目前迭代数组中的第一位的算法。选择排序的轨迹也比较简单了： OK，那我们现在先准备一个打印函数，以便后续可以用来方便的打印数组进行观察：

private static void printArray(String message, int[] array) {
  System.out.print(message + "：");
  for (int item : array) {
    System.out.print(item + " ");
  }
  System.out.println();
}

冒泡排序的代码也不是很难：

public static void selectSort() {
  int[] array = {17, 67, 11, 34, 22, 41};
  printArray("排序前", array);

  int iterCount = 0;
  for (int i = 0; i < array.length; i++) {
    for (int j = i + 1; j < array.length; j++) {
      if (array[i] > array[j]) {
        int _temp = array[i];
        array[i] = array[j];
        array[j] = _temp;
      }
      iterCount++;
    }
  }
  System.out.println("一共迭代：" + iterCount);
  printArray("排序后", array);
}
// ----------- 
排序前：17 67 11 34 22 41 
一共迭代：15
排序后：11 17 22 34 41 67

而这个算法，我们可以看到，他所需要的迭代次数是 ≈6^2/2，除以2 可以忽略，所以 O(n) = n^2。而且这个算法，即使我们给的数组已经是一个有序的数组，他也需要全部扫描，使用的时间跟完全倒序的数组基本一样。

插入排序

说到排序，可以结合一下我们常玩的扑克牌（揭阳的 上游），我们在开始发牌的时候，先从桌子上拿出来一张牌，然后看看在哪个地方，把这张牌插入到对应的位置，当桌子上所有的牌都已经取到手上的时候，手中的牌也已经是一个有序的状态了，这就是 插入排序。但是这个步骤分解成程序的话，就需要多一点步骤：

眼睛找到位置 –> 程序遍历前面的牌找到位置；
牌插进去合适的位置的时候 –> 需要挪动后面的元素。

public static void insertSort() {
  int[] array = {17, 67, 11, 34, 22, 41};
  printArray("排序前", array);
  // 相当于一次从桌子上取出一张牌子
  int iterCount = 0;
  for (int i = 0; i < array.length; i++) {
    int j = i;
    while (j > 0) {
      // 依次比较，如果取出的这张牌子比目前数组的最后一张小，则把位置挪一挪
      if (array[j] < array[j-1]) {
        int _temp = array[j];
        array[j] = array[j-1];
        array[j-1] = _temp;
      }
      iterCount++;
      j--;
    }
  }
  System.out.println("一共迭代：" + iterCount);
  printArray("排序后", array);
}
// ----------- 
排序前：17 67 11 34 22 41 
一共迭代：15
排序后：11 17 22 34 41 67

诶！！！迭代次数怎么跟 选择排序 一样，那我们在 if (array[j] < array[j-1]) 后面补充一个 else：

public static void insertSort() {
  int[] array = {17, 67, 11, 34, 22, 41};
  printArray("排序前", array);
  // 相当于一次从桌子上取出一张牌子
  int iterCount = 0;
  for (int i = 0; i < array.length; i++) {
    int j = i;
    while (j > 0) {
      iterCount++;
      // 依次比较，如果取出的这张牌子比目前数组的最后一张小，则把位置挪一挪
      if (array[j] < array[j-1]) {
        int _temp = array[j];
        array[j] = array[j-1];
        array[j-1] = _temp;
      } else
        break;    // <---------------------------- 补充Break
      j--;
    }
  }
  System.out.println("一共迭代：" + iterCount);
  printArray("排序后", array);
}
// ----------- 
排序前：17 67 11 34 22 41 
一共迭代：10
排序后：11 17 22 34 41 67

但总的来说我们比较两个算法的计算时间，简单的实验都没法证明，姑且先使用第一版来说吧，因为每次都需要遍历所有的元素，那么大可可以认为 插入排序 和 选择排序 的时间复杂度都是 n^2，但是加入 break 语句以后，计算难度就会提高很多。那么我们先不纠结这些，那么既然 插入排序 和 选择排序 的效率相当，最坏情况下就不一样，插入排序 的最坏情况咧，就是数组刚好是倒序的情况，每个元素都需要重新挪位（也就是无法进入 break 语句），而 选择 无论如何都需要双双遍历。

希尔排序

希尔排序 其实是对 插入排序 的一个优化，他先将数组分割成不同的子数组，子数组的长度为 h，而在 插入排序 的选择阶段，先把 h数组 整成有序的数组，然后 h 不停的递减，直到 h = 1，即实现了上面的 插入排序（但是此时的数组已经是部分有序了，插入交换的次数少必定减少）。由于上面的数组比较短，无法看出规律，我现在重新随机生成一个 15长度 的数组：[51, 13, 9, 84, 35, 43, 82, 68, 29, 42, 67, 50, 34, 46, 83]。

public static void shellSort() {
  int[] array = {51, 13, 9, 84, 35, 43, 82, 68, 29, 42, 67, 50, 34, 46, 83};
  printArray("排序前", array);
  //希尔排序
  int gap = array.length;
  do {
    gap /= 2;   //增量每次减半
    for (int i = 0; i < gap; i++) {
      for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序
        int k = j;
        while (k > 0) {
          if (k - gap >= 0 && array[k] < array[k - gap]) {
            int _temp = array[k];
            array[k] = array[k - gap];
            array[k - gap] = _temp;
          } else {
            break;
          }
          k -= gap;
        }
      }
    }
  } while (gap != 1);

  printArray("排序后", array);
}
// ----------- 
排序前：51 13 9 84 35 43 82 68 29 42 67 50 34 46 83 
排序后：9 13 29 34 35 42 43 46 50 51 67 68 82 83 84

轨迹图：他相比 插入排序 最大的优势就在于，不需要再一步一步的重新替换位置，就算到了最后一步 gap=1 的时候，移动的元素也会变得很少。这种优势在数组越大就越明显，我们可以简单的做一下测试。（原谅我懒得封装，直接把算法拷贝过来用了…）

public static void main(String[] args) {
  long shellTime = 0L;
  long insertTime = 0L;
  int arrayLeng = 10000;

  for (int a = 0; a < 1000; a++) {
    // 拷贝两个数组
    int[] array = randomArray(arrayLeng);
    int[] brray = new int[arrayLeng];
    System.arraycopy(array, 0, brray, 0, arrayLeng);

    long start = System.currentTimeMillis();
    //希尔排序
    int gap = array.length;
    do {
      gap /= 2;   //增量每次减半
      for (int i = 0; i < gap ; i++) {
        for (int j = i + gap; j < array.length; j += gap) {//这个循环里其实就是一个插入排序
          int k = j;
          while (k > 0) {
            if (k - gap >= 0 && array[k] < array[k - gap]) {
              int _temp = array[k];
              array[k] = array[k - gap];
              array[k - gap] = _temp;
            } else {
              break;
            }
            k -= gap;
          }
        }
      }
    } while (gap != 1);
    shellTime += System.currentTimeMillis() - start;

    start = System.currentTimeMillis();
    // 相当于一次从桌子上取出一张牌子
    for (int i = 0; i < brray.length; i++) {
      int j = i;
      while (j > 0) {
        // 依次比较，如果取出的这张牌子比目前数组的最后一张小，则把位置挪一挪
        if (brray[j] < brray[j-1]) {
          int _temp = brray[j];
          brray[j] = brray[j-1];
          brray[j-1] = _temp;
        } else
          break;
        j--;
      }
    }
    insertTime += System.currentTimeMillis() - start;
  }

  System.out.println("希尔1000次排序所需时间：" + (shellTime) + " 毫秒");
  System.out.println("插入1000次排序所需时间：" + (insertTime) + " 毫秒");
}
// ----------- 
希尔1000次排序所需时间：694 毫秒
插入1000次排序所需时间：13718 毫秒

可以看出希尔是真的比较优秀，特别是数组越大，后期结果越明显。在我电脑上，测试 1000_000 长度的数组，希尔排序使用 106ms，插入使用 147095ms。

归并排序

归并排序，指的是将两个已经有序的数组，两两比较，然后将元素分别放进原来数组的操作。所以我们需要通过一个类来记录左右两边两个子数组：

public static void main(String[] args) {
  int[] array = {51, 13, 9, 84, 35};
  printArray("排序前", array);
  new MergeSortCopy().sort(array);
  printArray("排序后", array);

}

public static class MergeSortCopy {

  int[] left;
  int[] right;

  public void sort(int[] array) {
    // 如果只有两个值，开始进行简单的换位
    if (array.length == 2) {
      if (array[0] > array[1]) {
        int t = array[1];
        array[1] = array[0];
        array[0] = t;
      }
      return;
    } else if (array.length <= 1){
      return;
    }

    int leftLeng = array.length / 2;
    left = new int[leftLeng];
    int rightLeng = array.length % 2 == 0 ? array.length / 2 : array.length / 2 + 1;
    right = new int[rightLeng];

    // 拷贝两个数组
    int index = 0;
    for (int i = 0; i < left.length; i++) {
      if (index < array.length) {
        left[i] = array[index++];
      }
    }
    for (int i = 0; i < right.length; i++) {
      if (index < array.length) {
        right[i] = array[index++];
      }
    }

    // 排序左边数组
    new MergeSortCopy().sort(left);
    // 排序右边数组
    new MergeSortCopy().sort(right);

    // 合并操作, left_index 和 right_index 和 array_index
    int li = 0, ri = 0, ai = 0;
    while (true) {
      // 左边用尽
      if (li > left.length - 1) {
        if (ri > right.length - 1) {
          break;
        }
        array[ai++] = right[ri++];
      }
      // 右边用尽
      else if (ri > right.length - 1) {
        if (li > left.length - 1) {
          break;
        }
        array[ai++] = left[li++];
      } else if (left[li] < right[ri]) {
        array[ai++] = left[li++];
      } else if (left[li] > right[ri]) {
        array[ai++] = right[ri++];
      }
    }
  }

}
// ----------- 
排序前：51 13 9 84 35 
排序后：9 13 35 51 84

结果是没有问题的了，但是出现另外一个问题，就是空间的问题，这个数组很小，察觉不到，但是如果数组是一个上万的数组，不停的开辟左右数组，将很容易导致内存被耗尽。所以聪明的大叔们，想起了一个东西，指针，让指针在拷贝过一次的数组上操作。

public static class MergeSort {

  static int[] aux;

  public static void sort(int[] array) {
    aux = new int[array.length];
    sort(array, 0, array.length - 1);
  }

  /**
     * 对数组指定的位置进行排序.
     *
     * @param array 数组.
     * @param lo 低位，相当于左数组的指针.
     * @param hi 高位，相当于右数组的指针.
     */
  private static void sort(int[] array, int lo, int hi) {
    // 2. 切割到高位等于或者小于低位的时候停止切割
    if (hi <= lo) return;
    // 1. 总是将数组切割成2部分
    int mid = lo + (hi - lo) / 2;
    sort(array, lo, mid);
    sort(array, mid + 1, hi);
    merge(array, lo, mid, hi);
  }

  private static void merge(int[] array, int lo, int mid, int hi) {
    // i = 左边数组的指针，j = 右边数组的指针，k = 最右边的那个指针
    int i = lo, j = mid + 1;
    for (int k = lo; k <= hi; k++) {
      aux[k] = array[k];
    }
    // 从左指针跑到右边指针
    for (int k = lo; k <= hi; k++) {
      // 左数组用尽，开始使用右边数组的元素
      if (i > mid) {
        array[k] = aux[j++];
      }
      // 右边数组用完，开始使用左边数组的元素
      else if (j > hi) {
        array[k] = aux[i++];
      } 
      // 左右比较大小，看看放哪个
      else if (aux[j] < aux[i]) {
        array[k] = aux[j++];
      } else {
        array[k] = aux[i++];
      }
    }
  }

}
// ----------- 
排序前：51 13 9 84 35 
排序后：9 13 35 51 84

我们可以来分解下运行轨迹：

sort(array, 0, 4)
    // 左边部分开始
    sort(array, 0, 2)
        sort(array, 0, 1)
            sort(array, 0, 0) 被返回掉，所以这部分忽略，从上面一层开始合并
            merge(array, 0, 0, 1)
        sort(array, 1, 2)
            sort(array, 1, 1) 被返回掉，所以这部分忽略，从上面一层开始合并
            merge(array, 1, 1, 2)
    // 右边部分开始
    sort(array, 3, 4)
        sort(array, 3, 3) 被返回掉，所以这部分忽略，从上面一层开始合并
        merge(array, 3, 3, 4)
    merge(array, 0, 2, 4)

然后我们给她换个方向：哦豁，是一个树！所以这种已经是类似于 二分查找 的思路了，也就是时间复杂度是 lgN

快速排序

快排 和 合并排 有点相似，合并排是无论数组如何都从中间切，然后左右分别排序，再合并起来。而 快排 则是先找出一个元素确定好的他的位置，然后再使用同样的方法去排序左右两个部分（左右两部分不一定相等长度）。

public static void main(String[] args) {
  int[] array = {51, 13, 9, 84, 35};
  printArray("排序前", array);
  quickSort(array);
  printArray("排序后", array);
}

public static void quickSort(int[] array) {
  quickSort(array, 0, array.length - 1);
  System.out.println(Arrays.toString(array));
}

public static void quickSort(int[] array, int lo, int hi) {
  if (hi <= lo) {
    return;
  }
  int pi = partition(array, lo, hi);
  quickSort(array, lo, pi - 1);
  quickSort(array, pi + 1, hi);
}

public static int partition(int[] array, int lo, int hi) {
  int li = lo, ri = hi + 1;
  int partitionVal = array[lo];
  while (true) {
    while (array[++li] < partitionVal) {
      if (li == hi) {
        break;
      }
    }
    while (partitionVal < array[--ri]) {
      if (ri == lo) {
        break;
      }
    }
    if (li >= ri) {
      break;
    }

    // 交换左右部分的元素
    int _t = array[li];
    array[li] = array[ri];
    array[ri] = _t;
  }

  // 再把第一个确定的元素放在他应该在的位置
  int _t = array[lo];
  array[lo] = array[ri];
  array[ri] = _t;

  return ri;
}
// ----------- 
排序前：51 13 9 84 35 
排序后：9 13 35 51 84

快排 的最差情况就是，第一次从最小的元素开始切分，而第二次也是从第二小的元素开始切分，这结果就很糟糕，所以为了防止这种情况的发生我们可以将需要排序的数组进行一次洗牌（有很多工具类已经实现了）。当然如果数组中存在大量的重复元素的时候，快排 就显得很多操作是多余的，那么 三向切分 就出现了，主要多维护一个指针指向相同的元素的高位，也就是类似于下图这样：那么我们就需要保证 指针lo < lt = gt < 指针hi。代码就不写了因为我懒…

堆排序

堆是一个 完全二叉树，关于二叉树的定义：一棵树，从上到下，从左到右进行排列，则可称为完全二叉树。而 二叉堆 则是加多一个条件，每个结点都大于或者等于他的两个子节点。 完全二叉树 可以使用一个数组对象装着：如图，我们可以从 下标1 开始装数据，0位 就让他空着吧，这样我们在请求子节点的时候会方便很多。仔细观察可以看出，子节点index = 父节点index*2 和 父节点index*2+1。那么我们就可以创建一个类来存储这个 二叉堆：那比方说，我在上面那颗树插入 11：那我现在就需要把这个点往上移动，也就是所说的 浮上去：那他的 下标 = 6 的 “爸爸” 就是 6 / 2，再 “爸爸” 就是 3 / 2 了。所以我们需要在这几个上面比较大小，让他上去，所以我们很容易就：

/**
  * 将元素上浮.
  *
  * @param idx 索引.
  */
private void swim(int idx) {
  while (idx > 1 && pq[idx / 2] < pq[idx]) {
    // 与父级交换
    int t = pq[idx / 2];
    pq[idx / 2] = pq[idx];
    pq[idx] = t;
    idx = idx / 2;
  }
}

那通过上面的例子我们可以看出，节点就是最大的点，那如果我们提供一个方法 delMax() 用来删除堆中最大的元素咧，我们就需要先用一个最小的点顶上这个位置，然后，把这个元素下沉到最合适的位置，还是那颗树：那我们现在就需要把 下标=1 进行下沉，那么下沉的下标轨迹就是 1、2、4：

/**
 * 将元素下沉.
 *
 * @param idx 索引.
 */
private void sink(int idx) {
  while (idx * 2 <= size) {
    int childIdx = idx * 2;
    // 比方传递进来的是1，childIdx = 2，
    // 如果1的右节点比左节点大，那么跟右节点进行交换
    if (childIdx < size && pq[childIdx] < pq[childIdx + 1]) {
      childIdx++;
    }
    // 一直到父节点大于等于子节点的时候，将循环打断
    if (!(pq[idx] < pq[childIdx])) {
      break;
    }

    // 交换交换
    int t = pq[idx];
    pq[idx] = pq[childIdx];
    pq[childIdx] = t;

    idx = childIdx;
  }
}

那么我们排序的时候就可以简单的使用这个类：

public static void main(String[] args) {
  int[] array = {51, 13, 9, 84, 35};
  printArray("排序前", array);
  HeapSort heapSort = new HeapSort(array);
  System.out.println(heapSort);

  for (int i = 0; i < array.length; i++) {
    int i1 = heapSort.delMax();
    System.out.println(i1);
  }

}

public static class HeapSort {

  private int[] pq;
  public int size;

  public HeapSort(int[] arr) {
    this.size = 0;
    this.pq = new int[arr.length + 1];
    for (int i : arr) {
      insert(i);
    }
  }

  public void insert(int ele) {
    pq[++size] = ele;
    swim(size);
  }

  /**
   * 将元素上浮.
   *
   * @param idx 索引.
   */
  private void swim(int idx) {
    while (idx > 1 && pq[idx / 2] < pq[idx]) {
      int t = pq[idx / 2];
      pq[idx / 2] = pq[idx];
      pq[idx] = t;
      idx = idx / 2;
    }
  }

  /**
   * 将元素下沉.
   *
   * @param idx 索引.
   */
  private void sink(int idx) {
    while (idx * 2 <= size) {
      int childIdx = idx * 2;
      // 比方传递进来的是1，childIdx = 2，
      // 如果1的右节点比左节点大，那么跟右节点进行交换
      if (childIdx < size && pq[childIdx] < pq[childIdx + 1]) {
        childIdx++;
      }
      if (!(pq[idx] < pq[childIdx])) {
        break;
      }

      int t = pq[idx];
      pq[idx] = pq[childIdx];
      pq[childIdx] = t;

      idx = childIdx;
    }
  }

  public int delMax() {
    int maxIdx = 1;
    int ele = pq[maxIdx];

    pq[maxIdx] = pq[size--];
    pq[size + 1] = 0;
    sink(1);

    return ele;
  }

  @Override
  public String toString() {
    return "HeapSort{" +
        "pq=" + Arrays.toString(pq) +
        ", size=" + size +
        '}';
  }
}
// ----------- 
排序前：51 13 9 84 35 
HeapSort{pq=[0, 84, 51, 9, 13, 35], size=5}
84
51
35
13
9

小顶堆

我们上面所示的，顶点最大称为 大顶堆，那如果顺序反过来，顶点 最小的就称为 小顶堆，我们可以简单的将 sink 和 swim 修改判断条件即可实现 小顶堆。