C++实现各种排序算法

#include<bits/stdc++.h>
using namespace std;

//直接插入排序 
void st_insert_sort(vector<int>& nums) {
  int n = nums.size();
  for(int i = 1; i < n; i++) {
    int cur = nums[i];
    int j = i - 1;
    while(cur < nums[j] && j >= 0) {
      nums[j + 1] = nums[j];
      j--;
    }
    j != -1 ? nums[j + 1] = cur : nums[0] = cur;
  }
}

//二分插入排序 
void bs_insert_sort(vector<int>& nums) {
  int n = nums.size();
  for(int i = 1; i < n; i++) {
    int cur = nums[i];  //待插入元素
    int low = 0, high = i - 1;
    while(low <= high) {
      int mid = low + (high - low) / 2;
      if(nums[mid] <= cur) {
        low = mid + 1;
      } else {
        high = mid - 1;
      }
    }
    //插入位置为high + 1
    for(int j = i - 1; j >= high + 1; j--) {
      nums[j + 1] = nums[j];
    } 
    nums[high + 1] = cur;
  }
}

//希尔排序
void shellpass(vector<int>& nums, int step) {
  int n = nums.size();
  for(int i = step; i < n; i++) {  //从每组的第二个记录开始进行插入排序 
    int cur = nums[i];
    int j = i - step;
    while(j >= 0 && cur < nums[j]) {
      nums[j + step] = nums[j];
      j -= step;
    }
    nums[j + step] = cur;
  } 
}

void shellsort(vector<int>& nums) {
  vector<int> d = {5, 3, 1};
  for(int x : d) {
    shellpass(nums, x);
  }
}

//冒泡 
void bubble_sort(vector<int>& nums) {
  int n = nums.size();
  bool flag = false;
  for(int i = 0; i < n - 1; i++) {
    for(int j = 0; j < n - 1 - i; j++) {
      if(nums[j] > nums[j + 1]) {
        flag = true;
        int t = nums[j];
        nums[j] = nums[j + 1];
        nums[j + 1] = t;
      }
    }
    if(flag) {
      flag = false;
      continue;
    }else {
      return;
    }
  }
}

//快排 
int partition(vector<int>& nums, int low, int high) {
  int cur = nums[low]; //基准
  while(low < high) {
    while(high > low && nums[high] >= cur){
      high--;
    }
    nums[low] = nums[high];
    while(low < high && nums[low] <= cur) {
      low++;
    }
    nums[high] = nums[low];
  }
  nums[low] = cur;
  return low;
}

void q_sort(vector<int>& nums, int low, int high) {
  if(low < high) {
    int loc = partition(nums, low, high);
    q_sort(nums, low, loc - 1);
    q_sort(nums, loc + 1, high);
  }
}

//简单选择排序
void simple_selectsort(vector<int>& nums) {
  int n = nums.size();
  for(int i = 0; i < n - 1; i++) {
    int _min = INT_MAX, k = i + 1;
    for(int j = i; j < n; j++) {
      if(nums[j] < _min) {
        _min = nums[j];
        k = j;
      }
    }
    //将nums[i]与nums[k]交换 
    int t = nums[i];
    nums[i] = nums[k];
    nums[k] = t;
  }
}

//堆排序
void swap(vector<int>& nums, int i, int j) {
  int t = nums[i];
  nums[i] = nums[j];
  nums[j] = t;
}

void adjust(vector<int>& arr, int x, int n) {
  //调整序号为x的元素
  int temp = arr[x];
  //2x+1和2x+2分别是x的左右孩子
  for(int k = 2 * x + 1; k < n; k = 2 * k + 1) {  //调整后指向其左孩子 
    if(k + 1 < n && arr[k] < arr[k + 1]) {
      k++;  //x的右孩子比左孩子更大 
    }
    if(temp < arr[k]) {
      arr[x] = arr[k]; //将x的左右孩子中的较大值赋给x
      x = k; 
    }else {
      break;
    }
  } 
  arr[x] = temp;  //此时要将待排序的点插入 
}

void heapSort(vector<int>& arr) {
  int n = arr.size();
  //先将初始序列建成大根堆, 最后一个非叶子结点的序号为n/2-1(堆顶序号为0) 
  for(int i = n / 2 - 1; i >= 0; i--) {
    adjust(arr, i, n); //调整第i个结点使arr[0...n - 1]成为大根堆 
  } 
  //堆排序
  for(int i = n - 1; i > 0; i--) {
    //将末尾元素与堆顶交换，然后再调整 
    int t = arr[0];
    arr[0] = arr[i];
    arr[i] = t;
    adjust(arr, 0, i);  //调整堆顶使arr[0...i - 1]再次成为大根堆
  } 
}

 
int main() {
  vector<int> nums = {26, 18, 20, 18, 38, 30, 20, 23, 31, 29};
  int n = nums.size();
  heapSort(nums);
  for(int x : nums) {
    cout << x << " ";
  }
  return 0;
}