排序

排序

排序算法的稳定性:若待排序表中又两个元素$R_i$和$R_j$，其对应的关键字相同即$key_i = key_j$，且在排序前$R_i$在$R_j$前面，若使用某一排序算法排序后，$R_i$仍然在$R_j$前面，则称这个排序算法是稳定的，否则称排序算法为不稳定的。

排序过程中，根据数据元素是否完全在内存中，讲排序算法分为两类:

• 内部排序，排序期间元素全部存放在内存中的排序。
• 外部排序，排序期间元素无法同时存放在内存中，必须在排序的过程中根据要求不断的在内、外存之间移动。

插入排序

假设表为$L[1...n]$，其中$A[0]$为哨兵。

思想:每次将一个待排序的记录按其关键字大小插入前面已经排好序的子序列，直到全部记录插入完成。

由插入排序的思想可以引申出:直接插入排序、折半插入排序、希尔排序。

直接插入排序

分析:

• 空间复杂度:$O(1)$。
• 时间复杂度:最好情况下为$O(n)$，最坏情况下，总的比较次数为$\sum_{i=2}^{n}i$，总的移动次数为$\sum_{i=2}^{n}i+1$，时间复杂度为$O(n^2)$。
• 稳定性:稳定。
• 适用型:顺序存储和链式存储的线性表。

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

折半插入排序

分析:

• 时间复杂度:比较次数为$O(n\log_2{n})$，而移动次数并未改变，因此时间复杂度仍为$O(n^2)$。
• 比较元素的次数$O(n\log_2{n})$。

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

希尔排序

思想:先将待排序表分割成若干形如$L[i,i+d,i+2d,...,i+kd]$的特殊子表，对各个子表分别进行直接插入排序，缩小增量d，重复上述过程，直到$d=1$为止。

分析:

• 空间复杂度:$O(1)$，
• 时间复杂度:当n在某个特定范围时，时间复杂度为$n^{1.3}$；最坏的时间复杂度为$O(n^2)$。
• 稳定性:由于相同关键字可能被划分到不同子表，可能改变相对次序，因此不稳定。
• 适用性:仅适用于线性表为顺序存储的情况。

void shellsort(ElemType A[], int n)
{
    int dk, i, j;
    for(dk=n/2;dk>=1;dk=dk/2)
    {
        for(i=dk+1;i<=n;i++)
        {
            if(A[i]<A[i-dk])
            {
                A[0] = A[i];
                for(j=i-dk;j>0&&A[0]<A[j];j-=dk)
                    A[j+dk] = A[j];
                A[j+dk] = A[0];
            }
        }
    }
}

交换排序

假设表为$L[0...n]$。

冒泡排序

思想:从后往前(从前往后)两两比较相邻元素的值，若为逆序则交换他们，直到序列比较完。并称其为第一躺冒泡，结果将最小的元素交换到待排序序列的第一个位置上。这样做最多$n-1$次冒泡即可将元素排好序。

分析:

• 空间复杂度:$O(1)$
• 时间复杂度:最好情况下，一次比较发现没有元素有序，比较次数为$n-1$，此时为$O(n)$；若元素逆序，则进行$n-1$次排序，第$i$次排序需要进行$n-i$次关键字的比较，而且每次比较后都要移动元素$3$次来交换位置(或者以位运算的方式交换)，此时$\text{比较次数}=\sum_{i=1}^{n-1}(n-i)=\frac{n(n-1)}{2}$，$\text{移动次数}=\sum_{i=1}^{n-1}3(n-i)=\frac{3n(n-1)}{2}$.因此最坏时间复杂度为$O(n^2)$，平均时间复杂度为$O(n^2)$。
• 稳定性:稳定。
• 适用型:顺序存储和链式存储的线性表。

void BubbleSort(ElemType A[], int n)
{
    int flag = false;
    for(int i=0;i<n-1;i++)
    {
        for(int j=n-1;j>i;j--)
        {
            if(A[j]<A[j-1])
            {
                swap(A[i-1],A[i]);
                flag = true;
            }
        }
        if(!flag)
            return;
    }
}

快速排序

思想:基于分治法，在待排序表$L[0...n]$中任取一个元素pivot作为枢轴(或基准，通常取首元素)，通过一趟排序将待排序表划分为独立的两部分$L[0...k-1]$和$L[k+1...n]$，使得$L[0...k-1]$中所有元素小于pivot，$L[k+1...n]$中所有元素大于等于pivot，则pivot放在了其最终位置L[k]上，这个过程被称为一趟快速排序，然后分别递归的两个子表重复上述过程，直至每个部分内只有一个元素或空为止，即所有元素放在了其最终位置上。

分析:

• 空间复杂度:O(递归层数)，最好空间复杂度$O(\log_{2}n)$，最坏空间复杂度$O(n)$。
• 时间复杂度:O(n*递归层数)，最好时间复杂度$O(n\log_{2}n)$，最坏时间复杂度$O(n^2)$，平均时间复杂度$O(n\log_{2}n)$。
• 稳定性:不稳定

void Partition(ElemType A[], int low, int high)
{
    ElemType pivot = A[low];
    while(low < high)
    {
        while(low<high && A[high]>=pivot)
            --high;
        A[low] = A[high];
        while(low<high && A[low]<=pivot)
            ++low;
        A[high] = A[low];
    }
    A[low] = pivot;
    return low;
}

void QuickSort(ElemType A[], int low, int high)
{
    if(low < high)
    {
        int pivotpos = Partition(A, low, high);
        QuickSort(A, low, pivotpos-1);
        QuickSort(A, pivotpos+1, high);
    }
}

选择排序

简单选择排序

假设表为$L[0...n]。

思想:每一次在待排元素中选取关键字最小的元素加入有序子序列。

分析:

• 空间复杂度:$O(1)$
• 时间复杂度:$O(n^2)$
• 适用型:顺序存储和链式存储的线性表。

void SelectSort(ElemType A[], int n)
{
    int i, j, min;
    for(i=0;i<n-1;i++)
    {
        min = i;
        for(j=i+1;j<n;j++)
        {
            if(A[j]<A[min])
            {
                min = j;
            }
        }
        if(min != i)
            swap(A[i],A[min]);
    }
}

堆排序

假设表为$L[1...n]$，其中$A[0]$为哨兵。

分析: 一个结点下坠一层，最多只需要对比关键字$2$次。若树高为$h$时，某结点的高度为$i$，则这个结点最多下坠$h-i$层，关键字对比次数不超过$2(h-i)$。$n$个结点的完全二叉树树高$h=\lfloor\log_2n\rfloor+1$，第$i$层，最多有$2^{i-1}$个结点，而只有$1~(h-1)$层的结点才有可能需要下坠调整。

// 堆排序的完整逻辑
void HeapSort(ElemType A[], int len)
{
    BuildMaxHeap(A, len);         // 建立初始的堆
    for(int i=len;i>1;i--)
    {
        swap(A[i], A[1]);         // 将最大的元素置在最后
        HeadAdjust(A, 1, i-1);    // 处理置在1处元素
    }

}

// 建立大根堆
void BuildMaxHeap(ElemType A[], int len)
{
    for(int i=len/2;i>0;i--)
        HeadAdjust(A, i, len);
}
// 将以k为跟的子树调整为大根堆
void HeadAdjust(ElemType A[], int k, int len)
{
    A[0] = A[k];
    for(int i=2*k;i<=len;i*=2)
    {
        if(k<len && A[k]<A[k+1])
            i++;
        if(A[0]>A[i])
            break;
        else
        {
            A[k] = A[i];
            k = i;
        }
    }
}

归并排序、基数排序

归并排序

假设表为$L[0...n]。

思想:把两个或者多个已经有序的序列合并成一个。

分析:

• 时间复杂度: 每趟归并时间复杂度为$O(n)$，归并趟数为$\lceil\log_2 n\rceil$，则算法的时间复杂度为$O(n\log_2 n)$
• 空间复杂度: 申请数组$O(n)$，递归工作栈$O(\log_2 n)$，因此空间复杂度为$O(n)$.

int *B = (int *)malloc(n*sizeof(int));
void Merge(int A[], int low, int mid, int high)
{
    int i, j, k;
    for(k=low;k<=high;k++)
        B[k] = A[k];
    
    for(i=low, high=mid+1, k=i;i<=mid && j<=high;k++)
    {
        if(B[i] <= B[j])
            A[k] = B[i++];
        else
            A[k] = B[j++];
    }
    while(i <= mid) A[k++] = B[i++];
    while(j <= high) A[k++] = B[j++];
}

void MergeSort(int A[], int low, int high)
{
    if(low < high)
    {
        int mid = (low + high) / 2;
        MergeSort(A, low, mid);
        MergeSort(A, mid+1, high);
        Merge(A, low, mid, high);
    }
}

基数排序

分析:

• 空间复杂度: $O(r)$(链式)
• 时间复杂度: $O(d(r+n))$，总共d(关键字拆成d个部分)趟分配，r(每个部分可能的取值)，n(每趟分配的时间)。
• 稳定性: 稳定

基数排序擅长解决的问题:

• 数据元素的关键字可以方便的拆分成d组，且d较小
• 每组关键字的取值范围不大，即r比较小
• 数据元素个数n比较大