平方级的排序算法

插入排序

每次选择一个元素K插入到之前已排好序的部分A[1…i]中，由后向前移动元素直到找到一个合适的位置。
插入排序是稳定的（相等的时候表示找到合适位置了，就不需要再移动元素了）。

void InsertSort(RecType R[], int n){
    int i, j;
    RecType temp;
    for(i = 1; i<n; ++i){
        temp = R[i];
        j = i - 1;//从后往前找到一个合适的位置
        while(j >= 0 && temp.key < R[j].key){
            R[j + 1] = R[j];
            j--;
        }
        R[j + 1] = temp;//将元素放置到该合适位置
    }
}

冒泡排序

通过交换元素，使关键字最大的记录如气泡一般逐渐往上“漂浮”直至“水面”。

排序过程中只交换相邻两个元素的位置。因此，当两个数相等时，是没必要交换两个数的位置的。所以，它们的相对位置并没有改变，冒泡排序算法是稳定的

void BubbleSort(RecType R[], int n){
    int i, j;
    RecType temp;
    for(i=0; i<n-1; i++){//每个元素
        bool flag = false;
        for(j=n-1;j > i; j--){//对每个元素进行冒泡
             if(R[j].key < R[j - 1].key){
                 temp = R[j];
                 R[j] = R[j - 1];
                 R[j - 1] = temp;
                 flag = true;
            }
            if(!flag){//如果没有交换，说明已经有序了
                return;
            }
        }
   }
} 

选择排序

搜索无序数组，找到当前最小的元素，并与无序数组首元素交换，缩小整个无序数组，并重复操作。直到整个数组有序。
由于每次都是选取未排序序列A中的最小元素x与A中的第一个元素交换，因此跨距离了，很可能破坏了元素间的相对位置，因此选择排序是不稳定的！

void SelectSort(RecType R[], int n){
    int i, j, k;
    RecType temp;
    for(i = 0; i < n - 1; ++i){
        k = i;
       //便利无序数组，找到最小的元素
        for(j = i + 1; j < n; j++){
            if(R[j].key < R[k].key){
                k = j;
            }
        }
        if(k != i){
           swap(R[i], R[k]);
        }
}

希尔排序

思想：希尔排序也是一种插入排序方法,实际上是一种分组插入方法。先取定一个小于n的整数d1作为第一个增量,把表的全部记录分成d1个组,所有距离为d1的倍数的记录放在同一个组中,在各组内进行直接插入排序；然后,取第二个增量d2(＜d1),重复上述的分组和排序,直至所取的增量dt=1(dt<dt-1<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
希尔排序时间复杂度平均为O(nlogn)