【数据结构】sorting

前置概念说明

稳定性

排序算法的“稳定性”是指，如果两个元素有相等的键值，在排序后这两个元素的相对顺序应保持不变。换句话说，一个稳定的排序算法会保留输入数据中相等元素的相对顺序。

Q: 谁是不稳定的？

A；答曰：“快希选堆”

与其他技术的互动或对比

数据库: 在数据库查询中，稳定的排序算法能确保当你按多个字段排序时，每一级的排序都不会影响其他级别的排序结果。

搜索引擎: 稳定性在搜索结果排序中也很重要，以便维持其他相关因素（如页面权重）的原有顺序。

并行计算: 在并行计算环境下，稳定排序算法更易于实现，并且能更有效地维持数据的相对顺序。

机器学习: 在数据预处理阶段，使用稳定的排序算法可以防止模型因数据顺序改变而受到不必要的影响。

简而言之，稳定性是排序算法中一个经常被忽视但实际上非常重要的特性。它与其他计算领域有很多交集和应用

作者：Native8418

链接：https://www.zhihu.com/question/587663148/answer/3211983666
来源：知乎

O(n^2) sorting algorithms

Bubble Sort

Selection Sort

Insertion Sort

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

//array[]为待排序数组，n为数组长度
void insertSort(int array[], int n)
{
    int i,j,temp;
    for( i=1;i<n;i++)
    {
        if(array[i]<array[i-1])
        {
            temp=array[i];
            for( j=i;array[j-1]>temp;j--)
            {
                array[j]=array[j-1];
            }
            array[j]=temp;
        }
    }
}

优化：折半插入排序

shell sort

希尔排序，也叫缩小增量排序，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。

先将待排序表分割成若干形如L[i,i+d,i+2d,…,i+kd]的特殊子表，分别进行直接插入排序，缩小增量d,重复直到d=1，即对整个表进行直接插入排序。

void ShellSort(int A[],int n){
    int i,j,d;
    for(d=n/2;d>=1;d=d/2){//步长变化
        for(i=d+1;i<=n;i++){
            if(A[i]<A[i-d])//需要将A[i]插入有序增量子表
                A[0]=A[i];//暂存在A[0]
                for(j=i-d;j>0&&A[0]<A[j];j-=d){
                    A[j+d]=A[j];//记录后移，查找插入位置
                }
                A[j+d]=A[0];//插入
            }
        }
    }

增量序列：

• Hibbard增量序列：$D_k=2^k-1$

• Sedgewick’s increments:$D_k=94^k-92^k+1$ 或$D_k=4^k-32^k+1 $
  The worst-case running time of Shellsort using Sedgewick’s increments is O(N4/3), O(N7/6) for the average-case. *(best known in practice)

O(nlogn) sorting algorithms

merge sort

归并排序，核心是把两个有序数组合为一个有序数组。

每一趟归并时间复杂度是O(n),n个元素进行2路归并，总共需要logn趟，所以总的时间复杂度是O(nlogn)。

void mergeSort(int array[], int n)
{
    int *temp;
    temp=(int *)malloc(n*sizeof(int));
    if(temp!=NULL)
    {
        mSort(array,temp,0,n-1);
        free(temp);
    }
    else
    {
        printf("No space!\n");
    }
}
void mSort(int array[], int temp[], int left, int right)
{
    int mid;
    if(left<right)
    {
        mid=(left+right)/2;
        mSort(array,temp,left,mid);
        mSort(array,temp,mid+1,right);
        merge(array,temp,left,mid,right);
    }
}
void merge(int array[], int temp[], int left, int mid, int right)
{
    int i,j,k;
    i=left;
    j=mid+1;
    k=left;
    while(i<=mid&&j<=right)
    {
        if(array[i]<=array[j])
        {
            temp[k++]=array[i++];
        }
        else
        {
            temp[k++]=array[j++];
        }
    }
    while(i<=mid)
    {
        temp[k++]=array[i++];
    }
    while(j<=right)
    {
        temp[k++]=array[j++];
    }
    for(i=left;i<=right;i++)
    {
        array[i]=temp[i];
    }
}

quick sort

快速排序和冒泡排序都属于交换排序。

快速排序的思想：在待排序表中任取一个元素pivot作为枢轴，或者说是基准，通过一趟排序将待排序表划分为独立的两部分，其中一部分的所有元素均比pivot小，另一部分的所有元素均比pivot大，此时pivot在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。

时间复杂度和空间复杂度都和递归层数（深度）正相关。时间复杂度=O(n*递归层数)，最好为O(nlogn)，也就是每次划分都均匀二分的情况；最差为O(n^2)，也就是已经排好序的划分后长度差别很大的情况。平均情况是接近最好情况的。空间复杂度=O(递归层数)，最好为O(logn)，最差为O(n)。

void quickSort(int array[], int n)
{
    qSort(array,0,n-1);
}
void qSort(int array[], int left, int right)
{
    int pivot;
    if(left<right)
    {
        pivot=partition(array,left,right);
        qSort(array,left,pivot-1);
        qSort(array,pivot+1,right);
    }
}
int partition(int array[], int left, int right)
{
    int pivotkey;
    pivotkey=array[left];
    while(left<right)
    {
        while(left<right&&array[right]>=pivotkey)
        {
            right--;
        }
        swap(array,left,right);
        while(left<right&&array[left]<=pivotkey)
        {
            left++;
        }
        swap(array,left,right);
    }
    return left;
}
void swap(int array[], int i, int j)
{
    int temp;

    temp=array[i];
    array[i]=array[j];
    array[j]=temp;
}

heap sort

堆排序是选择排序的一种。原理是首先将数组元素建成大小为n的大顶堆，堆顶（数组第一个元素）是所有元素中的最大值，将堆顶元素和数组最后一个元素进行交换，再将除了最后一个数的n-1个元素建立成大顶堆，再将最大元素和数组倒数第二个元素进行交换，重复直至堆大小减为1。

所以堆排序分为两个步骤，首先是建立大根堆，然后是输出堆顶元素，调整剩余元素成为新的堆。

所需要的最基本操作是小元素的下坠，建立大根堆和基于大根堆排序都是以元素下坠为操作基础的。

建立大根堆的时间复杂度：O(n)，基于大根堆排序的时间复杂度：O(nlogn)。综上，堆排序的时间复杂度：O(nlogn)。

大根堆的建立从待排序数组（有n个元素）的第n/2位置（保证是非叶子结点）开始。

void heapSort(int array[], int n)
{
    int i;
    //建立大根堆
    for (i=n/2;i>0;i--)
    {
        HeapAdjust(array,i,n);//从中间的非叶子结点开始，从下向上，从右向左调整
    }
    //基于大根堆进行排序
    for( i=n;i>1;i--)
    {
        swap(array, 1, i);//交换堆顶元素和最后的元素
        HeapAdjust(array, 1, i-1);//从上到下，从左向右调整
    }
}
void HeapAdjust(int array[], int s, int n )
{
    int i,temp;
    temp = array[s];
    for(i=2*s;i<=n;i*=2)
    {
        if(i<n&&array[i]<array[i+1])//确保i*2之后没有超过范围，也就是还有左节点；而且如果左节点小于右节点的话
        {
            i++;//转为比较右节点
        }
        if(temp>=array[i])
        {
            break;//如果父节点比两个子节点都大，那就不用继续往下坠了，直接break
        }
        array[s]=array[i];//否则就交换位置
        s=i;
    }
    array[s]=temp;//更新最终下坠的终点位置
}
void swap(int array[], int i, int j)
{
    int temp;

    temp=array[i];
    array[i]=array[j];
    array[j]=temp;
}

O(n) sorting algorithms

bucket sort

桶排序（Bucket sort）或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递回方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ(n)）。但桶排序并不是比较排序，他不受到 O(n log n) 下限的影响。

counting sort

计数排序（Counting sort）是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

radix sort

基数排序（Radix sort）是一种非比较型的整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

radix sort a array of strings

void radixSort(string array[], int n)
{
    int i;
    string *temp;
    temp=(string *)malloc(n*sizeof(string));
    if(temp!=NULL)
    {
        radixSort(array,temp,0,n-1,0);
        free(temp);
    }
    else
    {
        printf("No space!\n");
    }
}
void radixSort(string array[], string temp[], int left, int right, int radix)
{
    int i,j,k;
    int count[26];
    if(left<right)
    {
        for(i=0;i<26;i++)
        {
            count[i]=0;
        }
        for(i=left;i<=right;i++)
        {
            count[array[i][radix]-'a']++;
        }
        for(i=1;i<26;i++)
        {
            count[i]=count[i]+count[i-1];
        }
        for(i=right;i>=left;i--)
        {
            j=array[i][radix]-'a';
            temp[count[j]-1]=array[i];
            count[j]--;
        }
        for(i=left,j=0;i<=right;i++,j++)
        {
            array[i]=temp[j];
        }
        for(i=0;i<26;i++)
        {
            if(count[i]>0)
            {
                radixSort(array,temp,left+count[i-1],left+count[i]-1,radix+1);
            }
        }
    }
}

radix sorting的时间复杂度：O(d*(n+rd))，其中d是字符串的最大长度，r是字符串的基数，n是字符串的个数。

外部排序

多路归并

败者树