排序

排序是将表中的元素重排列为有序的过程

基于排序发生的位置可以分为:

内部排列
外部排列

其中内部排列是发生在内存中的排序算法，外部排序是发生在内存内部与内存与存储间的IO的整体排序算法。

内部排序

内部排序分为

插入排序
交换排序
选择排序
归并排序
基数排序

排序的实现基本都基于两个操作: 比较、移动

排序的稳定性

关键词存在重复时，如果排序算法可能改变关键词相对位置，则称其为不稳定的排序

插入排序

插入排序遍历表，将表分为待遍历段和已插入段，将遍历后的元素向前向前遍历比较大小后插入。

通常设置 $A[0] = A[i]$ ,作为”哨兵“防止向前遍历越界

void InsertSort(ElemType A[],int n){
    int i , j;
    for (i = 2 ; i <= n ; i++){
        A[0] = A[i];
        for (j = i-1; A[0] < A[j]; --k){
            A[j+1] = A[j];
        }
        A[j+1] = A[0];
    }
}

插入排序的时间复杂度会随着表结构而改变。当目标排序表已经有序，元素只需要逐个比较，不需要移动，因此时间复杂度为 $\mathcal{O}(n)$ . 当表处于完全逆序的情况下，每一个元素都需要向前移动前方的整个表，因此时间复杂度为 $\mathcal{O}(n^2)$ .

平均情况下的时间复杂度也为 $\mathcal{O}(n^2)$

折半插入排序

折半插入排序将向前顺序查找改为了插入段的二分查找

void BInsertSort(ElemType A[],int n){
    int i,j;
    int low, mid, high;
    for(i = 2; i < n ; i++){
        A[0] = A[i];
        while(low <= high){
            mid = (low + high)/2;
            if (A[mid]>A[0]){
                high = mid - 1;
            }
            else {
                low = mid + 1;
            }
        }
        for (j = i - 1; j >= high +1; --j){
            A[j+1] = A[i];
        }
        A[high+1] = A[0];
    }
}

折半比较搜索只优化了比较过程，但是没有优化插入的过程。整体比较过程的时间复杂度为 $\mathcal{O}(n\log_2 n)$ , 总体的时间复杂度仍为 $\mathcal{O}(n^2)$

希尔排序

希尔排序将表分为等间距的子序列进行排序，再进行多次插入排序。相当于对下标模 $d_i$ 等价类内部进行排序。

希尔排序的时间复杂度也依赖于所选序列，最好的情况约为 $\mathcal{O}(n^{1.3})$ ，最坏为 $\mathcal{O}(n^2)$

希尔排序是不稳定排序

void ShellSort(ElemType A[],int n, int mod[]){
    int i,j;
    for (int r = 0; r < sizeof(mod); r++){
        int d = mod[r];
        for (i = 1; i < n-d+1 ; i++){
            for(int k = 1; k < n /3 ; K++){
                j = d * k + i;
                A
            }
        }
    }
    
}

数据结构算法