排序算法的稳定性：所有相等的数经过某种排序方法后，仍能保持它们在排序前的相对次序，我们称这种排序算法是稳定的。反之，就是非稳定算法。
内排序：在排序过程中，所有需要排序的数都在内存，并在内存中调整它们的顺序，称为内排序。
外排序：在排序过程中，只有部分数被调入内存，并借助内存调整数在外存中的相对顺序，称为外排序。

1、插入排序

分三个步骤：

  • 在在A[1..i-1]中查找A[i]的插入位置，A[1..j].key <= A[i].key < A[j+1..i-1].key;
  • 将A[j+1..i-1]中的所有记录均后移一个位置;
  • 将A[i]插入(复制)到A[j+1]的位置上。
    1
    2
    3
    4
    5
    6
    template<typename E,typename Comp>
    void inssort(E A[],int n){
      for(int i = 1;i <= n;i ++)
        for(int j = i;(j>0) && (Comp::prior(A[j],A[j-1]);j --))//如果A[j]>A[j-1],交换
          swap(A[j],A[j-1]);
    }
2、冒泡排序

1
2
3
4
5
6
7
8
9
10
11
template<typename E,typename Comp>
void bubsort(E A[],int n){
  int flag;//标记此次冒泡过程中是否交换了元素，没有的话说明元素已经有序，终止
  for(int i = 0;i < n - 1;i ++){
    flag = false;
    for(j = n - 1;j > i;j --)//从后向前冒泡，从前往后也一样
      if(Comp::prior(A[j],A[j-1]))//如果A[j]>A[j-1]
      {swap(A,j,j-1);flag = True;}
    if(!flag) return;
  }
}
3、选择排序


假设当前下标为最小值的下标，向后遍历，一直更新最小值的下标，找到尽头，交换最小值和当前值。更新当前下标，持续上述，直至当前下标为最后一个元素下标。
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面，或者将最大值放在最后面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择，每一趟从前往后查找出无序区最小值，将最小值交换至无序区最前面的位置。

1
2
3
4
5
6
7
8
9
10
11
template<typename T>
void selection_sort(T arr[],int len){
  int i,j,min;
  for(int i = 0;i < len - 1;i ++){
    min = i;
    for(j = i + 1;j < len;j ++)
      if(arr[min] > arr[j])
        min = j;
      swap(arr[i],arr[min]);
  }
}