经典排序算法

经典排序算法

上图是经典排序算法的效率图，大致敲了一遍，堆排序、希尔排序、归并排序，思想真的很巧妙，关键还是看思路。

代码如下：

#ifndef __SORT_H__
#define __SORT_H__

#include <vector>
#include <algorithm>

using namespace std;

/** 
 * @file sort.h 
 * 
 * This is an sort algorithm header file, implement 10 main sorting algorithm
 * 
 * Created by yejy on 2019-03-22 22:02:04
 * Copyright (c) yejy. all rights reserved
 * 
 */

class CSoultion
{

public:

  /**
   * @brief 冒泡排序 
   *
   * @author yejy
   * @data 2019-03-22
   *
   * @性能：(交换排序; 时间平均:N^2 , 最坏:N^2 , 最好:N; 空间1; 稳定)
   *
   */
  void BubbleSort(vector<int> &vec)
  {
    int iSize = vec.size();
    bool flag = true;
    for (int i = 0; i < iSize - 1; i++)
    {
      for (int j = 0; j < iSize - i - 1; j++)
      {
        if (vec[j] > vec[j + 1])
        {
          swap(vec[j], vec[j + 1]);
          flag = false;
        }
      }

      if (flag)
      {
        break;
      }
    }
  }

  /**
   * @brief 选择排序
   *
   * @author yejy
   * @data 2019-03-22
   *
   * @性能：(选择排序;时间平均:N^2 , 最坏:N^2 , 最好:N^2 ; 空间1; 稳定)
   *
   */
  void SelectionSort(vector<int> &vec)
  {
    int iSize = vec.size();
    for (int i = 0; i < iSize - 1; i++)
    {
      for (int j = i + 1; j < iSize; j++)
      {
        if (vec[j] < vec[i])
        {
          swap(vec[j], vec[i]);
        }
      }
    }
  }

  /**
   * @brief 快速排序
   * 
   * @author yejy
   * @data 2019-03-22
   *
   * @性能：(交换排序;时间平均:NlogN, 最坏:N^2 , 最好:NlogN ; 空间logN; 不稳定)
   *
   */
  void QuickSort(vector<int> &vec, int iLow, int iHigh)
  {
    if (iLow >= iHigh)
    {
      return;
    }

    int i = iLow;
    int j = iHigh;
    int key = vec[iLow]; // 第一个值作为基准

    while (i < j)
    {
      while (vec[j] >= key && i < j)
      {
        j--;
      }

      if (i < j)
      {
        swap(vec[i], vec[j]);
      }

      while (vec[i] <= key && i < j)
      {
        i++;
      }

      if (i < j)
      {
        swap(vec[i], vec[j]);
      }
    }

    QuickSort(vec, iLow, i - 1);
    QuickSort(vec, i + 1, iHigh);
  }

  /**
   * @brief 插入排序
   *
   * @author yejy
   * @data 2019-03-22
   *
   * @性能：(插入排序;时间A:N^2 , B:N^2 , E:N;空间1;稳定)
   *
   */
  void InsertionSort(vector<int> &vec)
  {
    int iSize = vec.size();
    int iPreIndex; // 前面 index
    int iCurr;     // 当前值

    for (int i = 0; i < vec.size() - 1; i++)
    {
      iCurr = vec[i + 1];
      iPreIndex = i;

      while (iPreIndex >= 0 && vec[iPreIndex] > iCurr)
      {
        vec[iPreIndex + 1] = vec[iPreIndex];
        iPreIndex--;
      }

      vec[iPreIndex + 1] = iCurr;
    }
  }

  /**
   * @brief 希尔排序
   *
   * @author yejy
   * @data 2019-03-22
   *
   * @性能：(希尔排序;时间A:N 1.3次方 , B:N^2 , E:N;空间1;不稳定)
   *
   */
  void ShellSort(vector<int> &vec)
  {
    int iSize = vec.size();
    int iPreIndex;
    int iCurr;
    // 先做宽间隔排序，使得序列大致有序，最后再做插入排序
    for (int iGap = iSize / 2; iGap > 0; iGap = iGap / 2)
    {
      for (int i = 0; i < iSize - iGap; i += iGap)
      {
        iCurr = vec[i + iGap];
        iPreIndex = i;

        while (iPreIndex >= 0 && vec[iPreIndex] > iCurr)
        {
          vec[iPreIndex + iGap] = vec[iPreIndex];
          iPreIndex -= iGap;
        }

        vec[iPreIndex + iGap] = iCurr;
      }
    }
  }

  /**
   * @brief 归并排序
   *
   * @author yejy
   * @data 2019-03-22
   *
   * @性能：(归并排序;时间A:NlogN , B:NlogN , E:NlogN;空间N;稳定)
   *
   */
  void MergeSort(vector<int> &vec, vector<int> &vecTemp, int iLow, int iHigh)
  {
    if (iLow >= iHigh)
    {
      return;
    }

    int iMid = (iLow + iHigh) / 2;

    MergeSort(vec, vecTemp, iLow, iMid);
    MergeSort(vec, vecTemp, iMid + 1, iHigh);

    Merge(vec, vecTemp, iLow, iMid, iHigh);
  }

  void Merge(vector<int> &vec, vector<int> &vecTemp, int iLow, int iMid, int iHigh)
  {
    int iLeft = iLow;      // 左序列
    int iRight = iMid + 1; // 右序列
    int t = 0;             // 临时数组下标

    while (iLeft <= iMid && iRight <= iHigh)
    {
      if (vec[iLeft] <= vec[iRight])
      {
        vecTemp[t++] = vec[iLeft++];
      }
      else
      {
        vecTemp[t++] = vec[iRight++];
      }
    }

    while (iLeft <= iMid)
    {
      vecTemp[t++] = vec[iLeft++];
    }

    while (iRight <= iHigh)
    {
      vecTemp[t++] = vec[iRight++];
    }

    t = 0;

    while (iLow <= iHigh)
    {
      vec[iLow++] = vecTemp[t++];
    }
  }

  /**
   * @brief 堆排序
   *
   * @author yejy
   * @data 2019-03-22
   *
   * @性能：(堆排序;时间A:NlogN , B:NlogN , E:NlogN;空间1;不稳定)
   */
  void HeapSort(vector<int> &vec)
  {
    // 构造大顶堆
    BuildMaxHeap(vec);

    for (int i = vec.size() - 1; i > 0; i--)
    {
      swap(vec[0], vec[i]);  // 将最大值替换至末尾
      AdjustHeap(vec, 0, i); // 调整大顶堆
    }
  }

  void BuildMaxHeap(vector<int> &vec)
  {
    for (int i = vec.size() / 2 - 1; i >= 0; i--)
    {
      AdjustHeap(vec, i, vec.size());
    }
  }

  void AdjustHeap(vector<int> &vec, int i, int iLength)
  {
    int iLeft = 2 * i + 1;
    int iRight = 2 * i + 2;
    int iLargest = i;

    if (iLeft < iLength && vec[iLeft] > vec[iLargest])
    {
      iLargest = iLeft;
    }

    if (iRight < iLength && vec[iRight] > vec[iLargest])
    {
      iLargest = iRight;
    }

    if (iLargest != i)
    {
      swap(vec[iLargest], vec[i]);
      AdjustHeap(vec, iLargest, iLength);
    }
  }
};

#endif

测试代码：

#include "sort.h"
#include <iostream>

int main()
{
  CSoultion soultion;
  vector<int> vec;

  cout << "please input you need sort num: " << endl;
  int i;

  while (1)
  {
    cin >> i;
    if (i == 0)
    {
      break;
    }
    vec.push_back(i);
  }

  cout << "bubble sort begin: " << endl;
  vector<int> vecTemp = vec;
  soultion.BubbleSort(vecTemp);
  auto function = [&]() { for(auto elem : vecTemp){ cout << " " << elem;} }; // 使用 lambda 引用捕获打印
  function();
  cout << endl;

  cout << "selection sort begin: " << endl;
  vecTemp.clear();
  vecTemp = vec;
  soultion.SelectionSort(vecTemp);
  function();
  cout << endl;

  cout << "quick sort begin: " << endl;
  vecTemp.clear();
  vecTemp = vec;
  soultion.QuickSort(vecTemp, 0, vecTemp.size() - 1);
  function();
  cout << endl;

  cout << "insert sort begin: " << endl;
  vecTemp.clear();
  vecTemp = vec;
  soultion.InsertionSort(vecTemp);
  function();
  cout << endl;

  cout << "shell sort begin: " << endl;
  vecTemp.clear();
  vecTemp = vec;
  soultion.ShellSort(vecTemp);
  function();
  cout << endl;

  cout << "merge sort begin: " << endl;
  vecTemp.clear();
  vecTemp = vec;
  vector<int> vecContain = vec;
  vecContain.clear();
  soultion.MergeSort(vecTemp, vecContain, 0, vecTemp.size() - 1);
  function();
  cout << endl;

  cout << "heap sort begin: " << endl;
  vecTemp.clear();
  vecTemp = vec;
  soultion.HeapSort(vecTemp);
  function();
  cout << endl;

  return 0;
}

手动随机输入一组数字，过一遍用例，打印结果如下：

-bash-4.2$ valgrind ./a.out                  
==4743== Memcheck, a memory error detector
==4743== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==4743== Using Valgrind-3.14.0 and LibVEX; rerun with -h for copyright info
==4743== Command: ./a.out
==4743== 
please input you need sort num: 
77
44
55
99
11
2
6
3
7
88
99
11
0
bubble sort begin: 
 2 3 6 7 11 11 44 55 77 88 99 99
selection sort begin: 
 2 3 6 7 11 11 44 55 77 88 99 99
quick sort begin: 
 2 3 6 7 11 11 44 55 77 88 99 99
insert sort begin: 
 2 3 6 7 11 11 44 55 77 88 99 99
shell sort begin: 
 2 3 6 7 11 11 44 55 77 88 99 99
merge sort begin: 
 2 3 6 7 11 11 44 55 77 88 99 99
heap sort begin: 
 2 3 6 7 11 11 44 55 77 88 99 99
==4743== 
==4743== HEAP SUMMARY:
==4743==     in use at exit: 0 bytes in 0 blocks
==4743==   total heap usage: 7 allocs, 7 frees, 220 bytes allocated
==4743== 
==4743== All heap blocks were freed -- no leaks are possible
==4743== 
==4743== For counts of detected and suppressed errors, rerun with: -v
==4743== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
-bash-4.2$