数据结构之排序

2024-01-01 21:31:28

插入排序

算法思想：

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

特点：

是稳定的排序

空间复杂度为O(1)

平均时间复杂度为O(n^2)

最好的情况：原有序列有序，时间复杂度为O(n) 比较次数 n-1

最坏的情况：原有序列逆序，时间复杂度为O(n^2) 比较次数为 n*(n-1)/2

排序过程（递增排序）：

1.初始时，会从第二个元素开始（因为第一个元素已经是有序的了）。

2.将38与之前排好序的数依次进行对比，比38大的数要依次后移一位，然后再将38放入空出来的位置里。

3.处理65，65比已排好序的序列中的38和49均大，所以65放在原位置即可。

4.依次对剩下的每个数进行排序，最终可以得到一个递增的有序序列

实现：

void InsertSort(int A[],int n)
{
    int i,j,temp;
    for(i = 1; i < n; i++)
    {
        temp = A[i];
        if(temp>A[i-1])//如果当前待排数字大于前一个数字，那么不需要移位
            continue;
        for(j = i-1; j >= 0 && A[j]>temp; j--)
        {
            A[j+1]=A[j];
        }
        A[j+1] = temp;
    }
}

折半查找优化：

使用折半查找优化后，虽然找应该放的位置的比较次数减少了，但是并没有改变元素移位带来的时间花费，因此时间复杂度仍然为O(n^2)

void InsertSort(int A[],int n)
{
    int i,j,temp,low,high,mid;

    for(i = 1; i < n; i++)
    {
        temp = A[i];
        if(temp>A[i-1])
            continue;
        low = 1,high = i-1;
        //找第一个值大于temp的位置或最后一个值等于temp的位置
        while(low<=high)
        {
            mid = (low+high)/2;
            if(A[mid]>temp)
            {
                high = mid-1;
            }
            else
                low=mid+1;
        }
        //最终high+1指向的就是应该放的位置
        for(j = i-1; j >= high+1; j--)
        {
            A[j+1]=A[j];
        }
        A[high+1] = temp;
    }
}

基于链表实现的插入排序：

虽然插入元素不需要移位了，但是在链表中找到一个合适的插入位置需要从头开始遍历链表，所以时间复杂度仍然为O(n^2)

希尔排序

算法思想：

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

特点：

是一个不稳定的排序。

空间复杂度为O(1)

最坏时间复杂度为O(n^2)，当n在某个范围内时，可达O(n^1.3)

只适用于顺序表，不适用于链表。

排序过程：

与49相距为4的数为76；与38相距为4的数为13；与65相距为4的数为27；与97相距为4的数为49；因此构成4个子表。

然后分别对每个子表进行插入排序，最终结果如下

第一趟希尔排序后，表中数据如下：

第二趟希尔排序：

形成的子表有：

分别对子表进行插入排序，结果如下：

表中元素如下：

第三趟希尔排序：

相当于对整个表进行插入排序。

结果如下：

经过三趟希尔排序后，就得到了一个有序序列。

整体过程：

稳定性：

算法是不稳定的。

实现：

第一个元素的下标为0

void ShellSort(int A[],int n)
{
    int d,i,j,temp;
    for(d = n/2;d>=1;d/=2) // 枚举增量d
    {
        for(i = d;i<n;i++)//对子表进行插入排序
        {
            if(A[i]<A[i-d])//在子表中，前一个数比当前数大，需要进行插入排序
            {
                temp = A[i];
                for(j=i-d;j>=0&&A[j]>temp;j-=d)
                {
                    A[j+d]=A[j];
                }
                A[j+d]=temp;//最后j指向不合法的位置，j+d代表最后一个合法的位置
            }
        }
    }
}

冒泡排序

算法思路：

从后往前（或者从前往后），两两比较相邻元素的值，若为逆序（A[i-1]>A[i]），则交换它们，直到比较完。称这样的过程为"一趟"冒泡排序。每一趟排序都可以使一个元素移动到最终位置，已经确定好最终位置的元素在之后的处理中无需再对比。如果某一趟排序过程未发生交换，则算法可以提前结束。

一趟冒泡排序可以将当前表中最小的值放在最左边（最大的值放在最右边）。

特点：

空间复杂度为O(1)

算法是稳定的。

最好时间复杂度为O(n)

平均时间复杂度为O(n^2)

最坏时间复杂度为O(n^2)

比较次数为（n-1)*n/2

移动次数:每次发现一个逆序对，需要移动三次元素。

冒泡排序可以适用于链表

排序过程：

第一趟冒泡排序：

首先，比较最后面的两个元素，27比49小，且27在49前面，所以不需要改变位置。

之后往左移，13比27小，不用交换位置。

76比13小，所以要把76与13对调

97比13大，所以要互换位置。

65比13大，所以要呼唤位置。

38比13大，所以要互换位置。

49比13大，所以要互换位置。

最终把一个最小的数13移到了表的最左边。

每趟冒泡排序都把未确定最终位置的中的一个最小的数移到最左边。所以接下来再进行7趟冒泡排序即可实现序列有序。

实现：

void BubbleSort(int A[],int n)
{
    for(int i = 0;i<n-1;i++)
    {
        bool flag = false;//表示本趟冒泡排序是否发生交换的标志
        for(int j = n-1;j>=0;j--)//一趟冒泡过程
        {
            if(A[j]>A[j+1])//若为逆序
            {
                flag = true;
                swap(A[j],A[j+1]);//交换
            }
        }
        if(flag == true)//本趟遍历没有发生交换，说明表已经有序
            return;
    }
}

快速排序

算法思想：

特点：

空间复杂度为O(log(n))也就是递归深度

最坏空间复杂度为O(n)

平均时间复杂度为O(nlog(n))

最差时间复杂度为O(n^2)

是一个不稳定的排序

是所有内部排序中平均性能最优的

排序过程：

选取low指向的元素为枢轴。我们的任务是保证最后枢轴左边的数都比枢轴小，枢轴右边的数都比枢轴大。

使用high指针向左遍历，low指针向右遍历，移动的过程中保证high右边的值都大于等于枢轴，low左边的值都小于枢轴。

因为low指向的位置的元素已经被算作枢轴了，所以应该从high开始遍历。因为high此时指向的是49，49大于等于枢轴49，所以high直接左移即可。

high指向27，27比49小，所以27应该放在low指针的左边。把27移到low处，low++。

这时需要从low开始向右遍历（因为high那个位置空出来了），low指向的38小于49，所以不需要移动。low++。

移动后的low指向65，65>45，所以65应该放在high的位置。

此时，low处又空出来了，因此要从high位置向左遍历。

13小于49，13应该放在low处。low指针后移。

97大于49，97应该放在high指向位置。之后high左移。

76大于49不需要改变位置，high左移。

最终，low指针与high 指针重合时，表中的数已经满足了low左边的数都比49小，high右边的数都比49大，此时这个位置就是枢轴49的位置。

最终一趟快棑就实现了。

之后分别对49左边数组成的表与49右边的数组成的表进行递归快排，最终就可以使整个表的元素有序了。

实现：

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

算法效率分析：

对于一个序列的快速排序递归可视为建立一棵二叉树。

每一层时间复杂度不超过O(n)，总的层数依赖于树的高度，而树的高度的范围为⌈log(n+1)⌉~n，

所以时间复杂度的范围为O(nlog(n))~O(n^2)

如果每次枢轴都可以把表平均分为两部分，这样效率最高。如果每次枢轴只能把表分为一部分，那么quicksort树就会变成一颗单支树，高度为n，效率最低。

优化思路：

选头、中、尾三个位置的元素，取中间值作为枢轴元素；
随机选一个元素作为枢轴元素。

注意事项：

在408中

一次划分，就是对划分出来的那个表进行一趟快排，最终确定一个元素的位置。

一趟快排，能确定多个元素的最终位置。

如第二层，一趟排序确定了两个元素的位置

选择排序

算法思想：

每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列

特点：

空间复杂度为O(1)

时间复杂度为O(n^2)

无论逆序有序还是乱序，选择排序都会进行n-1趟，总共需要比较关键字n(n-1)/2。

选择排序是不稳定的。

适用于链表和顺序表。

排序过程：

第一趟排序：会从待排序元素中选取一个最小的元素与待排元素中第一个位置的元素交换。将13与49交换。

第二趟排序：从待排元素中选取最小的一个，与38交换。

最终经过7轮排序后，就可以得到一个有序序列、

实现：

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

堆排序

前置知识：

堆的概念

堆一定是一棵完全二叉树。且当i<=n/2时，结点是分支节点。

建立大根堆

思路：将所有非终端结点都检查一遍是否满足大根堆的要求，如果不满足则进行调整。

下图是一个含有8个元素的序列，其中前8/2=4个元素为分支节点。需要从最后一个分支结点开始检查是否符合大根堆的要求（这样可以保证每个分支结点在检查的时候，它的孩子已经确定了）。

1.显然，最后一个分支结点不满足大根堆的要求，32与09应该交换

2.接下来是三号节点，78应该与87交换。

3.接下来是2号结点，45比17大，45与32交换。

4.对于1号结点53，显然87比53要大，所以83与53交换位置

5.但是交换完之后，发现3号结点，也就是53当前位置不符合大顶堆了，所以要调整3号结点，将78与65交换。

最后就得到了一个大根堆。

有了大根堆之后，就可以是实现堆排序了。

算法思路：

每趟将堆顶元素加入有序子序列（与待排序序列中的最后一个元素交换），并将待排序元素序列再次调整为大根堆。

特点：

总的时间复杂度为 O(n)+O(nlog(n)) = O(nlog(n))

空间复杂度为O(1)

是一个不稳定的排序。

排序过程：

1.将堆顶元素与最后一个待排序序列中最后一个位置的元素互换位置。87与09互换位置。

此时堆已经不符合大顶堆了，所以要对堆进行调整，但87已经是确定最终位置的元素了，所以不算在堆中，也就是说我们在调整的过程中是把前n-1个元素视作一个待调整为大顶堆的序列。

2.调整好的堆如下。

此时再次将堆顶元素与待排序列中的最后一个元素互换位置。

3.这样就确定好了87与78在最终有序序列中的位置。之后再调整前n-2个元素为大顶堆。

4.这样不断重复交换和调整，最终就可以得到一个有序序列。

实现：

//调整大顶堆(非递归)
void HeapAdjust(int A[],int root,int n)
{
    int temp = A[root];
    for(int i = 2*root;i<=n;i*=2)
    {
        //取左右孩子中较大的那个
        if(i<n&&A[i]<A[i+1])
            i++;
        if(temp>=A[i]) break; //筛选结束
        else
        {
            A[root]=A[i];//将A[i]放在父节点上
            root=i;//修改root的值，继续往下筛选
        }
    }
    A[root]=temp;//把被筛选的值放入最终位置。
}
//调整为大顶堆（递归）
void HeapAdjust(int A[],int root,int n)
{
    int temp = A[root];
    int l = root*2,r=root*2+1,maxIndex = root;
    if(l<=n&&A[maxIndex]<A[l])
    {
        maxIndex = l;
    }
    if(r<=n&&A[maxIndex]<A[r])
    {
        maxIndex = r;
    }
    if(root==maxIndex)
    {
        return ;
    }
    swap(A[root],A[maxIndex]);
    if(maxIndex<=n/2)//如果maxIndex是一个分支结点，则还检查maxIndex结点。
    HeapAdjust(A,maxIndex,n);
}
//建立大顶堆
void BuildMaxHeap(int A[],int n)
{
    //调整每一个分支节点
    for(int i =n/2;i>=1;i--)
    {
        HeapAdjust(A,i,n);
    }
}
//堆棑
void HeapSort(int A[],int n)
{
    BuildMaxHeap(A,n);
    for(int i = n;i>1;i--)
    {
        swap(A[i],A[1]);
        HeapAdjust(A,1,i-1);
    }
}

效率分析：

在排序部分中，需要依次将堆顶元素与最后一个待排元素交换位置，一共需要交换n-1次，而每次交换完之后需要调整堆，调整一次堆的时间复杂度为O(h)=O(log(n))。所以排序部分的时间复杂度为O(nlog(n))

总的时间复杂度为 O(n)+O(nlog(n)) = O(nlog(n))

空间复杂度为O(1)

堆的插入操作

每次上升的过程中只需要比较一次关键字

堆的删除操作

每次下坠的过程中，至多比较两次关键字。

归并排序

前置知识：

归并：把两个或多个已经有序的序列合并为一个有序序列。

二路归并：把两个有序的序列合并为一个有序序列

notes，m路归并，每选出一个关键字，需要进行m-1次关键字对比。

算法思路：

将一个序列不断从中间划分，当划分到每个子序列只有一个元素时，开始进行二路合并，二路合并完一次后，会得到多个有序的包含两个元素的子序列，然后再进行二路合并，得到多个有序的包含四个元素的子序列，这样不断归并下去，最终得到一个有序的序列。

特点：

归并排序的时间复杂度为O(n*log(n))

空间复杂度为O(n)

是一个稳定的排序。

排序过程：

实现：

void Merge(int A[],int low,int mid,int high)
{
    int i,j,k;
    for(k=low;k<=high;k++)
    {
        B[k]=A[k];
    }
    k=low;
    for(i=low,j=mid+1;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);//合并
    }
}