之前看数据结构的时候，了解到了一些排序的算法，这里来总结一下方便理解和记忆~
由于是笔记性质的，附上收集到的gif图和思路以及代码算法，复习的时候就不那么容易记混

一、交换类排序

1.1 冒泡排序(Bubble Sort)

冒泡排序是一种极其简单也很好理解的排序算法，在一轮冒泡排序中，它重复地走访过要排序的元素，依次比较相邻两个元素，如果他们的顺序错误就把他们调换过来，直到没有元素再需要交换，这一轮便排序完成。因为最大/小的数据像泡泡一样慢慢浮上来，所以叫做冒泡排序~

冒泡排序算法的运作如下：
比较相邻的元素，如果前一个比后一个大，就把它们两个调换位置。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

冒泡排序的时间复杂度最好为O(n)，平均和最坏情况都是O（n^2）

进行冒泡排序的实现过程如下

使用冒泡排序为一列数字进行排序的过程如下图所示：

C语言描述：

void bubbleSort(int *arr,int n)
{
    int m,i,j;
    for(i=0;i<n-1;i++)
        for(j=0;j<n-1-i;j++)
            if(arr[j]>arr[j+1])
            {
                m=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=m;
            }
}

1.2 冒泡排序的改进：鸡尾酒排序

鸡尾酒排序，也叫定向冒泡排序，是冒泡排序的一种改进。此算法与冒泡排序的不同处在于从低到高然后从高到低，而冒泡排序则仅从低到高去比较序列里的每个元素。他可以得到比冒泡排序稍微好一点的效能。

复杂度：
鸡尾酒排序最糟或是平均所花费的次数都是O(n²)，但如果序列在一开始已经大部分排序过的话，会接近O(n)。

使用鸡尾酒排序为一列数字进行排序的过程如下图所示：

C语言描述：

void cocktailSort(int A[], int n){
    int left = 0;
    int right = n - 1;
    while (left != right) {
        
        for (int i = left; i < right; i++) {
            if (A[i] > A[i+1]) {
                swapA(A, i, i+1);
            }
        }
        right--;
        
        for (int i = right; i > left; i--) {
            if (A[i-1] > A[i]) {
                swapA(A, i-1, i);
            }
        }
        left++;
    }
}

1.3 快速排序(Quick Sort)

快速排序顾名思义，是速度非常快的排序，不过他是不稳定的排序，他的核心思想是分治法

  1. 从序列中挑出一个元素，作为"基准"(pivot).
  2. 把所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准的后面（相同的数可以到任一边），这个称为分区(partition)操作。
  3. 对每个分区递归地进行步骤1~2，递归的结束条件是序列的大小是0或1，这时整体已经被排好序了。
    快速排序的时间复杂度为O(nlogn)

使用快速排序法对一列数字进行排序的过程：

严蔚敏版C语言描述

//quick sort
int Partition(SqList& L,int low,int high)
{
    L.r[0]=L.r[low];
    pivotkey=L.r[low].key;
    while(low<high)
    {
        while(L.r[high].key>pivotkey&&low<high) --high;
        L.r[low]=L.r[high];
        while(L.r[low].key<pivotkey&&low<high) ++low;
        L.r[high]=L.r[low];
    }
    L.r[low]=L.r[0];
    return low;
}
 
void QSort(SqList &L,int low,int high)
{
    if(low<high)
    {
        pivoloc=Partition(L,low,high);
        QSort(L,low,pivoloc-1);
        QSort(L,pivoloc+1,high);
    }
}
 
void QuickSort(SqList &L)
{
    QSort(L,1,L.length);
}

二、选择类排序

2.1 简单选择排序(Selection Sort)

选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

　　注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

进行比较操作的时间复杂度为O(n^2)，进行移动操作的时间复杂度为O(n)。

对序列{ 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 }进行选择排序的实现过程如下图

使用选择排序为一列数字进行排序的宏观过程： 

void SelectSort(Sqlist &L)
{
    for(i=1;i<L.length;++i)
    {
        k=i;
        for(j=i+1;j<L.length;++i)
        {
            if(L.r[j].key<L.r[k].key) k=j;
        }
        if(k!=i)
        {
            t=L.r[k];L.r[k]=L.r[i];L.r[i]=t;
        }
    }
}

2.2 堆排序(Heap Sort)

堆排序是考研的重点，它是指利用堆这种数据结构所设计的一种选择排序算法。堆是一种近似完全二叉树的结构（通常堆是通过一维数组来实现的），并满足性质：以最大堆（也叫大根堆、大顶堆）为例，其中父结点的值总是大于它的孩子节点。

它的的过程：

  1. 由输入的无序数组构造一个最大堆，作为初始的无序区
  2. 把堆顶元素（最大值）和堆尾元素互换
  3. 把堆（无序区）的尺寸缩小1，并调用heapify(A, 0)从新的堆顶元素开始进行堆调整
  4. 重复步骤2，直到堆的尺寸为1

堆排序算法的演示：

动画中在排序过程之前简单的表现了创建堆的过程以及堆的逻辑结构。
堆排序也是不稳定的排序算法。

//调整堆
void HeapAdjust(Sqlist &L,int s,int m)
{
    rc=L.r[s];                           //将r[s]值储存起来，在调整过程中不插入
    for(j=2*s;j<=m;j*=2)
    {
        if(j<m&&L.r[j].key<L.r[j+1].key)  ++j;
        if(rc.key>=L.r[j]) break;
        L.r[s]=L.r[j];s=j;               //这里先不插入，最后插入
    }
    L.r[s]=rc.key;                       //循环结束再将r[s]值插入
}
 
//初建堆
void CreatHeap(Sqlist &L)
{
    n=L.length;
    for(i=n/2;i>=1;--i)
    {
        HeapAdjust(L,i,n);
    }
}
 
//heap sort
void HeapSort(Sqlist &L)
{
    CreatHeap(L);                 //初建堆
    for(i=L.length;i>=1;i--)
    {                            //不断交换并调整堆
        t=L.r[1];
        L.r[1]=L.r[i];
        L.r[i=t;
        HeapAdjust(L,1,i-1);
    }

三、插入类排序

3.1 希尔排序(Shell Sort)

希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

  1. 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
  2. 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。
　　假设有一个很小的数据在一个已按升序排好序的数组的末端。如果用复杂度为O(n^2)的排序（冒泡排序或直接插入排序），可能会进行n次的比较和交换才能将该数据移至正确位置。而希尔排序会用较大的步长移动数据，所以小数据只需进行少数比较和交换即可到正确位置。

时间复杂度为：O(n^（1.3—2）) 空间复杂度：O(1)

gif图：

void ShellInsert(SqList& L,int dk)
{
    for(i=dk+1;i<=L.length;++i)
        if(L.r[i].key<L.r[i-dk].key)
        {
            L.r[0]=L.r[i];
            for(j=i-dk;j>0&&L.r[0].key<L.r[j].key;j-=dk)
                L.r[j+dk]=L.r[j];
            L.r[j+dk]=L.r[0];
        }
}
 
void ShellSort(SqList& L,int dt[],int t)
{
    for(k=0;k<t;++k)
        ShellInsert(L,dt[k]);
}
Last modification：May 11th, 2021 at 09:44 pm
© 允许规范转载