排序概念

数据表：待排序数据元素的有很集合

排序码：通常数据元素有多个个属性域，即多少个数据成员组成，其中有一个属性域可用来区分元素，作为排序依据。

稳定性：2个元素R1,R2,它们的排序码K1=k2，在排序前R1在R2前，排序后R1仍在R2之前，则称这个排序方法是稳定的。

内部排序：在排序期间数据元素全部存放在内存的排序。

外部排序：在排序期间全部元素个数太多，不能同时存放内存，必须根据排序过程的要求，不断在内，外存之间移动的排序

直接插入排序:稳定

#include<iostream>
using namespace std;

/*
  如果当前值大于前一个数，那么，前面的数向后移动，直
  到当前值找到合适的插入位置为止
  */
void insertSort(int *a,int size){
    int j,temp;
    for(int i=1;i<size;i++){
        if(a[i]<a[i-1]){
            temp = a[i];
            j = i;
            do{
                a[j]=a[j-1];
                j--;
            }while(a[j]>temp&&j>0);
            a[j+1] = temp;
        }
    }
}

int main(){
    int a[] = {1,3,2,5,6,4,9,10,8,7};
    insertSort(a,10);
    for(int i=0;i<10;++i)
        cout << a[i] << " ";
}
1 2 3 4 5 6 7 8 9 10

希尔排序:不稳定

#include<iostream>
using namespace std;

void shellSort(int *a,int left,int right){
    int i,j,gap = right-left+1;
    int temp;
    do{
        gap = gap/3+1;
        for(i=left+gap;i<=right;i++){
            if(a[i]<a[i-gap]){
                temp = a[i];
                j = i-gap;
                do{
                    a[j+gap] = a[j];
                    j = j-gap;
                }while(j>=left&&temp<a[j]);
                a[j+gap] = temp;
            }
        }
    }while(gap>1);
}

int main()
{
    int a[] = {1,3,2,5,6,4,9,10,8,7};
    shellSort(a,0,9);
    for(int i=0;i<10;++i)
        cout << a[i] << " ";
}

1 2 3 4 5 6 7 8 9 10 

O（n*n)：
直接插入，冒泡，直接选择
O（nlogn):
快速：用的最多
堆：平均性能不如快速
归并：稳定，但需附加O(n)内存空间