Skip to main content

排序算法总结

排序就是将一组对象按照某种逻辑顺序重新排列的过程。

选择排序​

对于数组 arr，从小至大排序，算法步骤如下：

  1. 对于arr[i]，寻找区间[i + 1,n]最小值 min 索引 index；

  2. 交换arr[i]和arr[index]。

特点：

  1. 运行时间和输入数组是否有序无关；

  2. 数据移动最少，仅有N次交换。

代码实现：

// 选择排序
// 对于每一个索引，在该索引之后选择一个最小的值，然后与该索引交换
// 这样就能确保获得每一个最小的值
inline void select_sort(std::vector<int> &arr) {
  for (int i = 0; i < arr.size(); i++) {
    int ele = arr[i];
    int min_index = i;
    for (int j = i + 1; j < arr.size(); j++) {
      if (arr[j] < arr[min_index]) {
        min_index = j;
      }
    }

    swap(&arr[i], &arr[min_index]);
  }
}

插入排序​

对于数组 arr，从小至大排序，算法步骤如下：

  1. 对于arr[i]，保持左方有序，判断区间[0, i]，若arr[i] < arr[i - 1]，则使得大值右移；

  2. 直到arr[i] >= arr[i - 1]结束右移，插入arr[i]。

代码实现：

// 插入排序
// 要求0-i必须是有序的，对于arr[i]，判断其在 0-i 内插入的索引即可
inline void insert_sort(std::vector<int> &arr) {
  for (int i = 1; i < arr.size(); i++) {
    int a = arr[i];
    int j = i;
    while (j > 0 && arr[j - 1] > a) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = a;
  }
}

希尔排序​

希尔排序基于插入排序优化得来。

对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点一点的从数组的一端移动到另一端，这很不高效。

希尔排序的思想时使数组中任意间隔为h的元素都是有序的，这样的数组被称为h 有序数组。换句话说，一个 h 有序数组就是由 h 个互相独立的有序数组编织在一起组成的一个数组。这样，在进行排序时，如果 h 很大，我们就能把元素移动到很远的地方，为实现更小的 h 有序创造方便。

代码实现：

public static class Shell {
    public static void sort(Comparable[] arr) {
        int N = arr.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1;
        while (h >= 1) {
            for (int i = h; i < N; i++) {
                Comparable temp = arr[i]; // 要插入的元素
                int j = i;
                while (j >= h && less(temp, arr[j - h])) {
                    arr[j] = arr[j - h];
                    j -= h;
                }
                if (j != i) {
                    arr[j] = temp;
                }
            }
            h /= 3;
        }
    }
}

归并排序​

归并排序算法思路：要将一个数组排序，可以先递归地将它分成两半进行排序，然后将结果归并起来。

算法实现：

namespace {
void merge(std::vector<int> &arr, int lo, int mid, int hi);

inline void helper(std::vector<int> &arr, int lo, int hi) {
  if (lo >= hi)
    return;

  int mid = lo + ((hi - lo) >> 1);
  // left
  helper(arr, lo, mid);
  // right
  helper(arr, mid + 1, hi);
  merge(arr, lo, mid, hi);
}

inline void merge(std::vector<int> &arr, int lo, int mid, int hi) {
  static std::vector<int> aux(arr.size(), 0);
  int i = lo, j = mid + 1;
  for (int k = lo; k <= hi; k++) {
    aux[k] = arr[k];
  }
  for (int k = lo; k <= hi; k++) {
    if (i > mid)
      arr[k] = aux[j++];
    else if (j > hi)
      arr[k] = aux[i++];
    else if (aux[i] < aux[j])
      arr[k] = aux[i++];
    else
      arr[k] = aux[j++];
  }
}
}; // namespace

// 归并排序
// 归并排序的重点是对数组的两部分分别排序，然后将结果归并
inline void merge_sort(std::vector<int> &arr) {
  helper(arr, 0, arr.size() - 1);
}

快速排序​

快速排序基于分治思想，将一个数组分成两个子数组，两部分独立地进行排序。

快速排序和归并排序是互补的：归并排序是将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序；

而快速排序将数组排序的方式则是当两个子数组都有序时整个数组自然就有序了。

快速排序的左半部分不大于某个值，右半部分不小于某个值，那么两部分分别排好序后，自然就有序了。

算法实现：

namespace {
inline int partition(std::vector<int> &arr, int lo, int hi) {
  int partition = arr[hi];
  int index = lo;
  for (int i = lo; i < hi; i++) {
    if (arr[i] < partition) {
      swap(&arr[i], &arr[index++]);
    }
  }
  swap(&arr[hi], &arr[index]);
  return index;
}
}; // namespace

inline void quick_sort(std::vector<int> &arr, int lo, int hi) {
  if (lo >= hi)
    return;
  // 分治
  int index = partition(arr, lo, hi);
  quick_sort(arr, lo, index - 1);
  quick_sort(arr, index + 1, hi);
}