【学习笔记】数据结构(十)

内部排序

文章目录

  • 内部排序
    • 10.1 概述
    • 10.2 插入排序
      • 10.2.1 直接插入排序
      • 10.2.2 其他插入排序
        • 10.2.2.1 折半插入排序(Binary Insertion Sort)
        • 10.2.2.2 2-路插入排序(Two-Way Insertion Sort)
        • 10.2.2.3 表插入排序(Table Insertion Sort)
      • 10.2.3 希尔排序(Shell's Sort)
    • 10.3 交换排序
        • 10.3.1 冒泡排序(Bubble Sort)
        • 10.3.2 快速排序(Quick Sort)
    • 10.4 选择排序
      • 10.4.1 简单选择排序(Simple Selection Sort)
      • 10.4.2 树形选择排序(Tree Selection Sort)
      • 10.4.3 堆排序(Heap Sort)
    • 10.5 归并排序(Merging Sort)
    • 10.6 基数排序(Radix Sorting)
      • 10.6.1 多关键字的排序
      • 10.6.2 链式基数排序
    • 10.7 各种内部排序方法的比较讨论

10.1 概述

排序 :将一组杂乱无章的数据按一定规律顺次排列起来。即,将无序序列排成一个有序序列 (由小到大或由大到小) 的运算。

如果参加排序的数据结点包含多个数据域,那么排序往往是针对其中某个域而言。

排序方法分类

  • 按数据存储介质: 内部排序和外部排序

    • 内部排序:数据量不大、数据在内存,无需内外存交换数据
    • 外部排序:数据量较大、数据在外存(文件排序) —— 外部排序时,要将数据分批调入内存来排序,中间结果还要及时放入外存
  • 按比较器个数: 串行排序和并行排序

    • 串行排序:单处理机(同一时刻比较一对元素)
    • 并行排序:多处理机(同一时刻比较多对元素)
  • 按主要操作: 比较排序和基数排序

    • 比较排序:用比较的方法 —— 插入排序、交换排序、选择排序、归并排序
    • 基数排序:不比较元素的大小,仅仅根据元素本身的取值确定其有序位置。
  • 按辅助空间: 原地排序和非原地排序

    • 原地排序:辅助空间用量为O(1)的排序方法(所占的辅助存储空间与参加排序的数据量大小无关)·
    • 非原地排序:辅助空间用量超过O(1的排序方法(所占的辅助存储空间与参加排序的数据量大小有关)·
  • 按稳定性: 稳定排序和非稳定排序

    • 稳定排序:能够使任何数值相等的元素,排序以后相对次序不变。例如:直接插入排序

    • 非稳定性排序:数值相等的元素,排序以后相对次序改变。例如:简单选择排序

      排序方法是否稳定,并不能衡量一个排序算法的优劣。

  • 按自然性: 自然排序和非自然排序

    • 自然排序:输入数据越有序排序的速度越快的排序方法。
    • 非自然排序:输入数据越有序排序的速度慢的排序方法。

存储结构

  • 顺序表存储:待排序的一组记录存放在地址连续的一组存储单元上。记录之间的次序关系由其存储位置决定,则实现排 序必须借助移动记录

    # define MAXSIZE 20     // 设记录不超过20个
    typedef int KeyType;    // 设关键字为int型
    
    typedef struct {         //定义每个记录(数据元素)的结构
        KeyType key;         //关键字
        //InfoType otherinfo;  //其它数据项
    }RedType;
    
    
    typedef struct {   // 定义顺序表结构
        RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
        int length; //顺序表的长度
    }SqList;
    
  • 链表存储:待排序记录存放在静态链表中,记录之间的次序关系由 指针指示,则实现排序不需要移动记录,仅需修改指针即可;

  • 地址存储:待排序记录本身存储在一组地址连续的存储单元内,同时另设一个指示各个记录存储位置的地址向量,在排序过 程中不移动记录本身,而移动地址向量中这些记录的“地址",在排序结束之后再按照地址向量中的值调整记录的存储位置。

10.2 插入排序

插入排序:

在有序序列中插入一个元素,保持序列有序,有序长度不断增加。

有序插入方法:

  • 在插入a[i]前,数组a的前半段(a[0]~a[i-1])是有序段, 后半段(a[i]~a[n-1])是停留于输入次序的“无序段“
  • 插入a[i]使a[0]~a[i-1]有序,也就是要为a[i]找到有序位置j (0≤j≤i) ,将a[i]插入在a[j]的位置上。

在这里插入图片描述

根据找插入位置方法不同分为:

  • 顺序法定位插入位置:直接插入排序
  • 二分法定位插入位置:二分插入排序
  • 缩小增量多遍插入排序:希尔排序

10.2.1 直接插入排序

实现排序的基本操作有两个:

​ (1) “比较”序列中两个关键字的大小;

​ (2) “移动”记录。

在这里插入图片描述

#include<stdio.h>

# define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型

typedef struct {         //定义每个记录(数据元素)的结构
    KeyType key;         //关键字
}RedType;


typedef struct {   // 定义顺序表结构
    RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
    int length; //顺序表的长度
}SqList;

void InsertSort(SqList* L)
{
    int i, j;
    for (i = 2; i <= L->length; i++)
    {
        if (L->r[i].key < L->r[i - 1].key) //后面比前面数小,则需要进行排序
        {
            L->r[0] = L->r[i]; // 复制插入元素到哨兵

            //记录后移,寻找插入位置
            L->r[i] = L->r[i - 1];
            for (j = i - 2; L->r[0].key < L->r[j].key; j--)
            {
                L->r[j + 1] = L->r[j];
            }

            //插人到正确位置
            L->r[j + 1] = L->r[0];
        }
        //后面数大于等于前面数,只需继续循环,比较下一个数
    }
}

int main()
{
    int i;
    int r[7] = {32,12,24,5,16,43,20};
    SqList L;
    L.length = 7;
    for (i = 0; i < 7; i++)
    {
        L.r[i + 1].key = r[i];
    }
    InsertSort(&L);
    for (i = 0; i < 7; i++)
    {
        printf("%d ", L.r[i + 1].key);
    }
    return 0;
}

n个元素

最好情况:顺序有序

  • 比较次数: ∑ i = 2 n 1 = n − 1 \sum_{i=2}^{n}1 = n-1 i=2n1=n1
  • 移动次数:0
  • 时间复杂度 O(n)

最坏情况:逆序有序

  • 比较次数(平均值): ∑ i = 2 n i = ( n + 2 ) ( n − 1 ) 2 \sum_{i=2}^{n}i = \frac{(n+2)(n-1)}{2} i=2ni=2(n+2)(n1)

  • 移动次数(平均值): ∑ i = 2 n ( i + 1 ) = ( n + 4 ) ( n − 1 ) 2 \sum_{i=2}^{n}(i+1) = \frac{(n+4)(n-1)}{2} i=2n(i+1)=2(n+4)(n1)

  • 时间复杂度 O(n2)

平均情况:

  • 比较次数(平均值): ∑ i = 2 n i + 1 2 = ( n + 2 ) ( n − 1 ) 4 \sum_{i=2}^{n}\frac{i+1}{2} = \frac{(n+2)(n-1)}{4} i=2n2i+1=4(n+2)(n1)
  • 移动次数(平均值): ∑ i = 2 n ( i + 1 2 + 1 ) = ( n + 6 ) ( n − 1 ) 4 \sum_{i=2}^{n}(\frac{i+1}{2}+1) = \frac{(n+6)(n-1)}{4} i=2n(2i+1+1)=4(n+6)(n1)
  • 时间复杂度 O(n2) - 最坏的情况的一半

空间复杂度:O(1)

稳定性:稳定

原始数据越接近有序,排序速度越快

10.2.2 其他插入排序

10.2.2.1 折半插入排序(Binary Insertion Sort)

插入排序的基本操作是在一个有序表中进行查找和插入,这个==“查找“操作可利用“折半查找”==来实现,再进行插入,则称之为折半插入排序(Binary Insertion Sort)

#include<stdio.h>

# define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型

typedef struct {         //定义每个记录(数据元素)的结构
    KeyType key;         //关键字
}RedType;


typedef struct {   // 定义顺序表结构
    RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
    int length; //顺序表的长度
}SqList;

void BInsertSort(SqList* L)
{
    int i, j;
    for (i = 2; i <= L->length; i++)
    {
        L->r[0] = L->r[i]; // 复制插入元素到哨兵
        int low = 1;
        int high = i - 1;
        while (low <= high) { //在 r[low.. high]中折半查找有序插入的位置
            int m = (low + high) / 2; // 折半
            if (L->r[0].key < L->r[m].key) //插入点在低半区
            {
                high = m - 1;
            }
            else { //插入点在高半区
                low = m + 1;
            }
        }//循环结束,high+1 则为插入位置
        for (j = i - 1; j>=high+1; j--)
        {
            L->r[j + 1] = L->r[j]; //记录后移
        }
        L->r[high + 1] = L->r[0]; // 插入
    }
}

int main()
{
    int i;
    int r[7] = {32,12,24,5,16,43,20};
    SqList L;
    L.length = 7;
    for (i = 0; i < 7; i++)
    {
        L.r[i + 1].key = r[i];
    }
    BInsertSort(&L);
    for (i = 0; i < 7; i++)
    {
        printf("%d ", L.r[i + 1].key);
    }
    return 0;
}

折半插入排序特点:

  • 折半查找比顺序查找快,
  • 关键码比较次数与待排座对象序列的初始排列无关,仅依赖于对象个数。
  • 当n较大时,总关键码比较次数比直接插入排序的最坏情况要好得多,但比其最好情况要差;
  • 在对象的初始排列已经按关键码排好序或接近有序时,直接插入排序比折半插入排序执行的关键码比较次数要少;
  • 平均性能优于直接插入排序

n个元素

折半插入排序仅减少了关键字间的比较次数,而记录的移动次数不变

时间复杂度:仍为O(n2),

空间复杂度:O(1)

稳定性:稳定

10.2.2.2 2-路插入排序(Two-Way Insertion Sort)

2- 路插入排序是在折半插入排序的基础上再改进之,其目的是减少排序过程中移动 记录的次数,但为此需要n个记录的辅助空间。

  • 初始化一个与原数组一样大小的辅助数组d,并将原数组的第一个元素放入辅助数组的第一个位置。
  • 将d看成是一个循环向量,并设两个指针 first 和 final分别指示排序过程中得到的有序序列中的第一个和最后一个记录在d中的位置。
  • 从第二个元素开始遍历原数组,对于每个待排序元素:
    • 如果待排序元素小于辅助数组的最小值,则通过移动first将其插入到最小值之前。
    • 如果待排序元素大于辅助数组的最大值,则过移动final将其插入到最大值之后。
    • 否则,通过移动final将大于的数值向后移动并将待排序元素插入到适当的位置。
  • 处理完所有元素后,将辅助数组中的元素复制回原数组,完成排序。
#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型

typedef struct {         //定义每个记录(数据元素)的结构
    KeyType key;         //关键字
}RedType;

typedef struct {   // 定义顺序表结构
    RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
    int length; //顺序表的长度
}SqList;

void TwoWayInsertSort(SqList* L) {
    /* 初始化一个与原数组一样大小的辅助数组 */
    RedType* d;
    d = (RedType*)malloc((L->length) * sizeof(RedType));
    if (d == NULL) {
        return;
    }
    /* 设L的第1个记录为d中排好序的记录(在位置[0]) */
    d[0] = L->r[1];

    /* first、final分别指示d中排好序的记录的第1个和最后1个记录的位置 */
    int first, final;
    first = final = 0;

    int i, j;
    /* 依次将L的第2个~最后1个记录插入d中 */
    for (i = 2; i <= L->length; i++) {
        if (L->r[i].key < d[first].key) {
            /* 待插记录小于d中最小值,插到d[first]之前(不需移动d数组的元素) */
            first = (first - 1 + L->length) % L->length;
            d[first] = L->r[i];
        }
        else if (L->r[i].key > d[final].key) {
            /* 待插记录大于d中最大值,插到d[final]之后(不需移动d数组的元素) */
            final++;
            d[final] = L->r[i];
        }
        else {
            /* 待插记录大于d中最小值,小于d中最大值,插到d的中间(需要移动d数组的元素) */
            j = final++;
            while (L->r[i].key < d[j].key)
            {
                d[(j + 1) % L->length] = d[j];
                j = (j - 1 + L->length) % L->length;
            }
            d[j + 1] = L->r[i];
        }
    }

    for (i = 1; i <= L->length; i++) { // 修改循环条件
        L->r[i] = d[i - 1]; // 将排序后的元素放回L中
    }

    for (i = 1; i <= L->length; i++) { // 输出排序后的L
        printf("%d ", L->r[i].key);
    }
    printf("\n");
    printf("在L中first: %d \n", first + 1);
    printf("在L中final: %d ", final + 1);

    free(d); // 释放内存
}

int main() {
    int i;
    int r[8] = { 49,38,65,97,76,13,27,49 };
    SqList L;
    L.length = 8;
    for (i = 1; i <= L.length; i++) {
        L.r[i].key = r[i - 1];
    }
    TwoWayInsertSort(&L);

    return 0;
}

n个元素

‌时间复杂度‌:2-路插入排序的时间复杂度为O(n2),移动次数大约为n2/8次,尽管减少了移动次数,但并不能完全避免移动操作。

‌空间复杂度‌:需要额外的辅助数组,空间复杂度为O(n)。

10.2.2.3 表插入排序(Table Insertion Sort)

在排序过程中不移动记 录,只有改变存储结构

算法思路:

  • 初始化表头结点:设数组中下标为"0"的分量为表头结点,并令表头结点记录的关键字取最大整数 MAXINT
  • 表插入排序的过程:
    • 首先将静态链表中数组下标为"1"的分量(结点)和表头结点构成一个循环链表
    • 然后依次将下标为"2"至"n"的分量(结点)按记录关键字非递减有序插人到循环链表中

在这里插入图片描述

#include<stdio.h>
#include<limits.h>

#define MAXSIZE 20     // 设记录不超过20个
#define MAXVALUE INT_MAX  // 定义最大值

typedef struct SLNode {
    int data;  // 存储数据
    int link;  // 存储指向下一个元素的索引
}SLNode, Table[MAXSIZE];

void TableInsertSort(Table* tb, int n)
{
    //与第一个数据元素构成循环列表
    (*tb)[0].link = 1;  // 初始化顺序表的头结点,将其link指向第一个数据元素
    
    int p, q; // 用于在排序过程中存储当前元素和前驱元素的索引
    
    for (int i = 2; i < n; i++) // 从第二个元素开始遍历
    {
        p = (*tb)[0].link; 
        q = 0;
        while (p != 0 && (*tb)[p].data <= (*tb)[i].data)
        {
            q = p; //q是p的前驱
            p = (*tb)[p].link; // p更新为下一个元素的索引
        }
        (*tb)[i].link = (*tb)[q].link; // 将i插入到q的后面
        (*tb)[q].link = i; // 更新q的link,使其指向i
    }
}


int main() {
    int i;
    int r[9] = { 0,49,38,65,97,76,13,27,49 };
    Table tb;
    // 初始化表头结点:
    tb[0].data = MAXVALUE;
    tb[0].link = 0;
    for (i = 1; i < 9; i++)
    {
        tb[i].data = r[i];
        tb[i].link = 0;
    }
    
    TableInsertSort(&tb, 9);
    
    for (i = 0; i < 9; i++)
    {
        if (tb[i].data == MAXVALUE)
        {
            printf("%c ", 'M');
            continue;
        }
        printf("%d ", tb[i].data);
    }
    printf("\n");
    for (i = 0; i < 9; i++)
    {
        printf("%d ", tb[i].link);
    }

    return 0;
}

10.2.3 希尔排序(Shell’s Sort)

又称“缩小增量排序"(Diminishing Increment Sort)

基本思想: 先将整个待排记录序列分割成为若干子序列分别进行直接插入排 序,待整个序列中的记录“基本有序”时,再对全体记录进行一次直接插入排序。

  • 选择一个增量序列 Dk:DM > DM-1 > … > D1 = 1 必须递减
  • 对每个Dk进行“Dk-间隔”插入排序(K= M,M-1,…1)

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型

typedef struct {         //定义每个记录(数据元素)的结构
    KeyType key;         //关键字
}RedType;

typedef struct {   // 定义顺序表结构
    RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
    int length; //顺序表的长度
}SqList;

void ShellInsert(SqList* L, int dk)
{
    int i, j;
    for (i = dk + 1; i <= L->length; i++)// 从第dk+1个元素开始向后遍历顺序表
    { 
        if (L->r[i].key < L->r[i - dk].key)
         // 如果当前元素的key小于它dk位置前的元素的key
        {            
            L->r[0] = L->r[i];// L->r[0]是暂存单元,暂存当前元素
            for (j = i - dk; j > 0 && (L->r[0].key < L->r[j].key); j = j - dk)
            {// 从当前元素向前遍历,步长为dk
                L->r[j + dk] = L->r[j]; // 将比暂存元素大的元素向后移动dk个位置
            }
            L->r[j + dk] = L->r[0]; // 将暂存的元素插入到正确的位置
        }
    }
}

void ShellSort(SqList *L, int dlta[], int t) 
{
    int i, k;
    for (k = 0; k < t; k++)
    {
        ShellInsert(L, dlta[k]);
        printf("\n第 D%d 增量序列排序结果:\n", dlta[k]);
        for (i = 1; i <= 13; i++)
        {
            printf("%d ", L->r[i].key);
        }
    }
}

int main() {
    int i;
    int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
    SqList L;
    L.length = 13;
    for (i = 1; i <= L.length; i++) {
        L.r[i].key = r[i - 1];
    }
    // 增量序列
    int dlta[3] = { 5,3,1 };
    ShellSort(&L, dlta, 3);
    printf("\n-----------------\n");
    printf("排序结果:\n");
    for (i = 1; i <= 13; i++)
    {
        printf("%d ", L.r[i].key);
    }
    return 0;
}

希尔排序算法效率与增量序列的取值有关

Hibbard增量序列

  • Dk = 2 k-1 —— 相邻元素互质
  • 最坏: Tworst = O(n3/2)
  • 猜想: Tavg = O(n5/4)

Sedgewick增量序列

  • {1,5,19,41,109,……} —— 9 * 4i - 9 * 2i + 1 或 4i - 3 * 2i + 1
  • 最坏: Tworst = O(n4/3)
  • 猜想: Tavg = O(n7/6)

稳定性:不稳定

时间复杂度:O(n1.25) ~ O(1.6n1.25) – 经验公式

​ 最好:O(n)

​ 最坏:O(n2)

​ 最好:~O(n1.3)

空间复杂度:O(1)

不宜在链式存储结构上实现

10.3 交换排序

交换排序:两两比较,如果发生逆序则交换,直到所有记录都排好序为止。

10.3.1 冒泡排序(Bubble Sort)

基本思想: 每趟不断将记录两两比较,并按“前小后大”规则交换

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型

typedef struct {         //定义每个记录(数据元素)的结构
    KeyType key;         //关键字
}RedType;

typedef struct {   // 定义顺序表结构
    RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
    int length; //顺序表的长度
}SqList;


void bubble_sort(SqList *L) 
{
    int i, j;
    RedType x; // 交换时临时存储
    for (i = 1; i <= L->length - 1; i++) // 需要比较i趟,n个记录 总共n-1趟
    {
        for (j = 1; j <= L->length - i; j++) // 每一趟需要比较的次数,n个记录,比较n-i次
        {
            if (L->r[j].key > L->r[j + 1].key) // 比较 
            {
                //发生逆序 - 交换
                x = L->r[j]; 
                L->r[j] = L->r[j + 1];
                L->r[j + 1] = x;
            }
        }
        printf("\n第 %d 趟排序结果:\n", i);
        for (j = 1; j <= L->length; j++)
        {
            printf("%d ", L->r[j].key);
        }

    }
}

int main() {
    int i;
    int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
    SqList L;
    L.length = 13;
    for (i = 1; i <= L.length; i++) {
        L.r[i].key = r[i - 1];
    }
    bubble_sort(&L);
    printf("\n-----------------\n");
    printf("排序结果:\n");
    for (i = 1; i <= 13; i++)
    {
        printf("%d ", L.r[i].key);
    }
    return 0;
}

改进:冒泡处理过程中,没有进行任何交换,说明序列已有序,则停止交换

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型

typedef struct {         //定义每个记录(数据元素)的结构
    KeyType key;         //关键字
}RedType;

typedef struct {   // 定义顺序表结构
    RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
    int length; //顺序表的长度
}SqList;


void bubble_sort(SqList *L) 
{
    int i, j;
    int flag = 1;
    RedType x; // 交换时临时存储
    for (i = 1; (i <= L->length - 1) && (flag == 1); i++) // 需要比较i趟,n个记录 总共n-1趟
    {
        flag = 0;
        for (j = 1; j <= L->length - i; j++) // 每一趟需要比较的次数,n个记录,比较n-i次
        {
            if (L->r[j].key > L->r[j + 1].key) // 比较 
            {
                flag = 1;
                //发生逆序 - 交换
                x = L->r[j]; 
                L->r[j] = L->r[j + 1];
                L->r[j + 1] = x;
            }
        }
        printf("\n第 %d 趟排序结果:\n", i);
        printf("flag = %d \n", flag);
        for (j = 1; j <= L->length; j++)
        {
            printf("%d ", L->r[j].key);
        }

    }
}

int main() {
    int i;
    int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
    SqList L;
    L.length = 13;
    for (i = 1; i <= L.length; i++) {
        L.r[i].key = r[i - 1];
    }
    bubble_sort(&L);
    printf("\n-----------------\n");
    printf("排序结果:\n");
    for (i = 1; i <= 13; i++)
    {
        printf("%d ", L.r[i].key);
    }
    return 0;
}

最好情况:正序

  • 比较次数:n-1
  • 移动次数:0
  • 时间复杂度 O(n)

最坏情况:逆序

  • 比较次数(平均值): ∑ i = 1 n − 1 ( n − i ) = ( n 2 − n ) 2 \sum_{i=1}^{n-1}(n - i) = \frac{(n^2-n)}{2} i=1n1(ni)=2(n2n)

  • 移动次数(平均值): 3 ∑ i = 1 n − 1 ( n − i ) = 3 ( n 2 − n ) 2 3\sum_{i=1}^{n-1}(n - i) = \frac{3(n^2-n)}{2} 3i=1n1(ni)=23(n2n)

  • 时间复杂度 O(n2)

平均情况:

  • 时间复杂度 O(n2)

空间复杂度:O(1)

稳定性:稳定

10.3.2 快速排序(Quick Sort)

基本思想:

  • 任取一个元素 (如:第一个) 为中心pivot - 可以是第一个数、最后一个数、最中间一个数、任选一个数等

  • 所有比它小的元素一律前放,比它大的元素一律后放形成左右两个子表;

  • 对各子表重新选择中心元素并依此规则调整 【递归思想

  • 直到每个子表的元素只剩一个

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型

typedef struct {         //定义每个记录(数据元素)的结构
    KeyType key;         //关键字
}RedType;

typedef struct {   // 定义顺序表结构
    RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
    int length; //顺序表的长度
}SqList;

int Partition(SqList* L, int low, int high)
{
    int pivotkey = L->r[low].key; //任取一个元素 (第一个) 为中心pivot
    L->r[0] = L->r[low];  // 将中心pivot放到0处
    while (low < high)
    {
        while (low < high && L->r[high].key >= pivotkey) // high >= 中心  ,移动high向前
        {
            --high;
        }
        L->r[low] = L->r[high]; //high < 中心, 把该值移动到low那一侧
        while (low < high && L->r[low].key <= pivotkey)// low <= 中心  ,移动low向后
        {
            ++low;
        }
        L->r[high] = L->r[low];//low > 中心, 把该值移动到high那一侧
    }
    L->r[low] = L->r[0]; // 中心放到对应位置
    return low;
}

void QSort(SqList *L, int low, int high) 
{
    if (low < high)//长度大于1
    {
        int pivotloc = Partition(L, low, high); //将L.r[low .. high]一分为二
        printf("low = %d, high = %d, pivotloc = %d\n", low, high, pivotloc);
        for (int i = 1; i <= 13; i++)
        {
            printf("%d ", L->r[i].key);
        }
        printf("\n-----------------\n");
        QSort(L, low, pivotloc - 1); //对低子表递归排序
        QSort(L, pivotloc + 1, high);  //对高子表递归排序,
    }
}

int main() {
    int i;
    int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
    SqList L;
    L.length = 13;
    for (i = 1; i <= L.length; i++) {
        L.r[i].key = r[i - 1];
    }
    QSort(&L,1, L.length);
    printf("排序结果:\n");
    for (i = 1; i <= 13; i++)
    {
        printf("%d ", L.r[i].key);
    }
    return 0;
}

划分元素的选取是影响时间性能的关键

最好情况:

  • 时间复杂度 O(nlogn)

最坏情况:

  • 时间复杂度 O(n2)

平均情况:

  • 时间复杂度:O(nlogn)

​ QSort():O(logn)

​ Partition():O(n)

空间复杂度:

​ 平均情况:O(logn)

​ 最坏情况:O(n)

稳定性:不稳定

快速排序不适于对原本有序或基本有序(包括正序和逆序)的记录序列进行排序,退化成冒泡排序

10.4 选择排序

10.4.1 简单选择排序(Simple Selection Sort)

基本思想: 在待排序的数据中选出最大(小)的元素放在其最终的位置。

基本操作:

  • 首先通过n-1次关键字比较,从n个记录中找出关键字最小的记录,将它与第一个记录交换
  • 再通过n-2次比较,从剩余的n-1个记录中找出关键字次小的记录,将它与第二个记录交换
  • 重复上述操作,共进行n-1趟排序后,排序结束
#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为int型

typedef struct {         //定义每个记录(数据元素)的结构
    KeyType key;         //关键字
}RedType;

typedef struct {   // 定义顺序表结构
    RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
    int length; //顺序表的长度
}SqList;


void SelectSort(SqList* L)
{
    int i, j, k;
    for (i = 1; i < L->length; i++)
    {
        k = i; 
        for (j = i + 1; j <= L->length; j++)
        {
            if (L->r[j].key < L->r[k].key)
            {
                k = j;
            }
        }
        if (k != i)
        {
            L->r[0] = L->r[k];
            L->r[k] = L->r[i];
            L->r[i] = L->r[0];
        }
        printf("\n第 %d 次排序结果:\n", i);
        for (j = 1; j <= L->length; j++)
        {
            printf("%d ", L->r[j].key);
        }
    }
}

int main() {
    int i;
    int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
    SqList L;
    L.length = 13;
    for (i = 1; i <= L.length; i++) {
        L.r[i].key = r[i - 1];
    }
    SelectSort(&L);
    printf("\n-----------------\n");
    printf("排序结果:\n");
    for (i = 1; i <= 13; i++)
    {
        printf("%d ", L.r[i].key);
    }
    return 0;
}

时间复杂度 - O(n2):

  • 移动次数

    • 最好情况:0
    • 最坏情况:3(n-1)
  • 比较次数:

    • 最好情况:O(n2)
    • 最坏情况:O(n2)
    • 平均情况:O(n2)

    ∑ i = 1 n − 1 ( n − i ) = n ( n − 1 ) 2 \sum_{i=1}^{n-1}(n - i) = \frac{n(n-1)}{2} i=1n1(ni)=2n(n1)

空间复杂度:O(1)

稳定性:不稳定

10.4.2 树形选择排序(Tree Selection Sort)

又称锦标赛排序(Tournament Sort)

基本思想: 首先对n个记录的关键字进行两两比较,然后在 其中⌈ n / 2⌉个较小者之间再进行两两比较,如此重复,直至选出最小关键字的记录为止。

10.4.3 堆排序(Heap Sort)

若n个元素的序列{a1,a2,…, an}满足 ai ≤ a2i && ai ≤ a2i+1 则称该序列为小根堆

若n个元素的序列{a1,a2,…, an}满足 ai ≥ a2i && ai ≥ a2i+1 则称该序列为大根堆

从堆的定义可以看出,堆实质是满足如下性质的完全二叉树:二又树中任一非叶子结点均小于(大于)它的孩子结点

堆排序: 若在输出堆顶的最小值(最大值)后,使得剩余n-1个元素的序列重又建成一个堆,则得到n个元素的次小值(次大值)…如此反复,便能得到一个有序序列。【堆顶就是最小值(最大值),每次都取堆顶,就可得到一个有序序列】

堆序列需解决两个问题:

  • 如何由无序序列建成一个堆?

    1. 单结点的二又树是堆

    2. 在完全二叉树中所有以叶子结点(序号i>n/2【最后一个结点是n,那么他的双亲是n/2,所以叶子结点是 > n/2】)为根的子树是堆。

    3. 只需依次将以序号为n/2,n/2 - 1,… 1的结点为根的子树均调整为堆即可。

    在这里插入图片描述

  • 如何在输出堆顶元素后,调整剩余元素为一个新的堆?

    小根堆:

    1. 输出堆顶元素之后,以堆中最后一个元素【编号最大的元素】替代之;

    2. 然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换

    3. 重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的调整过程为“筛选

    在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>

#define MAXSIZE 20     // 设记录不超过20个
typedef int KeyType;    // 设关键字为 int 型

typedef struct {         //定义每个记录(数据元素)的结构
    KeyType key;         //关键字
}RedType;

typedef struct {   // 定义顺序表结构
    RedType r[MAXSIZE + 1]; //r[0]作为缓冲区或哨兵
    int length; //顺序表的长度
}SqList;
typedef SqList HeapType; // 堆采用顺序表存储表示

/*大根堆*/
void HeapAdjust_big(HeapType* H, int s, int m)
{
    //调整R[s]关键字,使R[s...m]成为一个大根堆
    RedType rc = H->r[s];
    int j;
    for (j = 2 * s; j <= m; j *= 2)
    {
        // H->r[j]和 H->r[j + 1]分别代表H->r[s]的左子结点和右子结点,比较出两者之间最大值
        if (j < m && H->r[j].key < H->r[j + 1].key)
        {
            ++j;
        }
        //再和比较H->r[s]比较最大值
        if (rc.key >= H->r[j].key)
        {
            //H->r[s]最大,即无需改动位置
            break;
        }
        H->r[s] = H->r[j];
        s = j;
    }
    H->r[s] = rc;//插入
}

/*小根堆*/
void HeapAdjust_small(HeapType* H, int s, int m)
{
    //调整R[s]关键字,使R[s...m]成为一个小根堆
    RedType rc = H->r[s];
    int j;
    for (j = 2 * s; j <= m; j *= 2)
    {
        if (j < m && H->r[j].key > H->r[j + 1].key)
        {
            ++j;
        }
        if (rc.key <= H->r[j].key)
        {
            break;
        }
        H->r[s] = H->r[j];
        s = j;
    }
    H->r[s] = rc;
}

void HeapSort(HeapType* H)
{
    //对顺序表H进行堆排序
    int i;
    for (i = H->length / 2; i > 0; i--)  //建初始堆 从 i = H->length / 2 往前到1
    {
        HeapAdjust_small(H, i, H->length);
    }
    for (i = H->length; i > 1; i--)  //进行n-1趟排序
    {
        printf("%d ", H->r[1].key);
        //根与最后一个元素交换
        H->r[0] = H->r[i];
        H->r[i] = H->r[1];
        H->r[1] = H->r[0];
        //对R[1]到R[i-1]重新建堆
        HeapAdjust_small(H, 1, i-1);
    }
}


int main() {
    int i;
    int r[13] = { 81,94,11,96,12,35,17,95,28,58,41,75,15 };
    HeapType H;
    H.length = 13;
    for (i = 1; i <= H.length; i++) {
        H.r[i].key = r[i - 1];
    }
    printf("排序结果:\n");
    HeapSort(&H);
    return 0;
}

时间复杂度:

  • 初始堆化所需时间不超过O(n)
  • 排序阶段(不含初始堆化)
    • 一次重新堆化所需时间不超过O(logn)
    • n-1次循环所需时间不超过O(nlogn)
  • Tw(n)=0(n)+ O(nlogn)= O(nlogn) —— 最好情况、最坏情况、平均情况

空间复杂度:O(1)

稳定性:不稳定

不适用于待排序记录个数n较少的情况,但对于n较大的文件还是很有效的。

10.5 归并排序(Merging Sort)

基本思想:将两个或两个以上的有序子序列“归并”为一个有序序列,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题 分(divide) 成一些小的问题然后递归求解,而 治(conquer) 的阶段则将分的阶段得到的各答案"修补"在一起,即分而治之)。

通常采用2-路归并排序:将两个位置相邻的有序子序列R[l…]m]和R[m+1…]n] 归并为一个有序序列R[l…n]

整个归并排序仅需 ⌈log2n⌉

在这里插入图片描述

#include<stdio.h>
#include<stdlib.h>

void Merge(int* arr, int left, int mid, int right) {
    int* temp = (int*)malloc((right - left + 1) * sizeof(int));
    /* 
    i => [left, mid]
    j => [mid + 1, right]
    */
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        }
        else {
            temp[k++] = arr[j++];
        }
    }

    while (i <= mid) {
        temp[k++] = arr[i++];
    }

    while (j <= right) {
        temp[k++] = arr[j++];
    }

    for (i = left, k = 0; i <= right; i++, k++) {
        arr[i] = temp[k];
    }

    free(temp);
}

void MergeSort(int* arr, int left, int right) {
    if (left >= right) {
        return;
    }
    int mid = (left + right) / 2;
    MergeSort(arr, left, mid);
    MergeSort(arr, mid + 1, right);
    Merge(arr, left, mid, right);
}


void printArray(int* arr, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = { 81, 94, 11, 96, 12, 35, 17, 95, 28, 58, 41, 75, 15 };
    int n = sizeof(arr) / sizeof(arr[0]);
    MergeSort(arr, 0, n - 1);
    printArray(arr, n);
    return 0;
}

在这里插入图片描述

时间复杂度:O(nlogn) —— 最好情况、最坏情况、平均情况

空间复杂度:O(n)

稳定性:稳定

10.6 基数排序(Radix Sorting)

10.6.1 多关键字的排序

基本步骤:

  1. 确定每个关键字的优先级
  2. 对每个关键字进行排序
  3. 根据优先级合并排序结果

关键字的次序:K0, K1, … , Kd-1

最主位关键字:K0

最次位关键字:Kd-1

最高位优先 (Most Significant Digit first)法,简称 MSD 法

  • 先对最主位关键字 K0 进行排序,将序列分成若干子序列,每个子序 列中的记录都具有相同的K0值,

  • 然后分别就每个子序列对关键字 K1 进行排序,按K1值 不同再分成若干更小的子序列,

  • 依次重复,

  • 直至对 Kd-2 进行排序之后得到的每一子序列 中的记录都具有相同的关键字(K0, K1, … , Kd-2),

  • 而后分别每个子序列对 Kd-1 进行排 序,最后将所有子序列依次联接在一起成为一个有序序列

在这里插入图片描述

最低位优先 (Least Significant Digit first) 法,简称 LSD 法

  • 从最次位关键字 Kd-1 起进行排序。
  • 然后再对高一位的关键字 Kd-2 进行排序,
  • 依次重复,
  • 直至对 K0 进行排序后便成 为一个有序序列

在这里插入图片描述

/*--------------使用LSD基数排序算法---------------*/
/* K 由 3个关键字(K0,0K1 ,K2)组成,其中 K0 是百位数,K1 是十位数,K2 是个位数;*/

#include<stdio.h>
#include<stdlib.h>

// 定义最大数字的位数
#define MAX_DIGITS 3  // 3位数字,百位、十位、个位

// 定义桶的大小
#define BUCKET_SIZE 10   // 10个桶,分别对应0-9

/**
 * 函数:分配数据到桶中
 * @param data 要排序的数据数组
 * @param bucket 桶数组,用于统计每个数字出现的次数
 * @param n 数据数组的长度
 * @param digit 当前正在处理的位数(1、10、100)
 */
void distribute(int* data, int* bucket, int n, int digit) {
    int i;
    // 遍历数据数组,统计每个数字在当前位数上的值
    for (i = 0; i < n; i++) {
        // 计算当前数字在当前位数上的值
        int index = (data[i] / digit) % 10;
        // 将该值对应的桶计数加1
        bucket[index]++;
    }
}

/**
 * 函数:收集数据从桶中
 * @param data 要排序的数据数组
 * @param bucket 桶数组,用于统计每个数字出现的次数
 * @param temp 临时数组,用于存储收集的数据
 * @param n 数据数组的长度
 * @param digit 当前正在处理的位数(1、10、100)
 */
void collect(int* data, int* bucket, int* temp, int n, int digit) {
    int i, j = 0;
    // 遍历桶数组,收集数据
    for (i = 0; i < BUCKET_SIZE; i++) {
        // 循环直到该桶的计数为0
        while (bucket[i] > 0) {
            // 遍历数据数组,找到对应的数字
            for (int k = 0; k < n; k++) {
                // 如果当前数字在当前位数上的值与桶的索引相等
                if ((data[k] / digit) % 10 == i) {
                    // 将该数字收集到临时数组中
                    temp[j] = data[k];
                    j++;
                    // 将桶的计数减1
                    bucket[i]--;
                }
            }
        }
    }
    // 将收集的数据复制回原始数据数组
    for (i = 0; i < n; i++) {
        data[i] = temp[i];
    }
}

// 函数:基数排序
void radixSort(int* data, int n) {
    int digit = 1;
    int* temp = (int*)malloc(n * sizeof(int));
    int bucket[BUCKET_SIZE] = { 0 };
    // 进行MAX_DIGITS次分配和收集
    for (int i = 0; i < MAX_DIGITS; i++) {
        // 分配数据到桶中
        distribute(data, bucket, n, digit);
        // 收集数据从桶中
        collect(data, bucket, temp, n, digit);
        // 将位数乘以10(下一位)
        digit *= 10;
        // 重置桶数组
        for (int j = 0; j < BUCKET_SIZE; j++) {
            bucket[j] = 0;
        }
        // 打印当前的数据状态
        printf("第 %d 趟分配 + 收集后的数据:\n", i);
        for (int i = 0; i < n; i++) {
            printf("%d ", data[i]);
        }
        printf("\n");
    }
}

// 主函数
int main() {
    int data[] = { 278, 109, 63, 930, 589, 184, 505, 269, 8, 83};
    int n = sizeof(data) / sizeof(data[0]);
    radixSort(data, n);    
    return 0;
}

10.6.2 链式基数排序

基数排序是借助 “分配“和“收集“ 两种操作对单逻辑关键字进行排序,并用链表作存储结构 的一种内部排序 方法。

基本步骤:

  1. 将数据分成多个桶,每个桶对应一个基数位
  2. 对每个桶进行排序,使用链表存储排序结果
  3. 迭代基数位,重复步骤1和2,直到所有基数位完成

在这里插入图片描述

#include <stdio.h>
#include <stdlib.h>

// 定义节点结构,包含数据和指向下一个节点的指针
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义链表结构,包含头节点和尾节点
typedef struct List {
    Node* head;
    Node* tail;
} List;

// 初始化链表函数,设置头节点和尾节点为NULL
void initList(List* list) {
    list->head = NULL;
    list->tail = NULL;
}

// 插入节点到链表末尾
void insertNode(List* list, int data) {
    // 分配新节点的内存
    Node* newNode = (Node*)malloc(sizeof(Node));
    // 设置新节点的数据
    newNode->data = data;
    // 置新节点的下一个节点为NULL
    newNode->next = NULL;

    // 如果链表为空,设置新节点为头节点和尾节点
    if (list->head == NULL) {
        // 设置头节点为新节点
        list->head = newNode;
        // 设置尾节点为新节点
        list->tail = newNode;
    }
    // 如果链表不为空,插入新节点到尾节点后面
    else {
        // 设置尾节点的下一个节点为新节点
        list->tail->next = newNode;
        // 更新尾节点为新节点
        list->tail = newNode;
    }
}

// 打印链表
void printList(List* list) {
    // 从头节点开始遍历链表
    Node* current = list->head;
    // 遍历链表,直到到达NULL
    while (current != NULL) {
        // 打印当前节点的数据
        printf("%d ", current->data);
        // 移动到下一个节点
        current = current->next;
    }
    printf("\n");
}


// 分配节点到桶中的函数
void allocateNodes(List* list, List* bucket, int digit) {
    // 分配节点到桶中
    Node* current = list->head; // 从头节点开始遍历链表
    while (current != NULL) {
        // 计算当前节点的数据在当前位数上的值
        int index = (current->data / digit) % 10;
        // 将当前节点插入到对应的桶中
        insertNode(&bucket[index], current->data);
        // 移动到下一个节点
        current = current->next;
    }
}

// 收集节点从桶中的函数
void collectNodes(List* list, List* bucket) {
    // 收集节点从桶中
    list->head = NULL;// 重置头节点为NULL
    list->tail = NULL;// 重置尾节点为NULL
    for (int j = 0; j < 10; j++) {
        // 从每个桶中收集节点
        Node* current = bucket[j].head;// 从桶的头节点开始遍历
        while (current != NULL) {
            // 将当前节点插入到链表中
            insertNode(list, current->data);
            // 移动到下一个节点
            current = current->next;
        }
        // 初始化每个桶
        initList(&bucket[j]);
    }
}

// 基数排序函数
void radixSort(List* list) {
    int digit = 1;  // 初始化位数为个位(1)
    List bucket[10]; // 定义10个桶,用于存储不同位数的数据
    for (int i = 0; i < 10; i++) {
        // 初始化每个桶
        initList(&bucket[i]);
    }

    // 进行3次分配和收集(针对3位数字)
    for (int i = 0; i < 3; i++) {
        // 分配节点到桶中
        allocateNodes(list, bucket, digit);

        // 收集节点从桶中
        collectNodes(list, bucket);

        // 将位数乘以10(下一位)
        digit *= 10;

        // 打印当前的数据状态
        printf("第 %d 趟分配 + 收集后的数据:\n", i + 1);
        printList(list);
    }
}



int main() {
    List list;
    initList(&list);

    int r[] = { 614,738,921,485,637,101,215,530,790,306 };
    int i;
    int n = sizeof(r) / sizeof(r[0]);
    for (i = 0; i < n; i++)
    {
        insertNode(&list, r[i]);
    }
    // 插入示例数据

    printf("原始数据:\n");
    printList(&list);

    radixSort(&list);

    return 0;
}

适用范围:多关键字排序可以处理多种数据类型,而链式基数排序仅适用于整数或字符串数据。

时间复杂度: O(k*(n+m))

​ k:关键字个数,
​ m:关键字取值范围为m个值

空间复杂度: O(n+m)

稳定性: 稳定

10.7 各种内部排序方法的比较讨论

在这里插入图片描述

一、时间性能

  1. 按平均的时间性能来分,有三类排序方法:·

    • 时间复杂度为O(nlogn)的方法有: 快速排序、堆排序和归并排序,其中以快速排序为最好

    • 时间复杂度为O(n2)的有: 直接插入排序、冒泡排序和简单选择排序,其中以直接插入为最好

    • 时间复杂度为O(n)的排序方法只有: 基数排序。

  2. 当待排记录序列按关键字顺序有序时,直接插入排序和冒泡排序达到O(n)的时间复杂度;

    而对于快速排序而言,这是最不好的情况,此时的时间性能退化为O(n2),因此是应该尽量避免的情况。

二、空间性能:指的是排序过程中所需的辅助空间大小

  1. 所有的简单排序方法(包括:直接插入、冒泡和简单选择)和堆排序的空间复杂度为O(1)

  2. 快速排序为O(logn),为栈所需的辅助空间

  3. 归并排序所需辅助空间最多,其空间复杂度为O(n)

  4. 链式基数排序需附设队列首尾指针,则空间复杂度为O(rd)


参考:

教材:严蔚敏《数据结构》(C语言版).pdf

视频:

数据结构与算法基础(青岛大学-王卓)

表插入排序算法实现

博客:

2-路插入排序详解

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/949571.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Unity学习笔记(七)使用状态机重构角色攻击

前言 本文为Udemy课程The Ultimate Guide to Creating an RPG Game in Unity学习笔记 攻击状态重构 首先我们重构攻击状态的动画 之前的动画&#xff0c;我们是使用状态(isAttacking)攻击次数(comboCounter)完成动画的过渡&#xff0c;这样虽然能完成功能&#xff0c;但是如…

Ubuntu20.04中安装ns-3.36及遇到的问题

一、安装虚拟机&#xff1a;VMware 17.5 参考教程&#xff1a;VMware17Pro虚拟机安装教程(超详细)-CSDN博客 博主&#xff1a;七维大脑 遇到的问题&#xff1a; Q1&#xff1a;安装ubuntu系统时&#xff0c;页面看不到”继续“选项&#xff0c;无法进行下一步 A&#xff…

iOS 逆向学习 - iOS Architecture Cocoa Touch Layer

iOS 逆向学习 - iOS Architecture Cocoa Touch Layer 一、Cocoa Touch Layer 简介二、Cocoa Touch Layer 的核心功能1. UIKit2. Event Handling&#xff08;事件处理&#xff09;3. Multitasking&#xff08;多任务处理&#xff09;4. Push Notifications&#xff08;推送通知&…

人大金仓实现主键自增.

使用数据库中自带的参数类型 serial 类型(相当于创建一个INT列), 或者bigserial(相当于创建一个BIGINT列. 示例sql: CREATE TABLE ord(id SERIAL,ord_no INT NOT NULL,ord_name VARCHAR(32),CONSTRAINT "ord_PKEY" PRIMARY KEY ("id"));插入时指定自增值…

React Router 向路由组件传state参数浏览器回退历史页面显示效果问题

昨天在看尚硅谷张天禹老师讲的 React教程p90&#xff0c;老师讲到 React路由的 replace模式和push模式&#xff0c;老师的演示效果与自己本地操作不太一样。 老师的效果&#xff1a;点击查看消息1&#xff0c;消息2&#xff0c;消息3 再点回退&#xff0c;可以依次查看到 消息…

selenium无法定位元素的几种解决方案

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 1、frame/iframe表单嵌套 WebDriver只能在一个页面上对元素识别与定位&#xff0c;对于frame/iframe表单内嵌的页面元素无法直接定位。 解决方法&#xff1a; d…

SSM-Spring-IOC/DI注解开发

目录 IOC/DI注解开发 1 注解开发定义bean 2 纯注解开发模式 步骤 Bean的作用范围 Bean生命周期 3 注解开发依赖注入 Autowired 注解实现按照名称注入 简单数据类型注入 注解读取properties配置文件 4 IOC/DI 注解开发管理第三方bean 4.1 步骤&#xff08;以管理第三…

深入探讨 Android 中的 AlarmManager:定时任务调度及优化实践

引言 在 Android 开发中&#xff0c;AlarmManager 是一个非常重要的系统服务&#xff0c;用于设置定时任务或者周期性任务。无论是设置一个闹钟&#xff0c;还是定时进行数据同步&#xff0c;AlarmManager 都是不可或缺的工具之一。然而&#xff0c;随着 Android 系统的不断演…

接口开发完后,个人对于接下来接口优化的一些思考

优化点 入参的合法性和长度范围&#xff0c;必填项的检查验证 因为没有入参&#xff0c;所以不需要考虑。 批量思想解决N1问题 // 假设要查询100个订单及其对应的用户信息 List<Order> orders orderMapper.selectList(new QueryWrapper<>().last("limit …

Redis内存碎片

什么是内存碎片? 你可以将内存碎片简单地理解为那些不可用的空闲内存。 举个例子&#xff1a;操作系统为你分配了 32 字节的连续内存空间&#xff0c;而你存储数据实际只需要使用 24 字节内存空间&#xff0c;那这多余出来的 8 字节内存空间如果后续没办法再被分配存储其他数…

小程序租赁系统开发的优势与应用前景分析

内容概要 小程序租赁系统是一种新兴的数字化解决方案&#xff0c;旨在为用户提供更加便捷与高效的租赁服务。它通常包括一系列功能&#xff0c;如在线浏览、即时预定、支付功能以及用户反馈机制。这些系统在使用上极为友好&#xff0c;让用户能够轻松选择所需的商品或服务&…

25年1月更新。Windows 上搭建 Python 开发环境:PyCharm 安装全攻略(文中有安装包不用官网下载)

python环境没有安装的可以点击这里先安装好python环境&#xff0c;python环境安装教程 安装 PyCharm IDE 获取 PyCharm PyCharm 提供两种主要版本——社区版&#xff08;免费&#xff09;和专业版&#xff08;付费&#xff09;。对于初学者和个人开发者而言&#xff0c;社区…

RedisTemplate执行lua脚本及Lua 脚本语言详解

使用RedisTemplate执行lua脚本 在开发中&#xff0c;我们经常需要与Redis数据库进行交互&#xff0c;而Redis是一个基于内存的高性能键值存储数据库&#xff0c;它支持多种数据结构&#xff0c;并提供了丰富的命令接口。在某些情况下&#xff0c;我们可能需要执行一些复杂的逻…

基于Python 的宠物管理系统(源码+部署)

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

stm32第一次烧录或者上电运行卡死问题分析

问题描述 单片机烧录代码&#xff08;刚上电&#xff09;无法立即运行&#xff0c;必须要复位一次或多次才能运行&#xff1b;跟踪调试会进入HardFault_Handler中断。 问题分析 烧录配置如下图&#xff0c;首先排除配置问题那么该问题就比较让人头大了&#xff0c;理论上&am…

ESP32-C3 AT WiFi AP 启 TCP Server 被动接收模式 + BLE 共存

TCP 被动接收模式&#xff0c;每次发的数据会先存到缓冲区&#xff0c;参见&#xff1a;ATCIPRECVTYPE 指令说明。 即每包数据不会实时报告 IPD 接收情况&#xff0c;如果需要查询缓冲区的数据&#xff0c;先用 ATCIPRECVLEN? 指令查询被动接收模式下套接字数据的长度 。获取…

【LeetCode Hot100 二分查找】搜索插入位置、搜索二维矩阵、搜索旋转排序数组、寻找两个正序数组的中位数

二分查找 搜索插入位置搜索二维矩阵在排序数组中查找元素的第一个和最后一个位置寻找旋转排序数组中的最小值搜索旋转排序数组寻找两个正序数组的中位数&#xff08;hard&#xff09; 搜索插入位置 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并…

ChatGPT 主流模型GPT-4/GPT-4o mini的参数规模是多大?

微软论文又把 OpenAI 的机密泄露了&#xff1f;&#xff1f;在论文中明晃晃写着&#xff1a; o1-preview 约 300B&#xff1b;o1-mini 约 100BGPT-4o 约 200B&#xff1b;GPT-4o-mini 约 8BClaude 3.5 Sonnet 2024-10-22 版本约 175B微软自己的 Phi-3-7B&#xff0c;这个不用约…

Docker 安装Elasticsearch搜索引擎 搜索优化 词库挂载 拼音分词 插件安装

介绍 允许用户快速索引和搜索大量的文本数据。通过使用倒排索引&#xff0c;它能够在海量数据中高效检索相关信息。提供灵活的查询语言&#xff0c;可以做全文搜索、模糊搜索、数据统计等&#xff0c;用来代替MYSQL的模糊搜索&#xff0c;MYSQL的模糊搜索不支持使用索引从而导…

Scala_【5】函数式编程

第五章 函数式编程函数和方法的区别函数声明函数参数可变参数参数默认值 函数至简原则匿名函数高阶函数函数作为值传递函数作为参数传递函数作为返回值 函数闭包&柯里化函数递归控制抽象惰性函数友情链接 函数式编程 面向对象编程 解决问题时&#xff0c;分解对象&#xff…