专栏主页：计算机专业基础知识总结（适用于期末复习考研刷题求职面试）系列文章https://blog.csdn.net/seeker1994/category_12585732.html

......

数据结构知识点总结12-(第六章.图)-图的存储结构及图的遍历

数据结构知识点总结13-(第六章.图)-图的应用

数据结构知识点总结14-(第七章.查找)

......

第八章、排序

简介

        稳定的算法在排序的过程中不会改变相等元素彼此位置的相对次序，反之不稳定的排序算法经常会改变这个次序。

        一般情况下内部排序算法在执行过程中都要进行两种操作：比较和移动。但并非所有的排序算法都基于这两个操作，比如基数排序就不基于比较。

        每种排序都有各自的优缺点，适用于不同的场景。

插入排序

（1）直接插入排序

        空间复杂度O(1)；在排序过程中，向有序表中逐个插入元素的操作进行了n-1趟，每趟操作都需要比较和移动元素，比较次数和移动次数取决于初始待排序表的状态。

        最好情况下表已经有序，此时每插入一个元素，都只需要比较一次而不用移动元素，因为最好情况下时间复杂度为O(n).

        直接插入排序适用于顺序存储和链式存储的线性表，链式存储时，可以从前往后查找指定元素的插入位置。而大部分排序算法都仅适用于顺序存储的线性表。

代码：

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

（2）二分插入排序

        从前面的直接插入排序算法中，不难看出每趟插入的过程，都进行了两项工作：

        从前面的子表中查找出待插入元素应该被插入的位置。

        给插入位置腾出空间，将待插入元素复制到表中的插入位置。

        注意到该算法中，总是边比较边移动元素，下面将比较和移动操作分离开，即先二分查找出元素的待插入位置，然后再统一的移动待插入位置之后的元素。

        二分插入排序不是稳定的，最好情况下，当插入位置刚好是二分位置时，所用时间为O(log₂n); 最坏的情况是当插入的位置不在二分位置 所需比较次数为O(n)，平均时间复杂度为O(n^2)。

void InserSort(int 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[0])
                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];
    }
}

（3）希尔排序

        直接插入排序若待排序列为正序时，其时间复杂度可提高到O(n)，由此可见它更适合于基本有序的排序表和数据量不大的排序表。希尔排序正是利用了这两点观察，对直接插入排序进行改进，希尔排序又称为缩小增量的排序。

        希尔排序的基本思想是：先将待排序表分割为若干个形如L[i, i+d, i+2d, …, i+kd]的特殊子表，分别进行直接插入排序。希尔排序的排序过程如下：

        先取一个小于n的步长d1，把表中所有距离为d1的倍数的记录放在同一个组中，在各组中进行直接插入排序；然后取第二个步长d2≤d1，重复上述过程，直到所取到的dt=1，即所有记录已放在同一组中，再进行直接插入排序，由于此时已经具有较好的局部有序性，故可以很快的得到结果。到目前为止，尚未求得一个最好的增量序列，希尔提出的方法是d1 = n/2，di+1=di/2，并且最后一个增量等于1。

void SheelSort(int A[],int n) {
    for(int 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]; j=j-dk)
                    A[j+dk]=A[j];
                A[j+dk]=A[0];
            }
}

交换排序

        所谓交换是指根据序列中两个元素关键字的比较结果来对换这两个记录在序列中的位置。基于交换的排序算法很多，一般仅介绍冒泡排序和快速排序。

（1）冒泡排序

        冒泡排序的算法思想是：假设待排序表长为n，从后往前（或者从前向后）两两比较相邻元素的值，若为逆序（即A[i−1]>A[i])，则交换他们，直到序列比较完。我们称之为一趟冒泡，结果将最小的元素交换到待排序的第一个位置（关键字最小的元素如气泡一般逐渐向上“漂浮”直至“水面”，这就是冒泡排序名字的由来）。

        下一趟冒泡的时候，前一趟确定的最小元素不再参加比较，待排序列减少一个元素，每趟冒泡的结果把序列中的最小元素放到了序列的最终位置。

void BubleSort(int A[],int n) {
    for(int i=0;i<n-1;i++) {
        bool flag=false;
        for(int j=n-1;j>i;j--)
            if(A[j-1]>A[j]) {
                swap(A[j-1],A[j]);
                flag=true;
            }
        if(flag==false)
            break;
    }
}

        冒泡排序是最常用的小型数据排序方式，下面是其两种优化方式。

        第一种优化方式是设置一个标记位来标记是否发生了交换，如果没有发生交换就提前结束；

        第二种优化方式是记录最后发生交换的位置，作为下一趟比较结束的位置。因为每冒一次可以将最大的放在上面，结束位置之上的都是最大的，没有必要比较。

（2）快速排序

        快速排序是对冒泡排序的一种改进，其基本思想是基于分治法的：在待排序表L[1…n]中任取一个元素pivot作为基准，通过一趟排序将待排序表划分为独立的两部分L[1 … k−1]和L[k+1 … n]使得L[1 … k−1]中所有元素小于pivot，L[k+1 … n]中所有元素均大于或等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一趟快速排序。

        而后分别递归的对两个子表重复上述过程，直至每部分内只有一个元素或者为空为止，即所有元素放在了其最终位置之上。

int Partition(int A[], int low, int high) { // 传入 数组和 上下限
    int pivot = A[low];      // 让pivot暂存传入的数组第一个值.
    while(low<high) {        // 当low等于high的时候 才跳出去。
        while(low<high&&A[high]>=pivot) // 当low小于high并且数组靠前的值
            high--;                     //开始 减小high的值 知道不符合上述条件
        A[low]=A[high];                 // 较小的值 放到前面 那个空位上
        while(low<high&&A[low]<=pivot)  // 当low小于high并且数组靠前的值比较小
            low++;
        A[high]=A[low];
    }
    A[low]=pivot;
    return low;
}
void QuickSort(int A[], int low, int high) {
    if(low<high) {
        int pivot = Partition(A,low,high);
        QuickSort(A,low,pivot-1);
        QuickSort(A,pivot+1,high);
    }
}

快速排序动画演示：

选择排序

        选择排序的基本思想是：每一趟比如第i趟 ，在后面n-i+1个排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第n-1趟昨晚，待排序列只剩下1个就不用再选了。

（1）简单选择排序

        简单选择排序算法的思想：假设排序表L[1…n]，第i趟排序即从L[i…n]中选择关键字最小的元素与L(i)交换，每一趟排序可以确定 一个元素的最终位置，这样经过n−1趟排序就可以使整个排序表有序。

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]);
    }
}

（2）堆排序

        堆排序是一种树形选择排序方法，它的特点是：在排序过程中，将L[1…n]看做一棵完全二叉树的顺序存储结构，利用完全二叉树双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大。

        堆的定义如下：n个关键字序列L[1…n]称为堆，当且仅当该序列满足：L(i)≤L(2i)且L(i)≤L(2i+1)或L(i)≥L(2i)且L(i)≥L(2i+1)。

        满足前者的称为小根堆（小顶堆），满足后者情况的堆称为大根堆（大顶堆）。显然，在大根堆中，最大元素存放在根节点中，且对其任一费根节点，它的值小于或者等于其双亲结点值。小根堆的定义刚好相反，根节点是最小元素。

        堆排序的关键是构造初始堆，掌握初始序列建堆的过程。

最小堆的构造：

     初始数组为：9,3,7,6,5,1,10,2

      按照完全二叉树，将数字依次填入。

      填入后，找到最后一个结点（本示例为数字2的节点），从它的父节点（本示例为数字6的节点）

开始调整。根据性质，小的数字往上移动；至此，第1次调整完成。

      注意，被调整的节点，还有子节点的情况，需要递归进行调整。

      第二次调整，是数字6的节点数组下标小1的节点（比数字6的下标小1的节点是数字7的节点），

用刚才的规则进行调整。以此类推，直到调整到根节点。

注意：数字9的节点 将和 数字1的节点 发生对调，对调后，需要递归进行调整，请一定注意。

最小堆的插入：

        以上个最小堆为例，插入数字0。

        数字0的节点首先加入到该二叉树最后的一个节点，依据最小堆的定义，自底向上，递归调整。

        按照序列逐步插入，也可以构造了一个最小堆。

最小堆的删除：

        对于最小堆和最大堆而言，删除是针对于根节点而言。对于删除操作，将二叉树的最后一个节点替换到根节点，然后自顶向下，递归调整。依次删除堆顶元素，即完成了堆排序。

void AdjustDown(int A[],int k,int len)
{
    A[0]=A[k];
    for(int i=2*k;i<=len;i=i*2)
    {
         if(i<len && A[i]<A[i+1])
            i++;
        if(A[0]>=A[i])
            break;
        else
        {
            A[k]=A[i];
            k=i;
        }
    }
    A[k]=A[0];
}
void AdjustUp(int A[],int k)
{
    A[0]=A[k];
    int i=k/2;
    while(i>0&&A[i]<A[0])
    {
        A[k]=A[i];
        k=i;
        i=k/2;
    }
    A[k]=A[0];
 }
void BuildMaxHeap(int A[],int len)
{
    for(int i=len/2;i>0;i--)
        AdjustDown(A,i,len);
        //AdjustUp(A,i);
}
void HeapSort(int A[],int len)
{
    BuildMaxHeap(A,len);
    for(int i=len;i>1;i--)
    {
        swap(A[i],A[1]);
        AdjustDown(A,1,i-1);
    }
}

下一篇介绍：数据结构知识点总结-(第八章.排序)-归并排序、基数排序、桶排序、Hash排序、外部排序。

专栏主页：计算机专业基础知识总结（适用于期末复习考研刷题求职面试）系列文章https://blog.csdn.net/seeker1994/category_12585732.html

......

数据结构知识点总结12-(第六章.图)-图的存储结构及图的遍历

数据结构知识点总结13-(第六章.图)-图的应用

数据结构知识点总结14-(第七章.查找)

......