冒泡排序_框架

冒泡排序(Bubble-sort)是一种简单的排序算法。它重复地遍历要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。遍历数列的工作重复地进行直到没有元素再需要交换，此时该数列已经排序完成。

void bubblesort()
{
  for(int i = n; i > 1; i--)
  {
    bool f = true;
    for(int j = 1; j < i; j++)
    {
      if(a[j] > a[j + 1])
      {
        swap(a[j], a[j + 1]);
        f = false;
      }
    }
    if(f) break;
  }
}

选择排序_框架

选择排序(Select-sort)是一种简单直观的排序算法，应该是初学者最容易想到的解决方法之一。

它的工作原理是：首先在无序序列中找到最大元素，存放到无序序列的结束位置，变为有序序列。然后再从剩余无序序列中继续寻找最大元素，然后放到无序序列的末尾。重复此过程，直到所有元素均排序完毕。

void selectsort()
{
  for(int i = n; i > 1; i--)
  {
    int mx = 1;
    for(int j = 2; j >= i; j++)
      if(a[j] > a[mx])
        mx = j;
    if(i != mx)
      swap(a[i], a[mx]);
  }
}

插入排序_框架

插入排序（Insert-Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

void insertsort()
{
  for(int i = 2; i <= n; i++)
    for(int j = i; j > 1; j--)
      if(a[j] < a[j - 1])
        swap(a[j], a[j - 1]);
}

计数排序_框架

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法。 当然这是一种牺牲空间换取时间的做法，而且当O(k)＞O(n* log(n))的时候其效率反而不如基于比较的排序（基于比较的排序的时间复杂度在理论上的下限是O(n* log(n)), 如归并排序，堆排序）

int countingArr[M];
void countingsort()
{
  for(int i = 1; i <= n; i++)
    
    countingArr[a[i]]++;
  for(int i = 1, j = 0; j < M; j++)
    for(int k = 0; k < countingArr[j]; k++)
      a[i++] = j;
}