排序算法

性质

稳定性

稳定性是指相等的元素经过排序之后的相对顺序是否发生了改变。拥有稳定性这一特性的算法会让原本相等键值的记录维持相对次序不变。如果一个排序算法是稳定的，那么对相等键值的数据R和S，如果R出现在S之前，那么在排序过的列表中R也会在S之前
稳定排序：基数排序、计数排序、冒泡排序、归并排序
非稳定排序：选择排序、堆排序、快速排序和希尔排序

选择排序

遍历列表，每次都和当前最小（最大）的元素进行交换

void selection_sort(vector<int> v)
{
  int n = v.size();
  int total = 0;
  for (int i = 0; i < n - 1; i++)
  {
    int minIndex = i;
    for (int j = i + 1; j < n; j++)
    {
      if (v[j] < v[minIndex])
      {
        total++;
        minIndex = j;
      }
    }
    swap(v[i], v[minIndex]);
  }
  cout << "***************选择排序...****************" << endl;
  for (auto &item : v)
  {
    cout << item << " ";
  }
  cout << endl;
  cout << "总共比较次数为：" << total << endl;
}

冒泡排序

每次都将邻近的两个元素进行比较，并按照规则进行交换 另外，一般来说是要对每一个元素都进行遍历，并交换，但在最坏的情况下：比如序列原本就已经升序，那么我们就不需要再重复循环，优化后的代码如下：

void bubble_sort(vector<int> v)
{
  int n = v.size();
  int total = 0;
  bool flag = true;
  while (flag)
  {
    flag = false;
    for (int i = 0; i < n - 1; i++)
    {
      if (v[i] > v[i + 1])
      {
        flag = true;
        swap(v[i], v[i + 1]);
        total++;
      }
    }
  }
  cout << "***************冒泡排序...****************" << endl;
  for (auto &item : v)
  {
    cout << item << " ";
  }
  cout << endl;
  cout << "总共比较次数为：" << total << endl;
}

插入排序

void insert_sort(vector<int> v)
{
  int n = v.size();
  int total = 0;
  for (int i = 1; i < n; i++)
  {
    int temp = v[i];
    int j = i - 1;
    while (j >= 0 && v[j] > temp)
    {
      v[j + 1] = v[j];
      j--;
      total++;
    }
    v[j + 1] = temp;
  }
  cout << "***************插入排序...****************" << endl;
  for (auto &item : v)
  {
    cout << item << " ";
  }
  cout << endl;
  cout << "总共比较次数为：" << total << endl;
}

快速排序

找出一个基准数m，其左边的数全部小于m，右边的数全部大于m

void quick_sort(vector<int> v)
{
  function<void(vector<int> &, int, int)> quick_sort_oper = [&](vector<int> &v, int left, int right)
  {
    if (left >= right)
    {
      return;
    }
    int i = left;
    int j = right;
    int key = v[left];
    while (i < j)
    {
      while (i < j && v[j] >= key)
      {
        j--;
      }
      while (i < j && v[i] <= key)
      {
        i++;
      }
      swap(v[i], v[j]);
    }
    swap(v[left], v[i]);
    quick_sort_oper(v, left, i - 1);
    quick_sort_oper(v, i + 1, right);
  };
  quick_sort_oper(v, 0, v.size() - 1);
  for (auto &item : v)
  {
    cout << item << " ";
  }
  cout << endl;
}

桶排序

用一个静态长度的数组来模拟一个桶，如果输入的列表中存在这个数，那么就在对应桶中放入一个数 最后再遍历每一个桶，由于遍历的时候是按照下标顺序（下标顺序其实就是每一个数的顺序），从而可以实现排序 这种排序方式很快，但是很耗费空间（数据量多大，就要开多大的空间）

void bucket_sort(vector<int> v)
{
  int n = v.size();
  vector<int> bucket(10001, 0);
  int maxEle = *max_element(v.begin(), v.end());
  for (int i = 0; i < v.size(); i++)
  {
    bucket[v[i]]++;
  }
  for (int i = 0; i < maxEle; i++)
  {
    if (bucket[i] != 0)
    {
      cout << i << " ";
    }
  }
}