当前位置： 首页 > news >正文

【数据结构与算法】顺序表和链表、栈和队列、二叉树、排序等数据结构的完整代码收录

news 2025/8/6 7:33:05

 

 🔥个人主页：艾莉丝努力练剑

❄专栏传送门：《C语言》、《数据结构与算法》、C语言刷题12天IO强训、LeetCode代码强化刷题

🍉学习方向：C/C++方向

⭐️人生格言：为天地立心，为生民立命，为往圣继绝学，为万世开太平

 

重要提醒：为什么我们要学那么多的数据结构？这是因为没有一种数据结构能够去应对所有场景。我们在不同的场景需要选择不同的数据结构，所以数据结构没有谁好谁坏之分，而评估数据结构的好坏要针对场景，如果在一种场景下我们需要频繁地对头部进行插入删除操作，那么这个时候我们用链表；但是如果对尾部进行插入删除操作比较频繁，那我们用顺序表比较好。

        因此，不同的场景我们选择不同的数据结构。

前言：本篇文章，我们继续来看二叉树相关的知识点，在初阶的数据结构与算法阶段，我们把知识点分成三部分，复杂度作为第一部分，顺序表和链表、栈和队列、二叉树为第二部分，排序为第二部分，我们之前已经介绍完了第一部分：算法复杂度，本文我们将正式开始学习第二部分中的二叉树部分内容啦。 

目录

正文

一、顺序表

（一）静态顺序表

1、SeqList.h

2、SeqList.c（静态顺序表）

3、test.c

（二）动态顺序表

1、SeqList.h

2、SeqList.c

3、test.c

二、链表

（一）单链表

1、SList.h

2、SList.c

3、test.c

（二）双向链表（优化版）

1、List.h

2、List.c

3、test.c

三、栈和队列

（一）栈：栈结构实现（数组）的完整代码

1、List.h

2、List.c

3、test.c

（二）队列（优化版）

1、Queue.h

2、Queue.c

3、test.c

四、二叉树：顺序结构、链式结构

（一）二叉树的顺序结构：堆

1、Heap.h

2、Heap.c

3、test.c

（二）二叉树——链式结构实现

1、Queue.h

2、Queue.c

3、Tree.h 

4、Tree.c

5、test.c

五、排序

（一）插入排序

1、直接插入排序

2、希尔排序

（二）选择排序

1、直接选择排序

2、堆排序

（三）交换排序

1、冒泡排序

2、快速排序

（1）递归版本

1）Hoare版本

2）挖坑法

3）Lomuto双指针版本

（2）非递归版本——栈

1）Stack.h：

2）Stack.c： 

3）sort.c： 

（3）三路划分

1）写法1

2）写法2

3）写法3

（4）自省排序（内观排序）

（四）归并排序

1、递归版本

2、非递归版本

3、文件归并排序

（五）非比较排序

1、计数排序

（六）排序——完整代码

1、Stack.h

2、Stack.c

3、sort.h

4、sort.c

5、test.c

（七）对比排序性能：测试代码

结尾

正文

一、顺序表

（一）静态顺序表

1、SeqList.h
#ifdef __TEST_H__
#define __TEST_H__#include<stdio.h>
#include<string.h>
//增强程序可维护性
#define  MAX_SIZE  10//100个、500个有点太大了，先来10个
typedef int SQDataType;typedef struct SeqList
{SQDataType a[MAX_SIZE];int size;
}SL;
//增删查改等接口函数
void SeqListInit(SL*ps);
void SeqListPushBack(SL*ps,SQDataType x);//尾插
void SeqListPushFront(SL*ps,SQDataType x);//头插
void SeqListPopBack(SL*ps);//头删
void SeqListPopFront(SL*ps);//尾删
#endif
2、SeqList.c（静态顺序表）
#include"SeqList.h"void SeqListInit(SL*p s)
{memset(ps->a,0,sizeof(SQDataType)*MAX_SIZE);ps->size = 0;
}
//头插  尾插  头删  尾删
void SeqListPushBack(SL*ps,SQDataType x);
{if(ps->size >= MAX_SIZE){printf("SeqList is Full\n");return;}ps->a[ps->size] = x;ps->size++;
}
//下面的大致也是上面这样，就不介绍了
void SeqListPushFront(SL*ps,SQDataType x);
void SeqListPopBack(SL*ps);
void SeqListPopFront(SL*ps);
3、test.c
#include"SeqList.h"void TestSeqList1()
{SL sl;SeqListInit(&sl);
//调接口进行初始化
}int main()
{TestSeqListl();return 0;
}

（二）动态顺序表

动态顺序表的各种方法博主已经整理过了，直接3！2！1！上链接！

【数据结构与算法】数据结构初阶：动态顺序表各种方法（接口函数）复盘与整理

这里我们还是把完整代码再展示一遍—— 

1、SeqList.h
#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义动态顺序表的结构
typedef int SLTDataType;
typedef struct SeqList 
{SLTDataType* arr;  //存储数据int size;  //有效数据个数int capacity; //空间大小
}SL;//typedef struct SeqList SL;void SLPrint(SL* ps);
void SLInit(SL* ps);
void SLDestroy(SL* ps);//尾插
void SLPushBack(SL* ps, SLTDataType x);//头插
void SLPushFront(SL* ps, SLTDataType x);//尾删
void SLPopBack(SL* ps);//头删
void SLPopFront(SL* ps);//查找
int SLFind(SL* ps, SLTDataType x);//指定位置之前插入
void SLInsert(SL* ps, int pos, SLTDataType x);//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLTDataType x);//删除pos(指定)位置的数据
void SLErase(SL* ps, int pos);//修改
void SLModity(SL* ps, int pos, SLTDataType x);
2、SeqList.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"SeqList.h"void SLInit(SL* ps)
{ps->arr = NULL;ps->size = ps->capacity = 0;
}
void SLDestroy(SL* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->size = ps->capacity = 0;
}void SLPrint(SL* ps)
{for (int i = 0; i < ps->size; i++){printf("%d ", ps->arr[i]);}printf("\n");
}void SLCheckCapacity(SL* ps)
{if (ps->size == ps->capacity){int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;//增容SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}
}//尾插
void SLPushBack(SL* ps, SLTDataType x)
{assert(ps);//空间不够SLCheckCapacity(ps);//空间足够ps->arr[ps->size++] = x;
}//头插
void SLPushFront(SL* ps, SLTDataType x)
{//温柔的处理方式//if (ps == NULL)//{//	return;//}assert(ps != NULL); //等价于assert(ps）//空间不够SLCheckCapacity(ps);//数据整体向后挪动一位for (int i = ps->size; i > 0; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[0] = x;ps->size++;
}
//尾删
void SLPopBack(SL* ps)
{assert(ps && ps->size);ps->size--;
}
//头删
void SLPopFront(SL* ps)
{assert(ps && ps->size);//数据整体向前挪动一位for (int i = 0; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//查找
int SLFind(SL* ps, SLTDataType x)
{assert(ps);for (int i = 0; i < ps->size; i++){if (ps->arr[i] == x){//找到了return i;}}//未找到return -1;
}
//指定位置之前插入
void SLInsert(SL* ps, int pos, SLTDataType x)
{assert(ps);//0<= pos < ps->sizeassert(pos >= 0 && pos < ps->size);//判断空间是否足够SLCheckCapacity(ps);//pos及之后数据向后挪动一位for (int i = ps->size; i > pos; i--){ps->arr[i] = ps->arr[i - 1];}ps->arr[pos] = x;ps->size++;
}//在指定位置之后插入数据
void SLInsertAfter(SL* ps, int pos, SLTDataType x)
{assert(ps);//0<= pos < ps->sizeassert(pos >= 0 && pos < ps->size);//判断空间是否足够SLCheckCapacity(ps);ps->arr[pos] = x;ps->size++;
}//删除pos位置的数据
void SLErase(SL* ps, int pos)
{assert(ps);//pos:[0，ps->size)assert(pos >= 0 && pos < ps->size);//pos后面的数据向前挪动一位for (int i = pos; i < ps->size - 1; i++){ps->arr[i] = ps->arr[i + 1];}ps->size--;
}//修改
void SLModity(SL* ps, int pos, SLTDataType x) 
{assert(pos < ps->size);ps->arr[pos] = x;
}
3、test.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"SeqList.h"void test01()
{SL sl;SLInit(&sl);//具备了一个空的顺序表SLPushBack(&sl, 1);SLPushBack(&sl, 2);SLPushBack(&sl, 3);SLPushBack(&sl, 4);SLPrint(&sl);//SLPushFront(&sl, 1);//SLPushFront(&sl, 2);//2 1//SLPushFront(&sl, 3);//3 2 1//SLPushFront(&sl, 4);//4 3 2 1//SLPopBack(&sl);//SLPrint(&sl);//1 2 3//SLPopBack(&sl);//SLPrint(&sl);//1 2 //SLPopBack(&sl);//SLPrint(&sl);//1 //SLPopBack(&sl);//SLPrint(&sl);////SLPopBack(&sl);////头删//SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//SLPrint(&sl);//SLPopFront(&sl);//测试查找int pos = SLFind(&sl, 3);//if (pos < 0)//{//	printf("未找到！\n");//}//else // {//	printf("找到了！\n");//}//SLInsert(&sl, pos, 100);//SLPrint(&sl);//SLInsert(&sl, pos, 200);//SLPrint(&sl);//SLInsert(&sl, pos, 300);//SLPrint(&sl);//SLInsert(&sl, pos, 400);//SLPrint(&sl);SLErase(&sl, pos);SLPrint(&sl);SLDestroy(&sl);
}int main()
{test01();return 0;
}

二、链表

（一）单链表

1、SList.h
#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//链表的结构​
typedef int SLTDatatype;
typedef struct SListNode
{SLTDatatype data;struct SListNode* next;//指向下一个节点的地址
}​SLTNode;//typedef struct SListNode SLTNode;void SLTPrint(​SLTNode* phead);//尾插
void SLTPushBack(​SLTNode** pphead, SLTDatatype x);//头插
void SLTPushFront(​SLTNode** pphead, SLTDatatype x);//尾删
void SLTPopBack(​SLTNode** pphead);//头删
void SLTPopFront(​SLTNode** pphead);//查找
​SLTNode* SLTFind(​SLTNode* phead, SLTDatatype x);//在指定位置之前插入数据
void SLTInsert(​SLTNode** pphead, ​SLTNode* pos, SLTDatatype x);//在指定位置之后插入数据
void SLTInsertAfter(​SLTNode* pos, SLTDatatype x);//删除pos节点
void SLTErase(​SLTNode** pphead, ​SLTNode* pos);//删除pos之后的节点
void SLTEraseAfter(​SLTNode* pos);//修改
void SLTChangeData(​SLTNode* pos, SLTDatatype x);//销毁链表
void SListDestory(​SLTNode** pphead);
2、SList.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"SList.h"void SLTPrint(​SLTNode* phead)
{​SLTNode* pcur = phead;while (pcur != NULL){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("NULL\n");
}//后续我们要申请新节点就直接调用SLTBuyNode方法
​SLTNode* SLTBuyNode(SLTDatatype x)
{​SLTNode* newnode = (​SLTNode*)malloc(sizeof(​SLTNode));//malloc不一定申请成功，我们判断一下if (newnode == NULL){printf("malloc fail!");exit(1);}//初始化一下newnode->data = x;newnode->next = NULL;return newnode;
}//尾插
void SLTPushBack(​SLTNode** pphead, SLTDatatype x)
{//申请新节点​SLTNode* newnode = SLTBuyNode(x);//链表为空——要特殊处理if (*pphead == NULL){*pphead = newnode;}else{​SLTNode* ptail = *pphead;while (ptail->next != NULL){ptail = ptail->next;}//找到了尾节点 ptail newnodeptail->next = newnode;}
}//头插
void SLTPushFront(​SLTNode** pphead, SLTDatatype x)
{assert(pphead);​SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}//尾删
void SLTPopBack(​SLTNode** pphead)
{//链表为空不能删除assert(pphead && *pphead);//pphead是*pphead的地址//pphead是一个二级指针，我们对pphead解引用一次，*pphead就是指向第一个节点的地址//*pphead为空说明链表为空//链表只有一个节点的情况if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{​SLTNode* prev = NULL;​SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}//prev  ptailprev->next = NULL;free(ptail);ptail = NULL;}
}//头删
void SLTPopFront(​SLTNode** pphead)
{assert(pphead && *pphead);​SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}//查找
​SLTNode* SLTFind(​SLTNode* phead, SLTDatatype x)
{​SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//未找到return NULL;
}//在指定位置之前插入数据
void SLTInsert(​SLTNode** pphead, ​SLTNode* pos, SLTDatatype x)
{assert(pphead && pos);​SLTNode* newnode = SLTBuyNode(x);//pos指向头节点if (pos == *pphead){//头插SLTPushFront(pphead, x);}else{//找pos前一个节点​SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev   newnode  posprev->next = newnode;newnode->next = pos;}
}//在指定位置之后插入数据
void SLTInsertAfter(​SLTNode* pos, SLTDatatype x)
{assert(pos);​SLTNode* newnode = SLTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;pos->next = newnode;
}//删除pos节点
void SLTErase(​SLTNode** pphead, ​SLTNode* pos)
{assert(pphead && pos);//pos刚好是头节点——头删if (pos==*pphead){SLTPopFront(pphead);}else{​SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}//删除pos之后的节点
void SLTEraseAfter(​SLTNode* pos)
{assert(pos);//pos  del  del->next​SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}//修改
void SLTChangeData(​SLTNode* pos, SLTDatatype x)
{assert(pos);pos->data = x;
}//销毁链表
void SListDestory(​SLTNode** pphead)
{//一个一个销毁assert(pphead);​SLTNode* pcur = *pphead;while (pcur){​SLTNode* next = pcur->next;free(pcur);pcur = next;}//*pphead是野指针，要置为空*pphead = NULL;
}
3、test.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"SList.h"int test01()
{//创建一个链表——实际上是创建一个一个节点，再把节点连起来​SLTNode*node1=(​SLTNode*)malloc(sizeof(​SLTNode));​SLTNode*node2=(​SLTNode*)malloc(sizeof(​SLTNode));​SLTNode*node3=(​SLTNode*)malloc(sizeof(​SLTNode));​SLTNode*node4=(​SLTNode*)malloc(sizeof(​SLTNode));node1->data = 1;node2->data = 2;node3->data = 3;node4->data = 4;node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;​SLTNode* plist = node1;//打印链表SLTPrint(plist);
}void test02()
{//创建空链表​SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPrint(plist);////SLTPushFront(&plist, 1);//SLTPrint(plist);//SLTPushFront(&plist, 2);//SLTPrint(plist);//SLTPushFront(&plist, 3);//SLTPrint(plist);//SLTPushFront(&plist, 4);//SLTPrint(plist);////SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);//SLTPopBack(&plist);//SLTPrint(plist);////头删
//	SLTPopFront(&plist);
//	SLTPrint(plist);
//	SLTPopFront(&plist);
//	SLTPrint(plist);
//	SLTPopFront(&plist);
//	SLTPrint(plist);
//	SLTPopFront(&plist);
//	SLTPrint(plist);​SLTNode* pos = SLTFind(plist, 3);//if (pos)//{//	printf("找到了！\n");//}//else//{//	printf("未找到！\n");//}//SLTInsert(&plist, pos, 100);/*SLTInsertAfter(pos, 100);*///SLTErase(&plist, pos);//SLTPrint(plist);SListDestory(&plist);
}int main()
{/*test01();*/test02();return 0;
}

（二）双向链表（优化版）

1、List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义双向链表结构
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;//指向后一个节点的指针struct ListNode* prev;//指向前一个节点的指针
}LTNode;//优化版初始化
LTNode* LTInit();//优化版销毁——为了保持接口一致性
void LTDestroy(LTNode* phead);//在双向链表中，增删查改都不会改变哨兵位节点
//所以我们要用一级指针，因为我们不改变phead——plist指针
//尾插
void LTPushBack(LTNode* phead, LTDataType x);//头插
void LTPushFront(LTNode* phead, LTDataType x);//尾删
void LTPopBack(LTNode* phead);//判断链表是否为空
bool LTEmpty(LTNode* phead);//打印
void LTPrint(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//在双向链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x);//在pos位置之前插入节点
void LTInsertBefore(LTNode* pos, LTDataType x);//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x);//任意位置的插入//删除pos位置的节点
void LTErase(LTNode* pos);//修改
void LTChange(LTNode* pos, LTDataType x);
2、List.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"List.h"LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = newnode->prev = newnode;return newnode;
}//优化版初始化
LTNode* LTInit()
{LTNode* phead = LTBuyNode(-1);return phead;
}//优化版销毁
void LTDestroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//销毁头结点free(phead);phead = NULL;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDataType x) 
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next;
}//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}//判断链表是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;//其实置不置为空都没关系，这里执行到这里程序已经结束了，不会再用到del了//这样写无非是养成一个好习惯
}//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;del->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}//在双向链表里面查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//未找到return NULL;
}//在pos位置之前插入节点
void LTInsertBefore(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos->prev newnode posnewnode->prev = pos->prev;newnode->next = pos;pos->prev->next = newnode;pos->prev = newnode;
}//在pos位置之后插入节点
void LTInsert(LTNode* pos, LTDataType x)//任意位置的插入
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}//删除pos位置的节点
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//修改
void LTChange(LTNode* pos, LTDataType x)
{assert(pos);pos->data = x;
}
3、test.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"List.h"void test01()
{LTNode* plist = LTInit();//创建一个指针来接收初始化的返回值LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//LTPushFront(plist, 1);//LTPushFront(plist, 2);//LTPushFront(plist, 3);//LTPushFront(plist, 4);// //LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);////LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);LTNode* pos = LTFind(plist,2);//if (pos)//{//	printf("找到了！\n");//}//else//{//	printf("未找到!\n");//}// //LTInsertBefore(pos, 100);//LTPrint(plist);//LTInsert(pos, 100);//LTPrint(plist);//LTErase(pos);//LTPrint(plist);//修改LTChange(pos, 100);LTPrint(plist);//优化版销毁LTDestroy(plist);plist = NULL;
}int main()
{test01();return 0;
}

三、栈和队列

（一）栈：栈结构实现（数组）的完整代码

1、List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;//定义栈中有效的数据个数int capacity;//栈的空间大小
}ST;//初始化
void STInit(ST* ps);//销毁
void STDestory(ST* ps);//入栈——栈顶
void STPush(ST* ps, STDataType x);//出栈——栈顶
void STPop(ST* ps);//取栈顶元素
STDataType STTop(ST* ps);//栈是否为空
bool STEmpty(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);
2、List.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"Stack.h"//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//销毁
void STDestory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//入栈——栈顶
void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;int* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈——栈顶
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
3、test.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"Stack.h"void test01()
{ST st;STInit(&st);STPush(&st, 1);STPush(&st, 2);STPush(&st, 3);STPush(&st, 4);printf("size:%d\n", STSize(&st));//STPop(&st);while (!STEmpty(&st)){//取栈顶STDataType top = STTop(&st);printf("%d ", top);//出栈STPop(&st);}printf("\n");STDestory(&st);
}int main()
{test01();return 0;
}

（二）队列（优化版）

1、Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
//定义节点的结构typedef struct QueueNode 
{QDataType data;struct QueueNode* next;
}QueueNode;//定义队列的结构
typedef struct Queue 
{QueueNode* phead;//指向队头节点的指针QueueNode* ptail;//指向队尾节点的指针int size;		   //队列中有效数据个数
}Queue;//初始化
void QueueInit(Queue* pq);//销毁
void QueueDestory(Queue* pq);//入队列，队尾
void QueuePush(Queue* pq, QDataType x);// 出队列，队头
void QueuePop(Queue* pq);//队列判空
bool QueueEmpty(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);//取队尾数据
QDataType QueueBack(Queue* pq);//队列有效元素个数
int QueueSize(Queue* pq);
2、Queue.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while(pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;//防止phead、ptail变野指针pq->size = 0;//销毁后元素个数重置为0
}//入队列,队尾
void QueuePush(Queue* pq, QDataType x)
{int size = 0;assert(pq);//创建值为x的节点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//队列为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;//入队后元素个数+1
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}// 出队列，队头
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));//队列中只有一个节点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else {QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;//出队后元素个数-1
}//取队头数据
QDataType QueueFront(Queue* pq)
{ assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}//队列有效元素个数
int QueueSize(Queue* pq)
{return pq->size;
}
3、test.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"Queue.h"void test01()
{Queue q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4); //1 2 3 4//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);//QueuePop(&q);printf("队头：%d\n", QueueFront(&q));printf("队尾：%d\n", QueueBack(&q));printf("size: %d\n", QueueSize(&q));QueueDestory(&q);
}int main()
{test01();return 0;
}

四、二叉树：顺序结构、链式结构

（一）二叉树的顺序结构：堆

1、Heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义堆结构
typedef int HPDataType;
typedef struct Heap {HPDataType* arr;int size;    //有效数据个数int capaicty;//空间大小
}HP;void HPInit(HP* php);
void HPDesTroy(HP* php);void HPPrint(HP* php);
void Swap(int* x, int* y);
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n);
//向上调整算法
void AdjustUp(HPDataType* arr, int child);void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
HPDataType HPTop(HP* php);bool HPEmpty(HP* php);
2、Heap.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"Heap.h"void HPInit(HP* php)
{assert(php);php->arr = NULL;php->size = php->capaicty = 0;
}
void HPDesTroy(HP* php)
{assert(php);if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capaicty = 0;
}
void HPPrint(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//向上调整算法
void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){//建大堆：>//建小堆: <if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}
//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){//建大堆：<//建小堆: >if (child + 1 < n && arr[child] > arr[child + 1]){child++;}//孩子和父亲比较//建大堆：>//建小堆:<if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}void HPPush(HP* php, HPDataType x)
{assert(php);//空间不够要增容if (php->size == php->capaicty){//增容int newCapacity = php->capaicty == 0 ? 4 : 2 * php->capaicty;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capaicty = newCapacity;}//空间足够php->arr[php->size] = x;//向上调整AdjustUp(php->arr, php->size);++php->size;
}bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}void HPPop(HP* php)
{assert(!HPEmpty(php));Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//堆顶数据需要向下调整AdjustDown(php->arr, 0, php->size);
}HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}
3、test.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"Heap.h"void test01()
{HP hp;HPInit(&hp);HPPush(&hp, 25);HPPush(&hp, 15);HPPush(&hp, 10);HPPush(&hp, 56);HPPush(&hp, 70);HPPush(&hp, 30);HPPrint(&hp);while (!HPEmpty(&hp)){int top = HPTop(&hp);printf("%d ", top);HPPop(&hp);}//HPPop(&hp);//HPPrint(&hp);//HPPop(&hp);//HPPrint(&hp);//HPPop(&hp);//HPPrint(&hp);//HPPop(&hp);//HPPrint(&hp);//HPPop(&hp);//HPPrint(&hp);HPDesTroy(&hp);}int main()
{test01();return 0;
}

（二）二叉树——链式结构实现

1、Queue.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//typedef int QDataType;
//int更改为二叉树节点结构
//前置声明————不需要定义，就相当于下面的void QueueInit(Queue* pq);这些方法一样
typedef struct BinaryTreeNode* QDataType;//定义节点的结构typedef struct QueueNode 
{QDataType data;struct QueueNode* next;
}QueueNode;//定义队列的结构
typedef struct Queue 
{QueueNode* phead;//指向队头节点的指针QueueNode* ptail;//指向队尾节点的指针int size;		   //队列中有效数据个数
}Queue;//初始化
void QueueInit(Queue* pq);//销毁
void QueueDestory(Queue* pq);//入队列，队尾
void QueuePush(Queue* pq, QDataType x);// 出队列，队头
void QueuePop(Queue* pq);//队列判空
bool QueueEmpty(Queue* pq);//取队头数据
QDataType QueueFront(Queue* pq);//取队尾数据
QDataType QueueBack(Queue* pq);//队列有效元素个数
int QueueSize(Queue* pq);
2、Queue.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}//销毁队列
void QueueDestory(Queue* pq)
{assert(pq);QueueNode* pcur = pq->phead;while(pcur){QueueNode* next = pcur->next;free(pcur);pcur = next;}pq->phead = pq->ptail = NULL;//防止phead、ptail变野指针pq->size = 0;//销毁后元素个数重置为0
}//入队列,队尾
void QueuePush(Queue* pq, QDataType x)
{int size = 0;assert(pq);//创建值为x的节点QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->next = NULL;//队列为空if (pq->phead == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = pq->ptail->next;}pq->size++;//入队后元素个数+1
}//队列判空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}// 出队列，队头
void QueuePop(Queue* pq)
{assert(!QueueEmpty(pq));//队列中只有一个节点if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else {QueueNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;//出队后元素个数-1
}//取队头数据
QDataType QueueFront(Queue* pq)
{ assert(!QueueEmpty(pq));return pq->phead->data;
}//取队尾数据
QDataType QueueBack(Queue* pq)
{assert(!QueueEmpty(pq));return pq->ptail->data;
}//队列有效元素个数
int QueueSize(Queue* pq)
{/*assert(pq);QueueNode* pcur = pq->phead;int size = 0;while (pcur){++size;pcur = pcur->next;}return size;*/return pq->size;
}
3、Tree.h 
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>typedef char BTDataType;
//定义二叉树节点结构
typedef struct BinaryTreeNode
{BTDataType data; // 当前结点值域struct BinTreeNode* left; // 指向当前结点左孩子struct BinTreeNode* right; // 指向当前结点右孩子 
}BTNode;//前序遍历
void PerOrder(BTNode* root);//中序遍历
void InOrder(BTNode* root);//后序遍历
void PostOrder(BTNode* root);//二叉树结点个数 
int BinaryTreeSize(BTNode* root);
//void BinaryTreeSize(BTNode* root, int* psize);//二叉树叶子结点个数 
int BinaryTreeLeafSize(BTNode* root);//二叉树第k层结点个数 
int BinaryTreeLevelKSize(BTNode* root, int k);//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);//二叉树查找值为x的结点 
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉树销毁
void BinaryTreeDestory(BTNode** root);//层序遍历————借助数据结构：队列
void LevelOrder(BTNode* root);//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root);
4、Tree.c
#define  _CRT_SECURE_NO_WARNINGS  1
#include"Tree.h"
#include"Queue.h"//前序遍历————口诀：根左右
void PerOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);PerOrder(root->left);PerOrder(root->right);
}//中序遍历——左根右
void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%c ", root->data);InOrder(root->right);
}//后序遍历——左右根
void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%c ", root->data);
}////错误：创建全局变量，多次调用方法会出现累加的情况
//int size = 0;
////二叉树结点个数 
//int BinaryTreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	size++;
//	BinaryTreeSize(root->left);
//	BinaryTreeSize(root->right);
//
//	return size;
//}//方法二：需要改造函数定义
////二叉树结点个数
//void BinaryTreeSize(BTNode* root, int* psize)
//{
//	if (root == NULL)
//	{
//		return 0;
//	}
//	(*psize)++;
//	BinaryTreeSize(root->left,psize);
//	BinaryTreeSize(root->right,psize);
//}//二叉树结点个数 = 1 + 左子树结点个数 + 右子树结点个数 
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}//二叉树叶子结点个数 
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}//判断是否为叶子结点if (root->left == NULL && root->right == NULL){return 1;}//上面也是递归结束的限制条件return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}//二叉树第k层结点个数 
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}//判断是否为第K层if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDep = BinaryTreeDepth(root->left);int rightDep = BinaryTreeDepth(root->right);//根节点+max(左子树高度，右子树高度)return 1 + (leftDep > rightDep ? leftDep : rightDep);//return 1 + (BinaryTreeDepth(root->left) > BinaryTreeDepth(root->right) ?//	BinaryTreeDepth(root->left) : BinaryTreeDepth(root->right);
}//二叉树查找值为x的结点 
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftFind = BinaryTreeFind(root->left, x);if (leftFind){return leftFind;}BTNode* rightFind = BinaryTreeFind(root->right, x);if (rightFind){return rightFind;}return NULL;
}// 二叉树销毁(后序遍历)
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}//层序遍历————借助数据结构：队列
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头，打印队头BTNode* top = QueueFront(&q);printf("%c ", top->data);QueuePop(&q);//队头节点不为空的孩子节点入队列if (top->left)QueuePush(&q, top->left);if(top->right)QueuePush(&q, top->right);}QueueDestory(&q);
}//判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);//头节点入队列QueuePush(&q, root);while (!QueueEmpty(&q)){//取队头，出队头BTNode* top = QueueFront(&q);QueuePop(&q);if (top == NULL){//top取到空就直接出队列break;}//将队头节点的左右孩子入队列QueuePush(&q, top->left);QueuePush(&q, top->right);}//队列不为空，继续取队列中的队头while (!QueueEmpty(&q)){BTNode* top = QueueFront(&q);QueuePop(&q);if (top != NULL){//不是完全二叉树QueueDestory(&q);return false;}}QueueDestory(&q);return true;
}
5、test.c
#define  _CRT_SECURE_NO_WARNINGS  1
#include"Tree.h"BTNode* buyNode(char x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (x == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}BTNode* creatTree()
{BTNode* nodeA = buyNode('A');BTNode* nodeB = buyNode('B');BTNode* nodeC = buyNode('C');BTNode* nodeD = buyNode('D');BTNode* nodeE = buyNode('E');BTNode* nodeF = buyNode('F');nodeA->left = nodeB;nodeA->right = nodeC;nodeB->left = nodeD;nodeC->left = nodeE;nodeC->right = nodeF;//nodeB->right = nodeE;//nodeC->left = nodeF;return nodeA;
}void test01()
{BTNode* root = creatTree();//PerOrder(root);//InOrder(root);/*PostOrder(root);*///既然返回的是void，就不能再打印了//printf("size:%d\n", BinaryTreeSize(root));//printf("size:%d\n", BinaryTreeSize(root));//int Treesize = 0;//BinaryTreeSize(root, &Treesize);//printf("size:%d\n", Treesize);//Treesize = 0;//BinaryTreeSize(root, &Treesize);//printf("size:%d\n", Treesize);printf("size:%d\n", BinaryTreeSize(root));printf("leaf size:%d\n", BinaryTreeLeafSize(root));printf("K level size:%d\n", BinaryTreeLevelKSize(root, 1));printf("Tree Depth:%d\n", BinaryTreeDepth(root));BTNode* find = BinaryTreeFind(root, 'H');if (find){printf("找到了!\n");}else{printf("未找到!\n");}//层序遍历printf("层序遍历的结果: ");LevelOrder(root);printf("\n");////层序遍历//printf("层序遍历的结果: ", LeveOrder(&root));bool isComplete = BinaryTreeComplete(root);if (isComplete){printf("是完全二叉树！\n");}else{printf("不是完全二叉树！\n");}BinaryTreeDestory(&root);
}int main()
{test01();return 0;
}

五、排序

（一）插入排序

1、直接插入排序
//1)随机插入排序 最差情况：O(N^2) 最好情况：O(N)
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}
2、希尔排序
//2)希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}

（二）选择排序

1、直接选择排序
//1)直接选择排序 O(n^2)
void SelectSort(int* arr, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] < arr[mini]){mini = i;}if (arr[i] > arr[maxi]){maxi = i;}}//maxi mini begin endif (maxi == begin){maxi = mini;}Swap(&arr[begin], &arr[mini]);Swap(&arr[end], &arr[maxi]);begin++;end--;}
}
2、堆排序
//升序——大堆
//交换——Swap方法
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//向下调整算法
void AdjustDown(int* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){//找最大的孩子//建大堆：<//建小堆：>if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//孩子和父亲比较//建大堆：>//建小堆：<if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序————使用的是堆结构的思想
void HeapSort(int* arr, int n)
{//向下调整算法——建堆 O(N)//乱序数组————建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}//n*lognint end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);//lognend--;}
}

（三）交换排序

1、冒泡排序
//冒泡排序
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] < arr[j + 1]){Swap(&arr[j], arr[j + 1]);}}}
}
2、快速排序
//快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值keyiint keyi = _QuickSort(arr, left, right);//左序列[left,keyi-1]  右序列[keyi+1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}
（1）递归版本
1）Hoare版本
//找基准值  hoare版本
int _QuickSort1(int* arr, int left,int right)
{int keyi = left;left++;while (left <= right){//right：从右往左找比基准值小的while (left <= right && arr[right] > arr[keyi]){--right;}//left：从右往左找比基准值大的while (left <= right && arr[left] < arr[keyi]){++left;}//left和right交换if (left <= right)Swap(&arr[left++], &arr[right--]);}//right的位置就是基准值的位置Swap(&arr[keyi], &arr[right]);return right;
}
2）挖坑法
//找基准值  挖坑法
int _QuickSort2(int* arr, int left,int right)
{int hole = left;int key = arr[hole];while (left < right){while (left < right && arr[right] > key){right--;}arr[hole] = arr[right];hole = right;while (left < right && arr[left < key]){++left;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}
3）Lomuto双指针版本
//找基准值 lomuto双指针方法
int _QuickSort(int* arr, int left,int right)
{int prev = left, cur = prev + 1;int keyi = left;while (cur <= right){//cur数据和基准值比较if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], & arr[prev]);}++cur;}Swap(&arr[keyi], &arr[prev]);return prev;
}
（2）非递归版本——栈
1）Stack.h：
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;//定义栈中有效的数据个数int capacity;//栈的空间大小
}ST;//初始化
void STInit(ST* ps);//销毁
void STDestory(ST* ps);//入栈——栈顶
void STPush(ST* ps, STDataType x);//出栈——栈顶
void STPop(ST* ps);//取栈顶元素
STDataType STTop(ST* ps);//栈是否为空
bool STEmpty(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);
2）Stack.c： 
#define  _CRT_SECURE_NO_WARNINGS  1#include"Stack.h"//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//销毁
void STDestory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//入栈——栈顶
void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈——栈顶
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
3）sort.c： 
//非递归版本快速排序——栈：栈+lomuto双指针
void QuickSortNorR(int* arr, int left,int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){//取栈顶两次int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);//[begin,end]————找基准值int keyi = begin;int prev = begin, cur = prev + 1;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}++cur;}Swap(&arr[prev], &arr[keyi]);keyi = prev;//begin  keyi  end//左序列[begin,keyi-1]//右序列[keyi+1,end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestory(&st);
}
（3）三路划分
1）写法1
//三路划分
KeyWayIndex PartSort3Way(int* arr, int left, int right)
{int key = arr[left];//left和right指向就是跟key相等的区间//[begin,left-1]  [left,right]  [right+1,end]int cur = left + 1;while (cur <= right){//1、cur遇到比key小，小的换到左边，同时把key换到中间位置//2、cur遇到比key大，大的换到右边if (arr[cur] < key){Swap(&arr[cur], &arr[left]);++left;++cur;}else if (arr[cur] > key){Swap(&arr[cur], &arr[right]);//cur不能动--right;}else{++cur;}}KeyWayIndex kwi;kwi.leftkeyi = left;kwi.rightkeyi = right;return kwi;
}
2）写法2
int _QuickSort3Way(int* arr, int left, int right)
{return;
}//三路划分实现
void QuickSort3Way(int* arr, int left, int right)
{if (left >= right){return;}//随机数取法srand((unsigned int)time(NULL));int randi = left + rand() % (right - left + 1);Swap(&arr[left], &arr[randi]);//三数取中int midi = _QuickSort3Way(arr, left, right);//三路划分int key = arr[left];int cur = left + 1;int begin = left;int end = right;while (cur <= right){//1、cur遇到比key小，小的换到左边，同时把key换到中间位置//2、cur遇到比key大，大的换到右边if (arr[cur] < key){Swap(&arr[cur], &arr[left]);++left;++cur;}else if (arr[cur] > key){Swap(&arr[cur], &arr[right]);//cur不能动--right;}else{++cur;}}//三路划分 [begin,left-1]  [left,right]  [right+1,end]QuickSort3Way(arr, begin, left - 1);QuickSort3Way(arr, right + 1, end);
}
3）写法3
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void QuickSort(int* arr, int left, int right)
{if (left >= right)return;int begin = left;int end = right;//随机选keyint randi = left + (rand() % (right - left + 1));Swap(&arr[left], &arr[randi]);//三路划分//left和right指向就是跟key相等的区间// [begin, left-1] [left, right] right+1, end]int key = arr[left];int cur = left + 1;while (cur <= right){//1、cur遇到比key小，小的换到左边，同时把key换到中间位置//2、cur遇到比key大，大的换到右边if (arr[cur] < key){Swap(&arr[cur], &arr[left]);++left;++cur;}else if (arr[cur] > key){Swap(&arr[cur], &arr[right]);--right;}else{++cur;}}// [begin, left-1] [left, right] right+1, end]QuickSort(arr, begin, left - 1);QuickSort(arr, right + 1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {srand(time(0));QuickSort(nums, 0, numsSize - 1);*returnSize = numsSize;return nums;
}
（4）自省排序（内观排序）
#define  _CRT_SECURE_NO_WARNINGS  1/*** Note: The returned array must be malloced, assume caller calls free().*/
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}
void AdjustDown(int* a, int n, int parent)
{int child = parent * 2 + 1;while (child < n){//选出左右孩子中大的那⼀个if (child + 1 < n && a[child + 1] > a[child]){++child;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//建堆--向下调整建堆-- O(N)for (int i = (n - 1 - 1) / 2; i >= 0; --i){AdjustDown(a, n, i);}// 自己先实现—— O(N * logN)int end = n - 1;while (end > 0){Swap(&a[end], &a[0]);AdjustDown(a, end, 0);--end;}
}
void InsertSort(int* a, int n)
{for (int i = 1; i < n; i++){int end = i - 1;int tmp = a[i];// 将tmp插入到[0, end]区间中，保持有序while (end >= 0){if (tmp < a[end]){a[end + 1] = a[end];--end;}else{break;}}a[end + 1] = tmp;}
}
void IntroSort(int* a, int left, int right, int depth, int defaultDepth)
{if (left >= right)return;//数组长度小于16的小数组，换为插入排序，简单递归次数if (right - left + 1 < 16){InsertSort(a + left, right - left + 1);return;}//当深度超过2 * logN时改用堆排序if (depth > defaultDepth){HeapSort(a + left, right - left + 1);return;}depth++;int begin = left;int end = right;//随机选keyint randi = left + (rand() % (right - left + 1));Swap(&a[left], &a[randi]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur){Swap(&a[prev], &a[cur]);}++cur;}Swap(&a[prev], &a[keyi]);keyi = prev;// [begin, keyi-1] keyi [keyi+1, end]IntroSort(a, begin, keyi - 1, depth, defaultDepth);IntroSort(a, keyi + 1, end, depth, defaultDepth);
}
void QuickSort(int* a, int left, int right)
{int depth = 0;int logn = 0;int N = right - left + 1;for (int i = 1; i < N; i *= 2){logn++;}//introspective sort -- 自省排序IntroSort(a, left, right, depth, logn * 2);
}
int* sortArray(int* nums, int numsSize, int* returnSize) 
{srand(time(0));QuickSort(nums, 0, numsSize - 1);*returnSize = numsSize;return nums;
}

（四）归并排序

1、递归版本
//归并排序————递归版本
void _MergeSort(int* arr, int left, int right, int* tmp)
{//分解if (left >= right)//==也可以{return;}int mid = (left + right) / 2;//根据mid将[left,right]划分左右两个序列:[left,mid] [mid+1,right]_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);//合并两个序列：[left,mid] [mid+1,right]int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = left;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else {tmp[index++] = arr[begin2++];}}//要么begin1序列中数据没有放完//要么begin2序列中数据没有放完while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//tmp--》arrfor (int i = left; i <= right; i++){arr[i] = tmp[i];}
}
//归并排序
void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);//[0,n-1]_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}
2、非递归版本
#define  _CRT_SECURE_NO_WARNINGS  1//归并排序——非递归版本
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");exit(1);}int gap = 1;while (gap < n){//根据gap划分组，两两一合并for (int i = 0;i < n;i += 2*gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (begin2 >= n)//没有右序列{break;}if (end2 >= n)//右序列不满gap个{end2 = n - 1;}int index = begin1;//两个有序序列合并while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}//导入到原数组中memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//原数组开始拷贝的位置  目标位置  拷贝大小}gap *= 2;}
}
3、文件归并排序
#define  _CRT_SECURE_NO_WARNINGS  1
#include<stdio.h>
#include<time.h>
#include<stdlib.h>//创建N个随机数，写到文件中
void CreatNData()
{//造数据int n = 10000000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (int i = 0; i < n; ++i){int x = rand() + i;fprintf(fin, "% d\n", x);}fclose(fin);
}int compare(const void* a, const void* b)
{return(*(int*)a - *(int*)b);
}//返回实际读到的数据个数，没有数据了返回0
int ReadNDataSortToFile(FILE* fout, int n, const char* file1)
{int x = 0;int* a = (int*)malloc(sizeof(int) * n);if (a == NULL){perror("malloc error");return 0;}//想读取n个数据，如果遇到文件结束，应该读到j个int j = 0;for (int i = 0; i < n; i++){if (fscanf(fout, "%d", &x) == EOF)break;a[j++] = x;}if (j == 0){free(a);return 0;}//排序qsort(a, j, sizeof(int), compare);FILE* fin = fopen(file1, "w");if (fin == NULL){free(a);perror("fopen error");return 0;}//写回file1文件for (int i = 0; i < j; i++){fprintf(fin, "%d\n", a[j]);}free(a);fclose(fin);return j;
}void MergeFile(const char* file1, const char* file2, const char* mfile)
{FILE* fout1 = fopen(file1, "r");if (fout1 == NULL){perror("fopen error");return;}FILE* fout2 = fopen(file2, "r");if (fout2 == NULL){perror("fopen error");return;}FILE* mfin = fopen(mfile, "w");if (mfin == NULL){perror("fopen error");return;}//归并逻辑int x1 = 0;int x2 = 0;int ret1 = fscanf(fout1, "%d", &x1);int ret2 = fscanf(fout2, "%d", &x2);while (ret1 != EOF && ret2 != EOF){if (x1 < x2){fprintf(mfin, "%d\n", x1);ret1 = fscanf(fout1, "%d", &x1);}else{fprintf(mfin, "%d\n", x2);ret2 = fscanf(fout2, "%d", &x2);}}while (ret1 != EOF){fprintf(mfin, "%d\n", x1);ret1 = fscanf(fout1, "%d", &x1);}while (ret2 != EOF){fprintf(mfin, "%d\n", x2);ret2 = fscanf(fout2, "%d", &x2);}fclose(fout1);fclose(fout2);fclose(mfin);
}int main()
{CreatNData();const char* file1 = "file1.txt";const char* file2 = "file1.txt";const char* mfile = "file1.txt";FILE* fout = fopen("data.txt", "r");if (fout == NULL){perror("fopen error");return;}int m = 1000000;ReadNDataSortToFile(fout, m, file1);ReadNDataSortToFile(fout, m, file2);while (1){MergeFile(file1, file2, mfile);//删除file1和file2remove(file1);remove(file2);//重命名mfile为file1rename(mfile, file1);//当再去读取数据，一个都读不到，说明此时已经没有数据了//已经归并完成，归并结果在file1int n = 0;if ((n = ReadNDataSortToFile(fout, m, file2)) == 0)break;//if (n < 100)//{//	int x = 0;//}}return 0;
}

（五）非比较排序

1、计数排序
//非比较排序——计数排序
void CountSort(int* arr, int n)
{//找min maxint min = arr[0], max = arr[0];for (int i = 1; i < n; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}//确定count数组的大小 max-min+1int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * (range));if (count == NULL){perror("malloc fail");exit(1);}//对count初始化：calloc memsetmemset(count, 0, sizeof(int) * (range));for (int i = 0; i < n; i++){count[arr[i] - min]++;}//将count数组中的数据还原到原数组中int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;}}
}

（六）排序——完整代码

1、Stack.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;
typedef struct Stack
{STDataType* arr;int top;//定义栈中有效的数据个数int capacity;//栈的空间大小
}ST;//初始化
void STInit(ST* ps);//销毁
void STDestory(ST* ps);//入栈——栈顶
void STPush(ST* ps, STDataType x);//出栈——栈顶
void STPop(ST* ps);//取栈顶元素
STDataType STTop(ST* ps);//栈是否为空
bool STEmpty(ST* ps);//获取栈中有效元素个数
int STSize(ST* ps);
2、Stack.c
#define  _CRT_SECURE_NO_WARNINGS  1#include"Stack.h"//初始化
void STInit(ST* ps)
{ps->arr = NULL;ps->top = ps->capacity = 0;
}//销毁
void STDestory(ST* ps)
{if (ps->arr)free(ps->arr);ps->arr = NULL;ps->top = ps->capacity = 0;
}//入栈——栈顶
void STPush(ST* ps, STDataType x)
{assert(ps);//判断空间是否足够if (ps->top == ps->capacity){//增容int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->arr, newCapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}ps->arr = tmp;ps->capacity = newCapacity;}//空间足够ps->arr[ps->top++] = x;
}//栈是否为空
bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈——栈顶
void STPop(ST* ps)
{assert(!STEmpty(ps));ps->top--;
}//取栈顶元素
STDataType STTop(ST* ps)
{assert(!STEmpty(ps));return ps->arr[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
3、sort.h
#pragma once
#include<stdio.h>//插入排序
//1)随机插入排序 O(n^2)
void InsertSort(int* arr, int n);//2)希尔排序 O(n^1.3)
void ShellSort(int* arr, int n);//选择排序
//1)直接插入排序 O(n^2)
void SelectSort(int* arr, int n);//2)堆排序 O(nlogn)
void HeapSort(int* arr, int n);//交换排序
//1)冒泡排序
void BubbleSort(int* arr, int n);//2）快速排序
void QuickSort(int* arr, int left, int right);
//非递归版本快速排序——栈：栈+lomuto双指针
void QuickSortNorR(int* arr, int left,int right);////三路划分
//KeyWayIndex PartSort3Way(int* a, int left, int right);//三路划分实现
void QuickSort3Way(int* arr, int left, int right);//归并排序————递归版本
void MergeSort(int* arr, int n);//归并排序——非递归版本
void MergeSortNonR(int* arr, int n);//非比较排序——计数排序
void CountSort(int* arr, int n);
4、sort.c
#define  _CRT_SECURE_NO_WARNINGS  1
#include"sort.h"
#include"Stack.h"//1)随机插入排序 最差情况：O(N^2) 最好情况：O(N)
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}arr[end + 1] = tmp;}
}//2)希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++){int end = i;int tmp = arr[end + gap];while (end >= 0){if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}}arr[end + gap] = tmp;}}
}//交换——Swap方法
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//向下调整算法
void AdjustDown(int* arr, int parent, int n)
{int child = parent * 2 + 1;while (child < n){//找最大的孩子//建大堆：<//建小堆：>if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//孩子和父亲比较//建大堆：>//建小堆：<if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序————使用的是堆结构的思想
void HeapSort(int* arr, int n)
{//向下调整算法——建堆————O(N)//乱序数组————建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}////向上调整算法——建堆 N*logN//for (int i = 0; i < n; i++)//{//	AdjustUp(arr, i);//}//n*lognint end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);//lognend--;}
}//冒泡排序
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] < arr[j + 1]){Swap(&arr[j], arr[j + 1]);}}}
}//1)直接选择排序 O(n^2)
void SelectSort(int* arr, int n)
{int begin = 0, end = n - 1;while (begin < end){int mini = begin;int maxi = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] < arr[mini]){mini = i;}if (arr[i] > arr[maxi]){maxi = i;}}//maxi mini begin endif (maxi == begin){maxi = mini;}Swap(&arr[begin], &arr[mini]);Swap(&arr[end], &arr[maxi]);begin++;end--;}
}////2)希尔排序
//void ShellSort(int* arr, int n)
//{
//	int gap = n;
//	while (gap > 0)
//	{
//		gap = gap / 3 + 1;
//		for (int i = 0; i < gap; i++)
//		{
//			for (int i = 0; i < n - gap; i += gap)
//			{
//				int end = i;
//				int tmp = arr[end + gap];
//				while (end >= 0)
//				{
//					if (arr[end] > tmp)
//					{
//						arr[end + gap] = arr[end];
//						end -= gap;
//					}
//					else
//					{
//						break;
//					}
//				}
//				arr[end + gap] = tmp;
//			}
//		}
//	}
//}////1)直接选择排序 O(n^2)
//void SelectSort(int* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		int mini = i;
//		for (int j = i + 1; j < n; j++)
//		{
//			if (arr[j] < arr[mini])
//			{
//				mini = j;
//			}
//		}
//		//mini i
//		Swap(&arr[mini], &arr[i]);
//	}
//}//找基准值  hoare版本
int _QuickSort1(int* arr, int left,int right)
{int keyi = left;left++;while (left <= right){//right：从右往左找比基准值小的while (left <= right && arr[right] > arr[keyi]){--right;}//left：从右往左找比基准值大的while (left <= right && arr[left] < arr[keyi]){++left;}//left和right交换if (left <= right)Swap(&arr[left++], &arr[right--]);}//right的位置就是基准值的位置Swap(&arr[keyi], &arr[right]);return right;
}//找基准值  挖坑法
int _QuickSort2(int* arr, int left,int right)
{int hole = left;int key = arr[hole];while (left < right){while (left < right && arr[right] > key){right--;}arr[hole] = arr[right];hole = right;while (left < right && arr[left < key]){++left;}arr[hole] = arr[left];hole = left;}arr[hole] = key;return hole;
}//找基准值 lomuto双指针方法
int _QuickSort(int* arr, int left,int right)
{int prev = left, cur = prev + 1;int keyi = left;while (cur <= right){//cur数据和基准值比较if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[cur], & arr[prev]);}++cur;}Swap(&arr[keyi], &arr[prev]);return prev;
}//非递归版本快速排序——栈：栈+lomuto双指针
void QuickSortNorR(int* arr, int left,int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!STEmpty(&st)){//取栈顶两次int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);//[begin,end]————找基准值int keyi = begin;int prev = begin, cur = prev + 1;while (cur <= end){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}++cur;}Swap(&arr[prev], &arr[keyi]);keyi = prev;//begin  keyi  end//左序列[begin,keyi-1]//右序列[keyi+1,end]if (keyi + 1 < end){STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestory(&st);
}//introsort的快排排序OJ代码
//
////交换——Swap方法
//void Swap(int* x, int* y)
//{
//	int tmp = *x;
//	*x = *y;
//	*y = tmp;
//}
//
////向下调整算法
//void AdjustDown(int* arr, int parent, int n)
//{
//	int child = parent * 2 + 1;
//	while (child < n)
//	{
//		//找最大的孩子
//		//建大堆：<
//		//建小堆：>
//		if (child + 1 < n && arr[child] < arr[child + 1])
//		{
//			child++;
//		}
//		//孩子和父亲比较
//		//建大堆：>
//		//建小堆：<
//		if (arr[child] > arr[parent])
//		{
//			Swap(&arr[child], &arr[parent]);
//			parent = child;
//			child = parent * 2 + 1;
//		}
//		else
//		{
//			break;
//		}
//	}
//}
//
////堆排序————使用的是堆结构的思想
//void HeapSort(int* arr, int n)
//{
//	//向下调整算法——建堆 O(N)
//	//乱序数组————建堆
//	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
//	{
//		AdjustDown(arr, i, n);
//	}
//
//	////向上调整算法——建堆 N*logN
//	//for (int i = 0; i < n; i++)
//	//{
//	//	AdjustUp(arr, i);
//	//}
//
//	//n*logn
//	int end = n - 1;
//	while (end > 0)
//	{
//		Swap(&arr[0], &arr[end]);
//		AdjustDown(arr, 0, end);//logn
//		end--;
//	}
//}
////随机插入排序 最差情况：O(N ^ 2) 最好情况：O(N)
//void InsertSort(int* arr, int n)
//{
//	for (int i = 0; i < n - 1; i++)
//	{
//		int end = i;
//		int tmp = arr[end + 1];
//		//将tmp插入到[0,end]区间中，保持有序
//		while (end >= 0)
//		{
//			if (arr[end] > tmp)
//			{
//				arr[end + 1] = arr[end];
//				end--;
//			}
//			else
//			{
//				break;
//			}
//		}
//		arr[end + 1] = tmp;
//	}
//}////三路划分
//KeyWayIndex PartSort3Way(int* arr, int left, int right)
//{
//	int key = arr[left];
//
//	//left和right指向就是跟key相等的区间
//	//[begin,left-1]  [left,right]  [right+1,end]
//	int cur = left + 1;
//	while (cur <= right)
//	{
//		//1、cur遇到比key小，小的换到左边，同时把key换到中间位置
//		//2、cur遇到比key大，大的换到右边
//		if (arr[cur] < key)
//		{
//			Swap(&arr[cur], &arr[left]);
//			++left;
//			++cur;
//		}
//		else if (arr[cur] > key)
//		{
//			Swap(&arr[cur], &arr[right]);
//			//cur不能动
//			--right;
//		}
//		else
//		{
//			++cur;
//		}
//	}
//
//	KeyWayIndex kwi;
//	kwi.leftkeyi = left;
//	kwi.rightkeyi = right;
//	return kwi;
//}int _QuickSort3Way(int* arr, int left, int right)
{return;
}//三路划分实现
void QuickSort3Way(int* arr, int left, int right)
{if (left >= right){return;}//随机数取法srand((unsigned int)time(NULL));int randi = left + rand() % (right - left + 1);Swap(&arr[left], &arr[randi]);//三数取中int midi = _QuickSort3Way(arr, left, right);//三路划分int key = arr[left];int cur = left + 1;int begin = left;int end = right;while (cur <= right){//1、cur遇到比key小，小的换到左边，同时把key换到中间位置//2、cur遇到比key大，大的换到右边if (arr[cur] < key){Swap(&arr[cur], &arr[left]);++left;++cur;}else if (arr[cur] > key){Swap(&arr[cur], &arr[right]);//cur不能动--right;}else{++cur;}}//三路划分 [begin,left-1]  [left,right]  [right+1,end]QuickSort3Way(arr, begin, left - 1);QuickSort3Way(arr, right + 1, end);
}////三路划分实现
//void Swap(int* x, int* y)
//{
//	int tmp = *x;
//	*x = *y;
//	*y = tmp;
//}
//void QuickSort(int* arr, int left, int right)
//{
//	if (left >= right)
//		return;
//	int begin = left;
//	int end = right;
//	//随机选key
//	int randi = left + (rand() % (right - left + 1));
//	Swap(&arr[left], &arr[randi]);
//	//三路划分
//		//left和right指向就是跟key相等的区间
//		// [begin, left-1] [left, right] right+1, end]
//	int key = arr[left];
//	int cur = left + 1;
//	while (cur <= right)
//	{
//		//1、cur遇到比key小，小的换到左边，同时把key换到中间位置
//		//2、cur遇到比key大，大的换到右边
//		if (arr[cur] < key)
//		{
//			Swap(&arr[cur], &arr[left]);
//			++left;
//			++cur;
//		}
//		else if (arr[cur] > key)
//		{
//			Swap(&arr[cur], &arr[right]);
//			--right;
//		}
//		else
//		{
//			++cur;
//		}
//	}
//	// [begin, left-1] [left, right] right+1, end]
//	QuickSort(arr, begin, left - 1);
//	QuickSort(arr, right + 1, end);
//}
//int* sortArray(int* nums, int numsSize, int* returnSize) {
//	srand(time(0));
//	QuickSort(nums, 0, numsSize - 1);
//	*returnSize = numsSize;
//	return nums;
//}//自省排序(内观排序)
void IntroSort(int* arr, int left, int right, int depth, int defaultDepth)
{if (left >= right)return;//数组大小小于16的小数组，换为插入排序，简单递归次数if (right - left + 1 < 16){InsertSort(arr + left, right - left + 1);return;}//当深度超过2*logn，则改用堆排序if (depth > defaultDepth){HeapSort(arr + left, right - left + 1);return;}depth++;int begin = left;int end = right;//随机选keyint randi = left + (rand() % (right - left));Swap(&arr[left], &arr[right]);int prev = left;int cur = prev + 1;int keyi = left;while (cur <= right){if (arr[cur] < arr[keyi] && ++prev != cur){Swap(&arr[prev], &arr[cur]);}++cur;}Swap(&arr[prev], &arr[keyi]);keyi = prev;//[begin,keyi-1]  keyi  [keyi+1,end]IntroSort(arr, begin, keyi - 1, depth, defaultDepth);
}//2）快速排序
void QuickSort(int* arr, int left, int right)
{if (left >= right){return;}//找基准值keyiint keyi = _QuickSort(arr, left, right);//左序列[left,keyi-1]  右序列[keyi+1,right]QuickSort(arr, left, keyi - 1);QuickSort(arr, keyi + 1, right);
}//归并排序————递归版本
void _MergeSort(int* arr, int left, int right, int* tmp)
{//分解if (left >= right)//==也可以{return;}int mid = (left + right) / 2;//根据mid将[left,right]划分左右两个序列:[left,mid] [mid+1,right]_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);//合并两个序列：[left,mid] [mid+1,right]int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = left;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else {tmp[index++] = arr[begin2++];}}//要么begin1序列中数据没有放完//要么begin2序列中数据没有放完while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//tmp--》arrfor (int i = left; i <= right; i++){arr[i] = tmp[i];}
}
//归并排序
void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);//[0,n-1]_MergeSort(arr, 0, n - 1, tmp);free(tmp);
}#define  _CRT_SECURE_NO_WARNINGS  1#define  _CRT_SECURE_NO_WARNINGS  1//归并排序——非递归版本
void MergeSortNonR(int* a, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);if (tmp == NULL){perror("malloc fail!");exit(1);}int gap = 1;while (gap < n){//根据gap划分组，两两一合并for (int i = 0; i < n; i += 2 * gap){int begin1 = i, end1 = i + gap - 1;int begin2 = i + gap, end2 = i + 2 * gap - 1;if (begin2 >= n)//没有右序列{break;}if (end2 >= n)//右序列不满gap个{end2 = n - 1;}int index = begin1;//两个有序序列合并while (begin1 <= end1 && begin2 <= end2){if (a[begin1] < a[begin2]){tmp[index] = a[begin1++];}else{tmp[index++] = a[begin2++];}}while (begin1 <= end1){tmp[index] = a[begin1++];}while (begin2 <= end2){tmp[index++] = a[begin2++];}//导入到原数组中memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//原数组开始拷贝的位置 目标位置 拷贝大小}gap *= 2;}
}//非比较排序——计数排序
void CountSort(int* arr, int n)
{//找min maxint min = arr[0], max = arr[0];for (int i = 1; i < n; i++){if (arr[i] < min){min = arr[i];}if (arr[i] > max){max = arr[i];}}//确定count数组的大小 max-min+1int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * (range));if (count == NULL){perror("malloc fail");exit(1);}//对count初始化：calloc memsetmemset(count, 0, sizeof(int) * (range));for (int i = 0; i < n; i++){count[arr[i] - min]++;}//将count数组中的数据还原到原数组中int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;}}
}
5、test.c
#define  _CRT_SECURE_NO_WARNINGS  1
#include"sort.h"
#include"Stack.h"void  printArr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test01()
{int arr[] = { 5,3,9,6,2,4,7,1,8 };int n = sizeof(arr) / sizeof(arr[0]);printf("排序之前：");printArr(arr, n);//InsertSort(arr,n);//ShellSort(arr, n);//SelectSort(arr, n);//QuickSort(arr, 0, n - 1);//QuickSortNorR(arr, 0, n - 1);//IntroSort(arr, 0, n - 1, arr, n);//QuickSort3Way(arr, 0, n - 1);//MergeSort(arr, n);//MergeSortNonR(arr, n);CountSort(arr, n);printf("排序之后：");printArr(arr, n);
}// 测试排序的性能对比
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{test01();/*TestOP();*/return 0;
}//int main1()
//{
//	//test01();
//	int arr[100] = { 5,3,9,6,2,4,7,1,8 };
//
//	printf("排序之前：\n");
//	for (int i = 0; i < 6; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//	printf("\n");
//
//	HeapSort(arr, 6);
//	//BubbleSort(arr, 6);
//
//	printf("排序之后：\n");
//	for (int i = 5; i >= 0; i--)
//	{
//		printf("%d ", arr[i]);
//	}
//	printf("\n");
//	return 0;
//}

（七）对比排序性能：测试代码

​
//测试排序的性能对比  
void TestOP()
{srand(time(0));const int N = 100000;int* a1 = (int*)malloc(sizeof(int) * N);int* a2 = (int*)malloc(sizeof(int) * N);int* a3 = (int*)malloc(sizeof(int) * N);int* a4 = (int*)malloc(sizeof(int) * N);int* a5 = (int*)malloc(sizeof(int) * N);int* a6 = (int*)malloc(sizeof(int) * N);int* a7 = (int*)malloc(sizeof(int) * N);for (int i = 0; i < N; ++i){a1[i] = rand();a2[i] = a1[i];a3[i] = a1[i];a4[i] = a1[i];a5[i] = a1[i];a6[i] = a1[i];a7[i] = a1[i];}//begin和end的时间差就是int begin1 = clock();InsertSort(a1, N);int end1 = clock();int begin2 = clock();ShellSort(a2, N);int end2 = clock();int begin3 = clock();SelectSort(a3, N);int end3 = clock();int begin4 = clock();HeapSort(a4, N);int end4 = clock();int begin5 = clock();QuickSort(a5, 0, N - 1);int end5 = clock();int begin6 = clock();MergeSort(a6, N);int end6 = clock();int begin7 = clock();BubbleSort(a7, N);int end7 = clock();printf("InsertSort:%d\n", end1 - begin1);printf("ShellSort:%d\n", end2 - begin2);printf("SelectSort:%d\n", end3 - begin3);printf("HeapSort:%d\n", end4 - begin4);printf("QuickSort:%d\n", end5 - begin5);printf("MergeSort:%d\n", end6 - begin6);printf("BubbleSort:%d\n", end7 - begin7);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}​

结尾

要回顾的文章数量太多，我们这里就只放排序部分的博客链接啦！

往期回顾：

【数据结构与算法】数据结构初阶：排序内容加餐（二）——文件归并排序思路详解（附代码实现）

本期内容需要回顾的C语言知识如下面的截图中所示（指针博主写了6篇，列出来有水字数嫌疑了，就只放指针第六篇的网址，博主在指针（六）把指针部分的前五篇的网址都放在【往期回顾】了，点击【传送门】就可以看了）。

大家如果对前面部分的知识点印象不深，可以去上一篇文章的结尾部分看看，博主把需要回顾的知识点相关的博客的链接都放在上一篇文章了，上一篇文章的链接博主放在下面了：

【数据结构与算法】数据结构初阶：详解顺序表和链表（三）——单链表（上）

结语：本篇文章到这里就结束了，对数据结构的二叉树知识感兴趣的友友们可以在评论区留言，博主创作时可能存在笔误，或者知识点不严谨的地方，大家多担待，如果大家在阅读的时候发现了行文有什么错误欢迎在评论区斧正，再次感谢友友们的关注和支持！  

http://www.lryc.cn/news/610584.html

相关文章：

  • 深度学习·基础知识
  • LG P2480 [SDOI2010] 古代猪文 Solution
  • 云平台监控-Zabbix企业级高级应用
  • ＜八＞ Docker安装oracle11.2.0.4库
  • 亚马逊账号关联全解析：从风险底层逻辑到高阶防控策略
  • 计算机视觉CS231n学习（3）
  • Vulnhuntr：用于识别远程可利用漏洞的开源工具
  • 《C++初阶之STL》【模板参数 + 模板特化 + 分离编译】
  • PCIe Base Specification解析（七）
  • 私有云盘新体验：FileRise在cpolar的加持下如何让数据管理更自由？
  • 24. 前端-js框架-Vue
  • Redis内存耗尽时的应对策略
  • K8S的NetworkPolicy使用教程
  • 升级 Elasticsearch 到新的 AWS Java SDK
  • iouring系统调用及示例
  • 学习游戏制作记录（将各种属性应用于战斗以及实体的死亡）8.5
  • 从循环嵌套到拓扑编排：LangGraph如何重构Agent工作流
  • 面向对象的七大设计原则
  • 【2025WACV-目标检测方向】
  • 目标检测、分割的数据增强策略
  • 智慧社区物业管理平台登录流程全解析：从验证码到JWT认证
  • 分布式网关技术 + BGP EVPN，解锁真正的无缝漫游
  • Java 异步编程工具类 CompletableFuture 详细介绍
  • CodeRush AI 助手进驻 Visual Studio：AiGen/AiFind 亮相（四）
  • 自然语言翻译--seq2seq
  • JavaWeb（苍穹外卖）--学习笔记17（Websocket）
  • 【题解】P3172 [CQOI2015] 选数（倍数莫反做法）
  • Spring-rabbit使用实战六
  • 智慧会所：科技赋能，开启休闲新体验
  • 计算机算术5-整形除法