排序

1. 冒泡排序（不稳定）

vector<int> arr = { 1, 2, 3, 4, 5 };
for(int end = arr.size() - 1; end > 0; end--) {
    // 从第二个位置开始比，每次和前一个元素比对，一直比对到最后面一个元素
    // 这样，每一轮循环之后，最大的元素会在最后
    // 同时，下一个循环需要在之后一个元素之前的序列中再次进行，所以，每次排序后最后比对的位置要前移，即end--
    for(int begin = 1; begin <= end; begin++) {
      if(arr[begin] < arr[begin-1]) {
        int tmp = arr[begin];
        arr[begin] = arr[begin-1];
        arr[begin-1] = tmp;
      }
    } 
}
// 优化
// 以上算法中，每一轮循环都要从第一个到最后一个位置进行遍历
// 那么，如果对于有序的数组来说，依然要进行没有必要的遍历，其实这是浪费的
// 所以，我们可以在当前轮遍历时判断是不是已经有序了，如果已经有序了，直接退出循环即可
vector<int> arr = { 1, 2, 3, 4, 5 };
for(int end = arr.size() - 1; end > 0; end--) {
    bool isSorted = true;  // 在每一轮循环前，假定是已经有序了
    for(int begin = 1; begin <= end; begin++) {
      if(arr[begin] < arr[begin-1]) {  // 如果发生了交换，说明是无序的
        int tmp = arr[begin];
        arr[begin] = arr[begin-1];
        arr[begin-1] = tmp;
        isSorted = false;
      }
    }
    // 如果当前循环没有发生交换，说明数组已经有序了，直接退出循环即可
    if(isSorted) break;
}
// 不过，对于一个数组来说，上面已经有序或者排几轮就有序的情况概率比较低
// 最坏情况下 isSorted 根本不起作用，而且对于 CPU 指令来说，还多了几个步骤，相比原始算法还稍微耗时
// 那么如何继续优化呢?
// 可以根据最后几个已经有序的情况来处理
// 如果最后几个已经有序了，那么可以记录下最后一个交换的位置，下一次循环直接到最后一个交换的位置即可
vector<int> arr = { 1, 2, 3, 4, 5 };
for(int end = arr.size() - 1; end > 0; end--) {
    bool sortedIndex = 1;  // sortedIndex = 1是给已经有序的情况处理的
    // 如果已经有序了，for loop 中的 sortedIndex 不会被改值
    // 那么 end = sortedIndex = 1，下一个轮次中 end-- == 0 就直接退出了，这不巧了吗
    for(int begin = 1; begin <= end; begin++) {
      if(arr[begin] < arr[begin-1]) {
        int tmp = arr[begin];
        arr[begin] = arr[begin-1];
        arr[begin-1] = tmp;
        sortedIndex = begin;
      }
    }
    // 把最后一次交换的位置赋值给 end ，下一次直接遍历到这个位置即可
    end = sortedIndex;
}

2. 选择排序（不稳定）

vector<int> arr = { 1, 2, 3, 4, 5 };
for(int end = arr.size() - 1; end > 0; end--) {
    int maxIndex = 0;
    for(int begin = 1; begin <= end; begin++) {
      if(arr[begin] > arr[maxIndex]) {
        maxIndex = begin;
      }
    }
    int tmp = arr[maxIndex];
    arr[maxIndex] = arr[end];
    arr[end] = tmp;
}

3. 插入排序（稳定）

vector<int> arr = {23, 12, 55, 6, 98};
for(int begin = 1; begin < arr.size(); begin++) {
  int cur = begin;
  while(cur > 0 && arr[cur] < arr[cur - 1]) {
    swap(arr[cur], arr[cur-1]);
    cur--;
  }
}

4. 归并排序（稳定）

void sort(int begin, int end);
void merge(int begin, int mid, int end);

vector<int> arr = {1, 2, 3, 4, 5};
vector<int> leftArray(arr.size() >> 1);
sort(0, arr.size());

void sort(int begin, int end) {
  if(end - begin < 2) { // (递归终止条件)小于2个元素
    return;
  }
  int mid = (begin + end) >> 1;
  // 分成2半，对左边进行排序，对右边进行排序
  // [begin, mid), [mid, end)
  sort(begin, mid);
  sort(mid, end);
  merge(begin, mid, end);
}

// 将 [begin, mid), [mid, end) 范围的序列合并成一个有序序列
void merge(int begin, int mid, int end) {
  int li = 0;
  int le = mid - begin;
  int ri = mid;
  int re = end;
  int ai = begin;

  // 备份左边数组
  for(int i = li; i < le; i++) {
    leftArray[i] = arr[begin + i];
  }

  while(li < le) { // 左边还没结束才执行操作
      if(ri < re && arr[ri] < leftArray[li]) {
      arr[ai] = arr[ri];
      ai++;
      ri++;
    } else {
      arr[ai] = leftArray[li];
      ai++;
      li++;
    }
  }
}

5. 堆排序（不稳定）

vector<int> arr = {1, 2, 3, 4, 6, 7};
int heapSize = arr.size();

// 1. 建堆，采用自下而上的下溢
// (size >> 1) - 1 : 最后一个非叶子节点的索引
// 完全二叉树非叶子节点为 floor(n/2) 即 总数的一半
// 即第一个叶子节点的索引为 size 的一半,所以(size >> 1) - 1 : 最后一个非叶子节点的索引
for(int i = (heapSize >> 1) - 1; i >= 0; i--) {
  siftDown(i);
}

void siftDonw(int index) {
  int element = arr[index];

  // 既然要下滤，说明要有子节点
  // 完全二叉树从上到下，从左到右，遇到第一个叶子结点之后的节点全是叶子结点
  // 所以只要对所有非叶子节点下滤即可
  // 非叶子节点：floor(n/2), 叶子节点：floor((n+1)/2)
  int half = heapSize >> 1;
  while(index < half) {  // 所以 index 必须是非叶子节点

    // 默认 childIndex 是左子节点
    int childIndex = (index << 1) + 1;
    int child = arr[childIndex];

    // 右子节点下标 = 左子节点下标 + 1  
    int rightIndex = childIndex + 1;

    // 右子节点比左子节点大
    if(rightIndex < heapSize && arr[rightIndex] > child) {
      child = arr[rightIndex];
      childIndex = rightIndex;
    }

    // 当前节点比子节点大
    if(element > child) {
      break;
    }

    // 将子节点赋值给当前节点
    arr[index] = child;

    // 更新 index 为较大的子节点下标(左右子节点中较大的那个)
    index = childIndex;
  }
  arr[index] = element;
}

// 2. 重复循环，直至堆中只有一个节点
while(heapSize > 1) {
  heapSize = heapSize - 1;
  // 第一个元素和最后一个元素交换，即把最大的值放到最后
  int tmp = arr[0];
  arr[0] = arr[heapSize];
  arr[heapSize] = tmp;

  // 对第一个元素进行下溢，重新调整堆的结构
  siftDonw(0);
}

6. 快速排序（不稳定）

快速排序的思想如下，找到一个数，使得最终结果，小于这个数的全部在左边，大于这个数的全部在右边，然后对于左边和右边分别进行快速排序，那么，这种把整个数组分成2部分的操作唱叫做 partition ,,具体过程如下示意：

如果arr[i] > v:

但是，如果arr[i] < v:即把arr[i]和arr[j+1]做一个交换，同时j++向后移

经过这样的操作，会得到这样一部分：

最后只需要把l位置和j位置进行交换就能达到我们要的结果：

代码如下：

// 对 arr[l, r] 部分进行 partition 操作
// return index p, make arr[l...p-1] < arr[p]; arr[p+1...r] > arr[p]
template <typename T>
int __partition(T arr[], int l, int r) {
    T v = arr[l];

    // arr[l+1...j] < v; arr[j+1...i) > v
    int j = l;
    for(int i = l + 1; i <= r; i++) {
        if(arr[i] < v) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

template <typename T>
void __quickSort(T arr[], int l, int r) {
    if(l >= r) {
        return;
    }
    // p 是 如上 v 的索引
    int p = __partition(arr, l, r);

    // 对左边进行快排
    __quickSort(arr, l, p - 1);

    // 对右边进行快排
    __quickSort(arr, p + 1, r);
}

template <typename T>
void quickSort(T arr[], int n) {
    __quickSort(arr, 0, n - 1);
}

但是，当数组近乎有序或者完全有序的情况，没有找到一个元素小于标定元素，此时，这个快排的递归树高度为 n,时间复杂度退化为 n^2

所以，我们需要随机选择一个元素作为标定元素即可

template <typename T>
int __partition(T arr[], int l, int r) {

    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];

    // arr[l+1...j] < v; arr[j+1...i) > v
    int j = l;
    for(int i = l + 1; i <= r; i++) {
        if(arr[i] < v) {
            swap(arr[j + 1], arr[i]);
            j++;
        }
    }
    swap(arr[l], arr[j]);
    return j;
}

template <typename T>
void __quickSort(T arr[], int l, int r) {
    if(l >= r) {
        return;
    }
    int p = __partition(arr, l, r);
    __quickSort(arr, l, p - 1);
    __quickSort(arr, p + 1, r);
}

template <typename T>
void quickSort(T arr[], int n) {
    srand(time(NULL));
    __quickSort(arr, 0, n - 1);
}

这里已经进行了一步优化，但是，如果存在大量与标定元素相同的元素，会造成分割的左右边非常不平衡，因此我们需要再次优化如下：

当i对应的值>=v, j对应的值<=v时，交换他们的值

此时，我们只需要改变 partition 的逻辑即可(双路快排)

template <typename T>
int __partition2(T arr[], int l, int r) {

    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];

    // arr[l+1...i) <= v, arr[j...r] >= v
    int i = l + 1, j = r;
    while(true) {
        while(i <= r && arr[i] < v) i++;
        while(j >= l + 1 && arr[j] > v) j--;
        if(i > j) break;
        swap(arr[i], arr[j]);
        i++;
        j--;
    }
    // 循环结束后 i 停在从左往右看第一个 >=v 的位置，j 停在从右往左看第一个 <=v 的位置
    // 而标定点的位置在 <= v的这一端，所以要和 arr[j] 交换
    swap(arr[l], arr[j]);
    return j;
}

不过，对于有重复元素的数组，我们除了双路快排，还有3路快排，即把数组分成3部分，小于v的，等于v的，和大于v的

当i=v，直接纳入绿色部分，i++、
当i当i>v，和gt的前一个元素交换即可,gt—

最后处理完成之后的数组就会被处理成这样：

最后，我们只需要把v和lt交换一下即可，然后递归小于v的和大于v的即可，等于v的不用管了，就省了很多元素

template <typename T>
void __quickSort3Ways(T arr[], int l, int r) {
    if(l >= r) {
        return;
    }
    // partition
    swap(arr[l], arr[rand() % (r - l + 1) + l]);
    T v = arr[l];
    int lt = l; // arr[l+1...lt] < v
    int gt = r + 1; // arr[gt...r] > v
    int i = l + 1; // arr[l+1...i) == v
    while(i < gt) {
        if(arr[i] < v) {
            swap(arr[i], arr[lt + 1]);
            lt++;
        } else if(arr[i] > v) {
            swap(arr[i], arr[gt - 1]);
            gt--;
        } else {
            i++;
        } 
    }
    swap(arr[l], arr[lt]);
    __quickSort3Ways(arr, l, lt -1);
    __quickSort3Ways(arr, gt, r);
}

template <typename T>
void quickSort3Ways(T arr[], int n) {
    srand(time(NULL));
    __quickSort3Ways(arr, 0, n - 1);
}