数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(上)

简介: 数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)

排序:所谓排序,就是使一组杂乱无章的数据,按照其中的一定的规律或某些关键字

(如价格,销量,好评率,排名等)的大小,递增或递减地排列起来的操作。

为了方便,我们这里讲的排序和有序指的都是升序,降序反过来就行了。

1.插入排序

1.1直接插入排序

  核心思想:

  把一个数插入一个有序区间。

  实现方法:假设0—end是已经有序的区间,我们用x存储end后面一个位置的元素,表示要把x存储到0—end的有序区间中。

  如果end所指元素比x大,就把end所指的元素赋给后面一个位置的元素(相当于把end所指元素往后移动一个格子),然后end=end-1使end指向前一个元素,继续比较;

1.1.1单趟插入排序:(把x插入一个有序数组

 
//单趟排序:(把x插入一个有序数组)
// 1 2 3 5 9 10 12    x=4
void InsertSort(int* arr, int sz)
{
    int end;
    int x;
    while (end >= 0)
    {
        if (arr[end] > x)
        {
            arr[end + 1] = arr[end];
            end--;
        }
        else
        {
            break;
        }
    }
    arr[end + 1] = x;//插入在最头上和插入在中间都在这里处理
}

整个数组排序,如何控制呢?我们把上面的x赋值给arr[ end +1 ] 然后重复插入就是这样:

1.1.2完整插入排序代码:

 
void InsertSort(int* arr, int sz)
{
    assert(arr != NULL);
    for (int i = 0;i <= sz - 2;i++)
    {
        int end = i;//把数组第一个元素当作有序,像打扑克牌摸牌排序一样
        int x = arr[end + 1];
        //x已经保存了a[end + 1] 所以后面再覆盖也可以 因此end只能落在n-2
        while (end >= 0)
        {
            if (arr[end] > x)
            {
                arr[end + 1] = arr[end];
                end--;
            }
            else
            {
                break;
            }
        }
        arr[end + 1] = x;
    }
}

为了验证代码,我们像以前一样分文件写,先把部分Sort.c和Test.c放出来,后面再把完整的放出来

 
#include"Sort.h"
先写打印数组函数和交换函数(后面排序使用)
 
void printArr(int* arr, int sz)
{
    for (int i = 0;i <= sz - 1;i++)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
 
int main()
{
    int arr[] = { 1,6,5,4,7,8,9,2,0,3 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    printArr(arr, sz);
 
    InsertSort(arr, sz);
    printArr(arr, sz);
    //输出:0 1 2 3 4 5 6 7 8 9
    return 0;
}

1.1.3插入排序复杂度分析

  直接插入排序最坏情况是逆序(每插入一个都要移动,从第二个元素开始,第二个元素需要移动1次,第三个元素需要移动2次,…,第n个元素需要移动n-1次)

  取最大项就是O(N^2).

  最好情况是已经有序或者基本有序,就只需要遍历一次数组(有序)或者偶尔几个元素需要移动几次格子再插入其他的直接插入在end所指元素后面就行(基本有序),故最好情况下时间复杂度是O(N)。

没有开辟额外的空间所以:插入排序的空间复杂度是O(1),时间复杂度是O(N^2)

我们之前写过冒泡排序

我们现在元素移动次数上进行分析,如果一组无序的数据通过冒泡排序排好序之后,

它的交换次数是这种数据的逆序度;对于插入排序来说也是一样的,

移动次数上都是原本数据的逆序度。

元素的移动次数是相同的,那我们接下来看看元素的交换次数。从代码上分析可以明显看出,

冒泡排序的一次交换需要三行代码,而插入排序的交换却需要一行,

所以总的交换次数冒泡排序大于插入排序。

有小伙伴会问,这两行的差别有那么大吗?移动一次,我们可以不计较,

如果数据很多,想想下,两者的效率差别很轻易的就比较出来了。

虽然冒泡排序的时间复杂度和插入排序的时间复杂度是相同的,

但是我们实际使用中还是优先选择插入排序。

对于插入排序还是可以优化的,对了,没错,就是下面的希尔排序

这里先说插入排序是比冒泡排序好的排序。(铺垫)


(我在最后的八大排序完整代码中放入了测试效率的测试,想测任何排序的时候可以去看看)


这里想到方便对比,所以讲完八大排序后再统一讲完八大排序的复杂度

1.2希尔排序

插入排序面对逆序或不太有序的情况下效率比较低,但是面对基本有序的情况它是非常棒的排序

基本有序的话时间复杂度是O(N),是排序算法的天花板,没有一个排序算法能比O(N)快)。

为了优化直接插入排序,一个叫希尔的人想出来了一种排序(希尔排序),核心思想:

  希尔排序就是在直接插入排序上优化,既然对基本有序的情况直接插入排序很棒,

那我先分成gap组进行一个预排序(这个过程可以使数组基本有序),

然后再进行一个直接插入排序,那么怎么样进行预排序呢?

预排序步骤:

1.2.1单趟预排序:

  按gap(缺口,缝隙,差距)分组,分成gap组,gap>1,对每个组进行插入排序,


使总体数组看起来接近有序


 实际上就是把0,0+gap,0+2gap…视为一组,1,1+gap,1+2gap…视为一组...


对每一组进行直接插入排序,这样每一组都是有序的了,总体数组就比之前有有序多了。


 那么对0,0+gap,0+2gap…这一组预排序的单趟排序代码如下(这里gap取3):

 
//分组的单趟和前面单趟插入排序一样,间距是gap,前面可以认为gap=1
//按gap分组进行预排序
    int gap = 3;
    int end = 0;
    int x = arr[end + gap];
    while (end >= 0)
    {
        if (arr[end] > x)
        {
            arr[end + gap] = arr[end];
            end -= gap;
        }
        else
        {
            break;
        }
    }
    arr[end + gap] = x;

1.2.2对所有组的预排序:

 
//依次排完gap组
int gap = 3;
for (int j = 0; j < gap; j++)
{
    for (int i = j; i < n - gap; i += gap)
    {
        int end = i;
        int x = arr[end + gap];
        while (end >= 0)
        {
            if (arr[end] > x)
            {
                arr[end + gap] = arr[end];
                end -= gap;
            }
            else
            {
                break;
            }
        }
        arr[end + gap] = x;
   }
}

上面的代码虽然清楚,但是不够简洁,我们可以对多组同时进行预排序

就好像把多组同时一锅炖了一样。对单趟多组预排序的代码改造如下:

1.2.3预排序代码简化:

 
int gap = 3;
for (int i = 0; i < n - gap; i++)
{
    int end = i;
    int x = arr[end + gap];
    while (end >= 0)
    {
        if (arr[end] > x)
        {
            //如果end所指的元素比x大
            //就把end所指元素往后移动,空出一个格子
            arr[end + gap] = arr[end];
            end -= gap;
        }
        else
        {
            //否则就跳出去,
            //这样可以同时处理end小于0的情况(插入在最头上的情况)
            break;
        }
    }
    arr[end + gap] = x;
}

怎么取gap呢?讨论一下预排序的时间复杂度


 与直接插入排序类似,最好情况是已经有序的时候,是O(N)(遍历一遍就行了)


 最坏情况:每一组都是逆序的,每一组的元素个数是[N/gap],这样的总共需要的循环次数是:gap*(1+2+3+…+[N/gap]-1)(套用最糟糕情况直接插入排序的循环次数,gap组)。


 观察这个总共需要的循环次数的函数,发现:


 gap越大 预排越快(gap=N,O(N)) ,但是因为分的组数太多了,排完后越接近无序;


 gap越小 预排越慢(gap=1,O(N^2)),分的组数少排完后越接近有序。


多趟分组预排序与最后的直接插入排序


 为了让最后进行插入排序的时候数组能更接近有序一些,我们可以加一个循环控制gap不断变化进行多趟分组预排序,并且把gap=1时,也就是最终进行直接插入排序耦合到while循环里,代码如下:

1.2.4完整希尔排序代码:

 
void ShellSort(int* arr, int sz)
{
    int gap = sz;
    //多次预排序(gap > 1)+直接插入排序(gap == 1)
    while (gap > 1)//gap进去以后才除所以大于1就行
    {
        //两种取gap的方法:
        //gap = gap / 2;//一次跳一半
        gap = gap / 3 + 1;
        //加一是为了保证最后一次gap小于3的时候
        //能够有gap等于1来表示直接插入排序
        //多组同时搞:
        for (int i = 0; i < sz - gap; i++)
        {
            int end = i;
            int x = arr[end + gap];
            while (end >= 0)
            {
                if (arr[end] > x)
                {
                    arr[end + gap] = arr[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            arr[end + gap] = x;
        }
    }
}

代码测试(依然输出0 1 2 3 4 5 6 7 8 9)

 
#include"Sort.h"
 
int main()
{
    int arr[] = { 1,6,5,4,7,8,9,2,0,3 };
    int sz = sizeof(arr) / sizeof(arr[0]);
    printArr(arr, sz);
 
    //InsertSort(arr, sz);
    ShellSort(arr, sz);
    printArr(arr, sz);
    return 0;
}

2.选择排序

2.1选择排序

  1. 在一个长度为 N 的无序数组中,第一次遍历 n-1 个数找到最小的和第一个数交换。
  2. 第二次从下一个数开始遍历 n-2个数,找到最小的数和第二个数交换。
  1. 重复以上操作直到第 n-1 次遍历最小的数和第 n-1 个数交换,排序完成。

2.1.1选择排序代码:

 
void SelectSort(int* arr, int sz)
{
    //先假设第一个元素最小
    for (int i = 0; i < sz; i++)
    {
        int begin = i;
        int minindex = i;
        while (begin < sz)
        {
            if (arr[begin] < arr[minindex])
            {
                minindex = begin;
            }
            begin++;
        }
        Swap(&arr[minindex], &arr[i]);
    }
}

2.1.2选择排序代码优化:

我们可以定义一个begin变量,一个end变量,用来记录数据首和尾的下标,我们一个可以找出两个值,一个最大值,一个最小值,最小值放在a[begin]中,最大值放在a[end]中,这样我们就比上面的快多了

 
void SelectSort(int* arr, int sz)
{
    int begin = 0;
    int end = sz - 1;
    while (begin < end)
    {
        int mini = begin;
        int maxi = end;
        int i = 0;
        for (i = begin;i <= end;i++)
        {
            //选出[begin,end]中最大和最小的
            if (arr[i] < arr[mini])
            {
                mini = i;
            }
            if (arr[i] > arr[maxi])
            {
                maxi = i;
            }
        }
        Swap(&arr[begin], &arr[mini]);
        //这里需要考虑第一个值放最大值的情况,如果第一个值为最大值,此时最大值位置被移动
        if (begin == maxi)
        {
            maxi = mini;//最大的值被换到了mini的位置,更新最大值的位置
        }
        Swap(&arr[end], & arr[maxi]);
        begin++;
        end--;
    }
}

2.2堆排序

要学习堆排序,首先要学习基础的二叉树结构,学习堆的向下调整算法,使用堆排序之前,

我们得先建一个堆出来,堆的向下调整算法的前提是:根节点的左右子树均是大堆或小堆。

由于堆排序在向下调整的过程中,需要从孩子中选择出较大或较小的那个孩子,

父亲才与孩子进行交换,所以堆排序是一种选择排序。

堆排序的详解请移至博客:

数据结构与算法⑫(第四章_中_续一)堆排序(详解)_GR C的博客-CSDN博客

2.1.1堆排序代码:

 
void justDown(int* arr, int sz, int father_idx)
{
    int child_idx = father_idx * 2 + 1; // 计算出左孩子的值(默认认为左孩子大)
    while (child_idx < sz) // 最坏情況:调到叶子(child_idx >= 数组范围时必然已经调到叶子)
    {
        if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx]))
        {   // 如果右孩子存在且右孩子比左孩子大
            child_idx = child_idx + 1;// 让其代表右孩子
        }
        if (arr[child_idx] > arr[father_idx])//如果孩子的值大于父亲的值(不符合大堆的性质)
        {
            Swap(&arr[child_idx], &arr[father_idx]);
            father_idx = child_idx;          // 更新下标往下走
            child_idx = father_idx * 2 + 1;  // 计算出该节点路线的新父亲
        }
        else // 如果孩子的值小于父亲的值(符合大堆的性质)
        {
            break;
        }
    }
}
 
//完整堆排序_升序
void HeapSort(int* arr, int sz)
{
    //创建大堆,选出最大的数,时间:O(N)
    int father = ((sz - 1) - 1) / 2;  // 计算出最后一个叶子节点的父亲
    while (father >= 0)
    {
        justDown(arr, sz, father);
        father--;
    }
 
    //交换后调堆  时间:O(N * logN)
    int end = sz - 1;
    while (end > 0)
    {
        Swap(&arr[0], &arr[end]);
        justDown(arr, end, 0);
        end--;
    }
}

数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)(中):https://developer.aliyun.com/article/1513587

目录
相关文章
TU^
|
2天前
|
搜索推荐 算法 测试技术
数据结构~~排序
数据结构~~排序
TU^
5 1
|
2天前
|
搜索推荐 算法 测试技术
数据结构——排序
数据结构——排序
|
3天前
|
存储 机器学习/深度学习 缓存
【数据结构】布隆过滤器原理详解及其代码实现
【数据结构】布隆过滤器原理详解及其代码实现
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
【经典LeetCode算法题目专栏分类】【第10期】排序问题、股票问题与TOP K问题:翻转对、买卖股票最佳时机、数组中第K个最大/最小元素
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
【经典LeetCode算法题目专栏分类】【第6期】二分查找系列:x的平方根、有效完全平方数、搜索二位矩阵、寻找旋转排序数组最小值
|
6天前
|
算法 搜索推荐 数据可视化
【漫画算法】指挥官的排序战术:快速排序算法解密
【漫画算法】指挥官的排序战术:快速排序算法解密
|
6天前
|
数据采集 算法 数据挖掘
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
LeetCode 题目 80:删除排序数组中的重复项 II【算法面试高频题】
|
10天前
|
搜索推荐 算法 Shell
数据结构和算法——排序算法的比较和排序综测测验
数据结构和算法——排序算法的比较和排序综测测验
6 0
|
1月前
|
存储 算法 Java
Java数据结构与算法-java数据结构与算法(二)
Java数据结构与算法-java数据结构与算法
125 1
|
10天前
|
算法 C语言
数据结构与算法——最小生成树问题(什么是最小生成树、Prim算法、Kruskal算法)
数据结构与算法——最小生成树问题(什么是最小生成树、Prim算法、Kruskal算法)
9 0