算法之经典排序算法

我就是我 2022-06-06 08:24 253阅读 0赞

# 基本排序算法 #

## 选择排序 ##

> 首先，找出数组中的最小元素，并用首位的元素与它交换。然后，从后面找出次大元素，并用第二个位置的元素与它变换。重复此步骤，直到排序完整个数组。这个方法称做选择排序(selection sort），因为它重复性地选择剩余元素中的最小元素来完成排序。

![这里写图片描述][SouthEast]

## 插入排序 ##

> 人们通常排列扑克的方法是一次考虑一张牌，将它插入到已经排序过的牌的适当位置中（时刻保持有序），这里通过一次回溯遍历将新的数据和已排好序的数据一一比较，找到适当的位置。在排序过程中 ， 当前索引左边的元素己有序 ， 但并非处于它们的最终位置，因为它们还必须移动，为后面碰到的更小元素腾出空间。不过，当索引到达右终端时，整个数组已经排序完毕。

![这里写图片描述][SouthEast 1]

[对应排序动画][Link 1]

## 冒泡排序 ##

> 冒泡排序不断地扫描文件，交换没有按序排列的邻近元素，直到完成整个文件的排序才停止 。 冒泡排序的主要优点是它易于实现，但实际上是否真的比插入排序和选择排序更容易实现值得商榷。 一般来说，冒泡排序会比其他两种方法要慢 。假如我们总是从右到左地移动文件。 第一遍中只要碰到最小元素，就用它左边的元素与它交换，最终将它放到数组的左末端 。 在第二遍中，将次小元素放到适当的位置，依此类推 。 因此，N遍足以完成排序任务，而且尽管冒泡排序将元素放到位要做更多的工作，但它的操作方式属于选择排序的一种。

## 希尔排序 ##

> 希尔排序也称缩小增量排序，完全是为了优化插入排序而产生的。插入排序速度慢，因为它进行的唯一变换仅仅涉及到邻接项，因此，在数组中，项只能一次移动一个位置。如果最小数值在最右端，则需要N步将他移到位。希尔排序先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

![这里写图片描述][SouthEast 2]

## 基本排序对应c源代码 ##

sort.h

#ifndef SORT_H
    #define SORT_H
    
    #include <stdio.h>
    typedef int Item;//定义排序的数据类型类型，为了实现万能比较，可以使用回调函数进行比较。
    bool isSort(int *a , int N);
    void DispalyItems(const Item *a , int N);
    void SelectionSort(int *a , int N);
    void InsertionSort(Item *a , int N);
    void BubbleSort(Item *a , int N);
    void ShellSort(Item *a , int N);
    #endif // SORT_H

sort.c

#include <stdbool.h>
    #include "sort.h"
    static int less(Item a ,Item b)//为了是程序通用化，修改比较程序即可。
    {
        if(a < b)
            return 1;
        else
            return 0;
    }
    static void exch(Item *a , int i , int j)
    {
        Item swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
    bool isSort(Item *a , int N)
    {
        for(int i =1 ; i<N ; i++){
            if(less(a[i] , a[i-1]))
                return false;
        }
        return true;
    }
    void DispalyItems(const Item *a , int N)
    {
        for(int i = 0 ; i < N ; i++)
            printf("%4d",a[i]);
        printf("\n");
    }
    void SelectionSort(Item *a , int N)//选择排序
    {
        int i , j;
        int min;//记录最小项索引
        for(i = 0 ; i < N ; i++ ){
            min = i;
            for(j = i + 1 ; j< N ; j++)//找出后面最小项索引并记录
                if(less(a[j] , a[min]))
                    min = j;
            exch(a , i , min);//最后一项自己和自己交换不变。
        }
    }
    void InsertionSort(Item *a , int N)//插入排序
    {
        int i , j;
        for( i = 0 ; i < N ; i++)
            for(j = i ; j > 0 ; j--){
                if(less(a[j] , a[j-1]))//插入前面已经排好序项目中
                    exch(a , j , j-1);
                else
                    break;//可以停止了因为前面已经排好序了不必继续遍历
            }
    }
    void BubbleSort(Item *a , int N)//冒泡排序
    {
        int i ,j;
        for(i = 0 ; i < N ; i++)
            for(j = i+1 ; j<N ; j++)
                if(less(a[j] , a[i]))//插入前面已经排好序项目中
                    exch(a , i , j);
    }
    void ShellSort(Item *a , int N)//希尔排序和插入排序很像
    {
        int i , j;
        int h = 1;//间隔大小
        while(h < N/3) h = 3 * h +1;//计算最大间隔。运用高纳德的 3n+1序列
        for( ; h >= 1 ; h /= 3 ){
       //h间隔一层循环
            for( i = h ; i < N ; i++)
                for(j = i ; j >= h ; j -= h){
                    if(less(a[j] , a[j-h]))//插入前面已经排好序项目中
                        exch(a , j , j-h);
                    else
                        break;//可以停止了因为前面已经排好序了不必继续遍历
                }
        }
    }

main.c

#include "sort.h"
    #include "stdlib.h"
    #define N 100
    int main(void)
    {
        Item *a = (Item *)malloc(N * sizeof(Item));
        for(int i = 0 ; i < N ; i++)
            a[i] = 1000*(1.0*rand()/RAND_MAX);//产生随机数
        DispalyItems(a , N);
        ShellSort(a , N);
        if( isSort(a , N) )
            printf("sorted\n");
        else
            printf("not sorted\n");
        DispalyItems(a , N);
        return 0;
    }

# 归并排序 #

分治思想：大问题分割成小问题解决，然后用所有小问题的答案来解决整个大问题。

> 归并排序是建立在归并操作上的一种有效的排序算法。该算法是分治法的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可，也就是下面merge实现的代码。  
> 要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。归并排序最吸引人的性质就是可以保证任意长度为N的数组排序所需要时间和NlgN成正比，缺点在于需要额外和N成正比的辅助空间。

## 自顶向下归并排序 ##

/**************归并排序****************/
    static void merge(Item *a , Item *aux , int lo , int mid , int hi)
    {
        for(int k = lo ; k <= hi ; k++)
            aux[k] = a[k];//将a数组复制到aux
        int i = lo , j = mid + 1;
        for(int k = lo ; k <= hi ; k++){
       //合并
            if( i  > mid) a[k] = aux[j++];//左边数据取完
            else if(j > hi) a[k] = aux[i++];//右边数据取完
            else if( less(aux[j] , aux[i]) ) a[k] = aux[j++];//
            else a[k] = aux[i++];
        }
    }
    static void MSort(Item *a , Item *aux , int lo , int hi)
    {
        if(hi <= lo) return ;
        int mid = lo + (hi - lo)/2;
        MSort(a , aux , lo , mid);//左半边排序
        MSort(a , aux , mid+1 , hi);//右半边排序
        merge(a , aux , lo , mid , hi);//归并
    }
    void MergeSort(Item *a , int N)
    {
        Item *aux = (Item *)malloc(N * sizeof(Item));
        MSort(a , aux , 0 , N - 1);//递归调用
        free(aux);//释放缓冲空间
    }
    #define N 16
    int main(void)
    {
        Item *a = (Item *)malloc(N * sizeof(Item));
        for(int i = 0 ; i < N ; i++)
            a[i] = 1000*(1.0*rand()/RAND_MAX);//产生随机数
        DispalyItems(a , N);
        MergeSort(a , N);
        if( isSort(a , N) )
            printf("sorted\n");
        else
            printf("not sorted\n");
        DispalyItems(a , N);
        return 0;
    }

下面两个图显示了递归调用的过程。  
![这里写图片描述][SouthEast 3]  
![这里写图片描述][SouthEast 4]

## 自底向上归并排序 ##

先归并微型数组，然后再成对归并得到子数组。一张图搞定这个方法。

#define MIN(a , b) ( (a) > (b) ) ? (b) : (a)
    static void MSort(Item *a , Item *aux , int lo , int hi)
    {
        if(hi <= lo) return ;
        int mid = lo + (hi - lo)/2;
        MSort(a , aux , lo , mid);//左半边排序
        MSort(a , aux , mid+1 , hi);//右半边排序
        merge(a , aux , lo , mid , hi);//归并
    }
    void MergeBUSort(Item *a , int N)
    {
        int sz , lo;
        Item *aux = (Item *)malloc(N * sizeof(Item));
        for(sz = 1 ; sz < N ; sz = sz + sz ){
       //sz子数组大小
            for( lo = 0 ; lo < N - sz ; lo += sz + sz){
       //lo子数组索引
                merge(a , aux , lo , lo+sz-1 , MIN(lo+sz+sz-1 , N-1));
            }
        }
        free(aux);//释放缓冲空间
    }
    #define N 16
    int main(void)
    {
        Item *a = (Item *)malloc(N * sizeof(Item));
        for(int i = 0 ; i < N ; i++)
            a[i] = 1000*(1.0*rand()/RAND_MAX);//产生随机数
        DispalyItems(a , N);
        MergeBUSort(a , N);
        if( isSort(a , N) )
            printf("sorted\n");
        else
            printf("not sorted\n");
        DispalyItems(a , N);
        return 0;
    }

![这里写图片描述][SouthEast 5]

稳定性：排序算法，对于两个相等的键，排完序后都保存了他们的相对顺序，那么就说排序算法是稳定的。插入、归并排序都是稳定的。

# 快速排序 #

> 快速排序是一种分治的排序算法。可能是应用最为广泛的排序算法了，实现简单并且适用于各种不同的输入数据且在一般应用中比其他排序算法快。最牛的特点是原地排序（仅仅需要很小的辅助栈，一个暂存变量），且长度为N的数组排序所需要的时间和NlgN成正比。

![这里写图片描述][SouthEast 6]

/**************快速排序****************/
    static int partition(Item *a , int lo , int hi)//快速排序的切分
    {
        int i = lo , j = hi + 1;
        Item v = a[lo];//用来切分数组的元素
        while(1){
            while(less(a[++i] , v))//扫描左边直到比v大停止
                if(i == hi)
                    break;
            while(less(v , a[--j]))//扫描右边直到比v小停止
                if(j == lo)
                    break;
            if(i >= j)//检查是否指针i和j交叉
                break;
            exch(a , i , j);
        }
        exch(a , lo , j);//交换切分元素
        return j;//返回切分元素的索引
    }
    static void Psort(Item *a , int lo , int hi)//内部调用排序
    {
        int j;
        if(hi < lo) return;
        j = partition(a , lo , hi);//切分
        Psort(a , lo , j-1);//左半部分排序，继续切分
        Psort(a , j+1 , hi);//右半部分排序，继续切分
    }
    void QuickSort(Item *a , int N)
    {
        Psort(a , 0 , N-1);
    }
    #define N 16
    int main(void)
    {
        Item *a = (Item *)malloc(N * sizeof(Item));
        for(int i = 0 ; i < N ; i++)
            a[i] = 1000*(1.0*rand()/RAND_MAX);//产生随机数
        DispalyItems(a , N);
        QuickSort(a , N);
        if( isSort(a , N) )
            printf("sorted\n");
        else
            printf("not sorted\n");
        DispalyItems(a , N);
        return 0;
    }

# 优先队列 #

> 许多应用要求我们使用按顺序排列的键来处理记录，但并不要求全部有序排列，或者所有的记录一次性排好。通常，搜集到一个记录集，处理其中具有最大键的记录；也许接着加入更多新目录，再处理具有当前最大键的记录，如此等等。这种情况下， 一个好的数据结构应该支持插入新记录、删除最大元素的运算，这样的数据结构称为优先队列 (priority queue) 。优先队列应该支持两种操作：删除最大元素和插入元素。  
> ![这里写图片描述][SouthEast 7]  
> 上图为优先队列实现过程，根据过程非常容易写出实现的代码。

## 数组实现 ##

/**************优先队列数组实现***************************/
    Item *pq;
    int pqindex = 0;//记录优先队列中的元素个数。
    void UnorderedArrayMaxPQ(int capacity)//动态创建优先队列缓冲区大小,并返回首地址
    {
        pq = (Item *)malloc( sizeof(Item) * capacity);
    }
    bool pqisEmpty()
    {
        return (pqindex == 0);
    }
    int pqSize()
    {
        return pqindex;
    }
    void pqInsert(Item x)
    {
        pq[pqindex++] = x;
    }
    Item pqdelMax()
    {
        int max = 0 , i = 0;
        for( i = 0 ; i < pqindex ; i++){
            if(less(pq[max] , pq[i])) max = i;//找出最大元素下标
        }
        exch(pq , max , pqindex-1);//把最大元素交换到缓冲最后
        return pq[--pqindex];//返回最大元素，并且缓冲队列记录减去1
    }
    void dispalypq()
    {
        int i;
        printf("pqsize = %d, " , pqindex);
        for( i = 0 ; i < pqindex ; i++){
            printf("%d " , pq[i]);
        }
        printf("\n");
    }
    
    int main(void)
    {
        UnorderedArrayMaxPQ(10);
        pqInsert(3);
        pqInsert(1);
        pqInsert(4);
        pqInsert(7);
        pqInsert(9);
        pqInsert(0);
        dispalypq();
    
        pqdelMax();
        dispalypq();
    
        pqdelMax();
        dispalypq();
    
        pqdelMax();
        dispalypq();
    
        pqdelMax();
        dispalypq();
        return 0;
    }

![这里写图片描述][SouthEast 8]  
实现起来很简单，通过一个数组缓冲数据，然后输出最大值而已。

## 二叉堆实现 ##

> 堆：一种简单的数据结构，可以有效的支持基本优先队列运算。在堆中，记录保存在教组中，确保每个键大于其他两个指定位置的键。反过来，这两个键的每个键卫必须大于另外的两个键。将键看作一颗二叉树结构中的元素，那么当一颗二叉树的每个节点都大于等于他的两个子节点时，被称为堆有序。  
> 二叉堆：是堆有序的完全二叉树，并在数组中按照层级储存（不使用数组第一个位置，因为那样表示更加方便。并且第一个元素可以当作哨兵元素）。  
> ![这里写图片描述][SouthEast 9]  
> 为了满足二叉堆规则：需要提供两种操作 swim（上浮），sink（下沉）。

swim操作为了消除子节点比父节点大：  
![这里写图片描述][SouthEast 10]  
sink操作为了消除父节点比子节点小：  
![这里写图片描述][SouthEast 11]

通过swim和sink就可以通过二叉堆规则实现优先队列  
其中insert操作，需要swim配合，delMax需要sink配合，这几个ppt图片已经清楚说明了操作详情。  
![这里写图片描述][SouthEast 12]  
![这里写图片描述][SouthEast 13]

#include "sort.h"
    /**************优先队列二插堆实现***************************/
    static Item *pq;
    static int N;//优先队列索引
    void PQinit(int maxN)
    {
        pq = (Item *)malloc(sizeof(Item) * (maxN + 1));//分配缓冲空间
        N = 0;
    }
    static int less(Item a ,Item b)
    {
        if(a < b)
            return 1;
        else
            return 0;
    }
    static void exch(Item *a , int i , int j)
    {
        Item swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }
    static void swim(Item *a , int k)//插入元素上浮到合适位置
    {
        while(k > 1 && less(a[k/2] , a[k])){
       //父节点小于子节点
            exch(a , k , k/2);//交换
            k = k/2;//索引下一次遍历
        }
    }
    static void sink(Item *a , int k , int N)//删除元素下沉到合适位置,N缓冲队列最后元素索引
    {
        int j;
        while(2 * k <= N){
            j = 2*k;
            if(j < N && less(a[j] , a[j+1])  ) j++;//在子节点中选择较大的一个
            if(!less(a[k] , a[j])) break;//如果已经满足条件，结束循环
            exch(a , k , j);//交换父子节点
            k= j;//迭代，继续下次循环
        }
    }
    void PQinsert(Item k)
    {
        pq[++N] = k;
        swim(pq,N);//将元素找到合适位置
    }
    Item delMax()
    {
        exch(pq, 1 , N);//将最大元素换到队列尾部
        sink(pq , 1 , N-1);
        return pq[N--];//删除一个元素
    }
    void dispalypq()
    {
        int i;
        printf("pqsize = %d, " , N);
        for( i = 1 ; i <= N ; i++){
            printf("%d " , pq[i]);
        }
        printf("\n");
    }
    #include "sort.h"
    #include "stdlib.h"
    int main(void)
    {
        PQinit(10);
    // bool pqisEmpty();
    // int pqSize();
    // void dispalypq();
        PQinsert(3);
        PQinsert(1);
        PQinsert(4);
        PQinsert(7);
        PQinsert(9);
        PQinsert(0);
        dispalypq();
    
        delMax();
        dispalypq();
    
        delMax();
        dispalypq();
    
        delMax();
        dispalypq();
    
        delMax();
        dispalypq();
        return 0;
    }

![这里写图片描述][SouthEast 14]  
结果就是二叉堆形式的优先队列。

# 堆排序 #

> 1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert W．Floyd）和威廉姆斯(J．Williams）在1964年共同发明了著名的堆排序算法（Heap Sort)。堆排序在唯一利用空间和时间的方法，当空间十分紧张的时候，很流行，因为它并不不需要辅助，且只需要几行代码就可以实现，具有较好的性能。堆排序需要两步：  
> 构造堆：将原始数组重新组织并安排进一个堆中。  
> 下沉阶段：从堆中依次按递减顺序取出所有元素并取得排序结果。

**构造堆可以从左到右遍历数组，通过上浮操作保证指针左边的元素已经是一个有序的完全二叉树即可，就像连续向优先队列里面插入元素一样。更好的方法是从右到左通过下沉方法构造一个堆，经过的的步骤明显比较小。实际过程就如同下图一样，一直使用下沉操作进行。下面示意图说明了一切。**

![这里写图片描述][SouthEast 15]

void HeapSort(Item *a , int N)
    {
        int k;
        for(k = N/2 ; k >=1 ; k--)//在原数组上面构造堆阶段
            sink(a , k , N);//N是最后元素索引
        while(N > 1){             //交换下沉操作
            exch(a , 1 , N);
            sink(a , 1 , --N);
        }
    }
    
    #include "sort.h"
    #include "stdlib.h"
    #define N 16
    int main(void)
    {
        Item *a = (Item *)malloc(((N+1)) * sizeof(Item));
        for(int i = 1 ; i < N+1 ; i++)
            a[i] = 1000*(1.0*rand()/RAND_MAX);//产生随机数
        DispalyItems(a+1 , N);
        HeapSort(a , N);//a[0]并没有用
        if( isSort(a+1 , N) )
            printf("sorted\n");
        else
            printf("not sorted\n");
        DispalyItems(a+1 , N);
        return 0;
    }

![这里写图片描述][SouthEast 16]  
![这里写图片描述][SouthEast 17]

# 排序应用及方法对比 #

![这里写图片描述][Image 1]

[SouthEast]: /images/20220606/4b809853af9e4f39a1d86efbe3be4a2a.png
[SouthEast 1]: /images/20220606/b292c57db27e46d48d0b54b187034fd3.png
[Link 1]: https://www.toptal.com/developers/sorting-algorithms/insertion-sort
[SouthEast 2]: /images/20220606/766745cadca14918b236ef74facaea85.png
[SouthEast 3]: /images/20220606/569bd9e1768443eb8f7ddf97abc2aa45.png
[SouthEast 4]: /images/20220606/f2388a57cb7f4cbea75b47454ad2aa69.png
[SouthEast 5]: /images/20220606/9511a758db60413ebf91ef5dc9a54e62.png
[SouthEast 6]: /images/20220606/f887a3e5a48a43bcb8c4586346a63a17.png
[SouthEast 7]: /images/20220606/8da064fe91194bd7958840e9030ad34e.png
[SouthEast 8]: /images/20220606/5510dead7e6249ba8ede54c5f6e1185f.png
[SouthEast 9]: /images/20220606/e86002882ef84103abe646fc5971a827.png
[SouthEast 10]: /images/20220606/4427d0a3a1124808a285053d2df85419.png
[SouthEast 11]: /images/20220606/901e95d89c324c6589f9a2b5ef68b5d0.png
[SouthEast 12]: /images/20220606/e3451895d3054743903483ee427e978b.png
[SouthEast 13]: /images/20220606/452a9e7f88c048d6a9197892aa82908b.png
[SouthEast 14]: /images/20220606/477fbfbeccb14269807ca63218ede8b4.png
[SouthEast 15]: /images/20220606/da171b12891b407cb49b2d2a77bc8645.png
[SouthEast 16]: /images/20220606/b1d7b48b320d45ea882e19afead40b0c.png
[SouthEast 17]: /images/20220606/5f976219073b46ac8ba3795117d1054c.png
[Image 1]: