排序

快速排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      quick_sort(arr, 0, arr.size()-1); 
      return arr;
    }
  
  private:
    void quick_sort(std::vector<int> &arr, int low, int high) {
      if (low < high) {
        int key = partition(arr, low, high);
        quick_sort(arr, low, key-1);
        quick_sort(arr, key+1, high);
      }
    }
    int partition(std::vector<int> &arr, int low, int high) {
      int base = low;  // 第一个元素作为基准
      while (low < high) {
        while (arr[high] > arr[base] && low < high) --high;
        while (arr[low] <= arr[base] && low < high) ++low;
        std::swap(arr[low], arr[high]);
      }
      if (arr[base] >= arr[low]) {   //  这里使用等于判断，防止首元素进行交换时产生越界
        std::swap(arr[base], arr[low]);
        return low;
      } else {
        std::swap(arr[base], arr[low-1]);
        return low-1;
      }
    }
};

归并排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      merge_sort(arr, 0 , arr.size()-1);
      return arr;
    }
  
  private:  
    void merge_elem(std::vector<int> &arr, int low, int mid, int high) {
      std::vector<int> temp;
      int i = low, j = mid + 1;
      
      // 排序插入
      while (i <= mid && j <= high) {
        if (arr[i] <= arr[j]) {
          temp.push_back(arr[i++]);
        } else {
          temp.push_back(arr[j++]);
        }
      }
      
      // 遍历剩下部分
      while (i <= mid) {
        temp.push_back(arr[i++]);
      }
      while (j <= high) {
        temp.push_back(arr[j++]);
      }
     
      // 拷贝回原数组
      for (int i = low, j = 0; i <= high; i++) {
        arr[i] = temp[j++];
      }
    }
    
    void merge_sort(std::vector<int> &arr, int low, int high) {
      if (low < high) {    // 分割到两个元素
        int mid = (low+high) / 2;
        merge_sort(arr, low, mid);
        merge_sort(arr, mid+1, high);
        merge_elem(arr, low, mid, high);   // 递归到两个元素后合并回退
      }
    }
};

堆排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      heap_sort(arr, 0, arr.size()-1);
      return arr;
    }
  
  private:
    void sink(std::vector<int> &arr, int node, int size) {
      while (2*node + 1 <= size) {
        int max_node = 2*node + 1;
        if (max_node < size && arr[max_node] < arr[max_node+1]) {  // 找到最大孩子
          max_node++;
        }
        if (arr[node] >= arr[max_node]) {
          break;
        } else {
          std::swap(arr[node], arr[max_node]);
        }
        node = max_node;   // 持续下沉到叶子结点或满足条件
      }
    }
    // 从零开始，使用(n-1)/2
    void heap_sort(std::vector<int> &arr, int low, int high) {
      for (int i = (high-1) / 2; i >= 0; i--) {   // 构建最大堆 
        sink(arr, i, high);
      }
      while (high > 0) {    // 交换-下沉 完成排序
        std::swap(arr[high--], arr[0]);   // 最大元素挪到末尾，再调整堆
        sink(arr, 0, high);
      }
    }
};

冒泡排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr; 
      }
      bubble_sort(arr, arr.size()-1);
      return arr;
    }
  
  private:
    void bubble_sort(std::vector<int> &arr, int size) {
      for (int i = 0; i < size; i++) {  // n个元素循环n-1次
        for (int j = 0; j < size; j++) {  // 每次取出最大元素到最尾
          if (arr[j] > arr[j+1]) {
            std::swap(arr[j], arr[j+1]);
          }
        }
      }
    }
};

选择排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr;
      }
      selection_sort(arr, arr.size()-1);
      return arr;
    }
  
  private:
    void selection_sort(std::vector<int> &arr, int size) {
      // 第一层循环选中n-1个元素
      // 从选中元素后面 挑选出最小的元素与当前元素交换
      // 选中元素最小则不交换
      for (int i = 0; i < size; i++) {
        int min = arr[i];
        int index = i;
        for (int j = i+1; j <= size; j++) {
          if (arr[j] < min) {
            min = arr[j];
            index = j;
          }
        }
        if (index != i) {
          std::swap(arr[i], arr[index]);
        }
      }
    }
};

插入排序

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr;
      }
      insertion_sort(arr, arr.size()-1);
      return arr;
    }
  
  private:
    void insertion_sort(std::vector<int> &arr, int size) {
      for (int i = 1; i <= size; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
          arr[j+1] = arr[j];
          j--;
        }
        arr[j+1] = key;
      }
    }
};

计数排序（适合数据集在小区间范围）

class Solution {
  public:
    vector<int> MySort(vector<int>& arr) {
      if (arr.empty()) {
        return arr;
      }
      counting_sort(arr, arr.size()-1);
      return arr;
    }
  
  private:
    void counting_sort(std::vector<int> &arr, int size) {
      int max = arr[0];
      std::vector<int> copy_arr(arr);  // 辅助数组
      for (int i = 0; i <= size; i++) {
        if (arr[i] > max) {
          max = arr[i];
        }
      }  
      std::vector<int> temp(max+1, 0);  // 大小为数据区间
      for (int i = 0; i <= size; i++) {
        temp[arr[i]]++;  // 统计每个值出现的次数，存放在对应下标
      }
      // 计数累加
      for (int i = 1; i < temp.size(); i++) {
        temp[i] += temp[i-1];   // 记录当前值排的位数
      }
      // 反向填充数组
      for (int i = size; i >= 0 ; i--) {
        arr[--temp[copy_arr[i]]] = copy_arr[i];  // 索引比计数值小1，先自减
      }
    }
};

桶排序 基数排序 希尔排序暂无