学数据结构和算法的时候接触到了不少排序算法，在这里整理一下。
涉及到的排序算法有冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序

一、暴力排序（我也不知道叫什么，感觉很暴力就这样叫了）

主要思想是：
将数组的第一个数和接下来的所有数比较，若该数小于第一个数，则他俩交换位置，第一轮遍历交换完就能找出最小的值放在第一位，然后找数组的第二个数和后面的所有数比较，也是交换出在后面的数中最小的（在整个数组中就是第二小的）
依次类推，一直排完整个数组

void ForceSort(vector<int> &arr)
 {
     int temp,len=arr.size();
     for (int i = 0; i < len - 1; ++i)
     {
         for (int j = i + 1; j < len; ++j)
         {
             if (arr[i] > arr[j])
             {
                 temp = arr[j];
                 arr[j] = arr[i];
                 arr[i] = temp;
             }
         }
     }
 }

二、冒泡排序

主要是比较两两相邻的数，如果是左边比右边大，则交换，否则就跳过，每这样从数组的尾到头两两交换一轮，就能选出一个最小值，然后下一轮就不用再管这个最小值了(++i)
下面还使用了一个tag作为标志位，当某轮冒泡从尾到头都已经没有出现过交换，就证明已经排序好了，不用再进行比较了，直接退出循环。就是因为他能用tag作为一种优化，所以在某些不完全乱序的排序任务中，要比上面的暴力排序要好

void BubbleSort(vector<int>& arr)
 {
     int temp, len = arr.size();
     bool tag=true;
     for (int i = 0; (i < len - 1) && tag; ++i)
     {
         tag = false;
         for (int j = len - 1; j >= i+1; --j)//从最后面开始，执行完一次此循环则将最小的数排到了最前面
         {
             if (arr[j] < arr[j - 1])//如果前一个数大于后一个数，就交换位置
             {
                 temp = arr[j - 1];
                 arr[j - 1] = arr[j];
                 arr[j] = temp;
                 tag = true;
             }
         }
     }
 }

三、选择排序

将第一个数和后面的每一个数作比较，找出最小的数的下标（所以每次都需要遍历完才知道谁最小）。找到最小的时候，就交换他俩的位置。这样就选出最小值放在第一位了，然后找重复操作找次小值（++i）。直到排序完成
选择排序的迭代次数其实和暴力排序是一样的，但是选择排序减少了交换次数，不用说每次一比他小就换位置，而是找到最小值才换
（即将交换语句放在了第二个循环的外面）

void SelectSort(vector<int>& arr)
 {
     int temp,min_index, len = arr.size();
     for (int i = 0; i < len - 1; ++i)
     {
         min_index = i;//min_index记录最小值的下标
         for (int j = i + 1; j < len; ++j)
         {
             if (arr[min_index] > arr[j])//进入里面就说明能找到更小的值
             {
                 min_index = j;
             }
         }
         if (min_index != i)//找到了比原本当前位置i更小的值就交换
         {
             temp = arr[min_index];
             arr[min_index] = arr[i];
             arr[i] = temp;
         }
     }
 }

四、插入排序

把每个数和上一个相比，如果这个数小于上一个数就考虑将这个数往前插，至于插到什么位置，就看这个数的大小，他要和前面的每一个数相比，若是小于就一直往前走，直到排在某个比他小的数的后面（然后他后面的数就往后挪位置给他）。（如果比所有数小就排第一了）
这种算法如果倒序比较多的话，其实效率并不比选择算法高，
但如果是完全乱序，这是一种比较快的算法。

void InsertSort(vector<int>& arr)
 {
     int temp,j, len = arr.size();
     for (int i = 1; i < len; ++i)
     {
         if (arr[i] < arr[i - 1])
         {
             temp = arr[i];
             for (j = i-1; arr[j]>temp; --j)
             {
                 arr[j+1] = arr[j];
                 if (j == 0)
                 {
                     --j;
                     break;
                 }
             }
             arr[j+1] = temp;
         }
     }
 }

五、希尔排序

插入排序的升级版，插入排序是每次和他上一个比较，
希尔排序是第一轮和他前gap个比较，就是把arr[i]和arr[i-gap]每两个数当成一组插入排序，进行排序。(一共有gap组)
第二轮是gap缩小一倍，把arr[i-gap]，arr[i]，arr[i+gap]，arr[i+2*gap]每四个数当成一组插入排序。（一共有gap组）
…
依次类推
一般来讲只要理解了插入排序，然后再插入排序的基础上加个外循环，再把原本的间隔1，改成gap即可

void HillSort(vector<int>& arr)
 {
     int temp, j, len = arr.size(),gap;
     gap = len;
     do
     {
          gap = gap/2;
          for (int i = gap; i < len; i+=gap)
          {
               if (arr[i] < arr[i - gap])
               {
                    temp = arr[i];
                    for (j = i - gap; arr[j] > temp; j-=gap)
                    {
                         arr[j + gap] = arr[j];
                         if (j == 0)
                         {
                             j-=gap;
                             break; 
                          }
                    }
                    arr[j + gap] = temp;
                }
          }
     } while (gap > 1);
 }

六、归并排序

主要思想是先将n长的数组无限二分，直到每份都只有两个数，然后将这两个数排序，重新回退到上一层（每份只有四个数的时候）再进行排序，在原来两个两个已有顺序的基础上，这是比较好排序的，排完后又回退到上一层
依次类推
用递归的思想比较好实现，但递归有点影响效率了

void merging(vector<int>::iterator begin1, vector::iterator<int> end1, vector::iterator<int> begin2, vector::iterator<int> end2)
 {
     auto t1 = begin1, t2 = begin2;
     vector t3;
     while (end1 > t1&& end2 > t2)
     {
         if (*t1 < *t2)
         {
              t3.push_back(t1);
              ++t1;
         }
         else
         {
             t3.push_back(t2);
             ++t2;
         }
     }
     while (t1 < end1)
     {
         t3.push_back(t1);
         ++t1;
     }
     while (t2 < end1)
     {
         t3.push_back(t2);
         ++t2;
     }
     t1 = begin1;
     for (int i = 0; i < t3.size(); ++i)
     {
         *t1 = t3[i];
         ++t1;
     }
 }
void MeregeSort(vector<int>::iterator begin, vector<int>::iterator end)
 {
     if (end-begin > 1)
     {
         auto new_begin1 = begin;
         auto new_end1 = begin+(end- begin)/2;
         auto new_begin2 = begin + (end - begin) / 2 ;
         auto new_end2 = end;
         MeregeSort(new_begin1, new_end1);
         MeregeSort(new_begin2, new_end2);
         merging(new_begin1, new_end1, new_begin2, new_end2);
     }
 }

七、堆排序

是简单选择排序的升级版。
可以理解为数组是按完全二叉树层叠排列的，从最右下小二叉树起，将三个数选出最大的一个排到根的位置。继续从右到左从上到下依次执行，执行完后，根部的位置即当前最大值（即数组里第0位）。然后将这个最大值放到完全二叉树最末位，（数组里最后一位），然后再依次类推选出第二大，第三大。。。最终完成排序。

void SwapTheMax(vector<int>& arr, int i, int len)
 {
     int max_index = i;
     if (2 * i + 1 < len && arr[max_index] < arr[i * 2 + 1])
         max_index = 2 * i + 1;
     if (2 * i + 2 < len && arr[max_index] < arr[i * 2 + 2])
         max_index = 2 * i + 2;
     if (max_index != i)
     {
         int temp = arr[i];
         arr[i] = arr[max_index];
         arr[max_index] = temp;
         SwapTheMax(arr, max_index, len);
     }
 }
 void HeapSort(vector<int>& arr)
 {
     int len = arr.size();
     while (len > 1)
     {
         //初始化堆
         for (int i = len / 2 - 1; i >= 0; --i)
         {
             SwapTheMax(arr, i, len);
         }
         int temp = arr[0];
         arr[0] = arr[len - 1];
         arr[len - 1] = temp;
         //交换堆顶和当前最后一个的位置
         --len;
     }
 }

八、快速排序

是一种冒泡算法的升级版！
每次取一个数组中的（当前第一位）一个数作为基准点，然后把数组里大于他的数放在右边，小于它的数放在左边，把左边和右边又看成是一个数组，进行递归操作。当数组里递归到只剩一个数的时候就返回。最终就能实现一个排序效果。

int CalculatePoint(vector<int>::iterator begin, vector<int>::iterator end)
 {
     int point = begin;
     auto e = end-1, b = begin;
     while (e - b > 0)
     {
         while (b < e)
         {
             if (e < point)
             {
                 int temp = *e;
                 *e = point;
                 b = temp;
                 break;
             }
             --e;
         }
         while (b < e)
         {
             if (b > point)
             {
                 int temp = *b;
                 *b = point;
                 *e = temp;
                 break;
             }
             ++b;
         }
     }
     return (b - begin);
 }
void QuickSort(vector<int>::iterator begin, vector<int>::iterator end)
 {
     if (end - begin > 1)
     {
         int point = CalculatePoint(begin, end);
         QuickSort(begin, begin + point+1);
         QuickSort(begin + point+1, end);
     }
 }

开始测评

生成999个测试数据

各排序算法耗时

换了组数据再测

结论：
一些简单的排序比如冒泡排序暴力排序速度是比较慢的，选择排序的速度也不快，插入排序简单但是速度还算快，改进后的希尔排序有一定提升。归并排序用了递归，实测起来反而速度慢了，快速排序就算用了递归速度也很快（快速排序牛逼！）

最后一句话总结：
有STL库的sort在，写个屁的排序，溜了溜了