排序算法_期末复习笔记

黎羽轩 · 发表于 2022-7-24 09:54:34

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

头文件

#include <stdio.h>
#include <string>

复制代码

直接插入排序

//直接插入排序（普通版本）
void InsertSort0(int A[], int n)
{
int i, j, temp;
for (i = 1; i < n; i++)
{
if (A[i] < A[i - 1])
{
temp = A[i];
for (j = i - 1; j >= 0 && A[j] > temp; --j)
{
A[j + 1] = A[j];
}
A[j + 1] = temp;
}
}
}
//直接插入排序（带哨兵）
void InsertSort1(int A[], int n)
{
int i, j;
for (i = 2; i <= n; i++)
{
if (A[i] < A[i - 1])
{
A[0] = A[i]; //A[0]为哨兵，不带元素
for (j = i - 1; A[0] < A[j]; --j)
{
A[j + 1] = A[j];
}
A[j + 1] = A[0];
}
}
}

复制代码

折半插入排序

//折半插入排序
void InsertSort2(int A[], int n)
{
int i, j, low, high, mid;
for (i = 2; i <= n; i++)
{
A[0] = A[i];
low = 1; high = i - 1; //设置折半查找范围
while (low <= high)
{
mid = (low + high) / 2; //取中间点
if (A[mid] > A[0])
{
high = mid - 1; //查找左半值表
}
else
{
low = mid + 1; //查找右半值表
}
}
for (j = i - 1; j >= high + 1; j--)
{
A[j + 1] = A[j]; //统一后移元素，空出插入位置
}
A[high + 1] = A[0]; //插入操作
}
}

复制代码

冒泡排序

//冒泡排序
//交换函数（可用于堆排序）
void swap(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
//冒泡排序算法
void BubbleSort(int A[], int n)
{
for (int i = 0; i < n - 1; i++)
{
bool flag = false; //表示本趟冒泡是否发生交换的标志
for (int j = n - 1; j > i; j--)
{
if (A[j - 1] > A[j])
{
swap(A[j - 1], A[j]);
flag = true;
}
}
if (flag == false)
{
return;
}
}
}

复制代码

快速排序

//快速排序
//满足条件左右划分函数
int Partition(int A[], int low, int high)
{
int pivot = A[low];
while (low < high)
{
while (low < high && A[high] >= pivot)
{
--high;
}
A[low] = A[high];
while (low < high && A[low] <= pivot)
{
++low;
}
A[high] = A[low];
}
A[low] = pivot;
return low;
}
//快速排序算法
void QuickSort(int A[], int low, int high)
{
if (low < high) //调出递归的条件
{
int pivotpos = Partition(A, low, high); //划分
QuickSort(A, low, pivotpos - 1);
QuickSort(A, pivotpos + 1, high);
}
}

复制代码

简单选择排序

//简单选择排序
void SelectSort(int A[], int n)
{
int i, j, min;
for (i = 0; i < n - 1; i++)
{
min = i;
for (j = i + 1; j < n; j++)
{
if (A[j] < A[min])
{
min = j;
}
}
if (min != i)
{
int temp = A[i];
A[i] = A[min];
A[min] = temp;
}
}
}

复制代码

堆排序

//堆排序算法
/*-----------------------------------------------------------
A是存储堆的数组，k是需要检查的结点小标，len是堆中结点个数
-----------------------------------------------------------*/
void AdjustDown(int A[], int k, int len)
{
A[0] = A[k]; //A[0]暂存这个需要检查的结点值
/*------------------------------------------------------------------------------
从这个结点的左孩子开始往下比较,
如果发生交换，对交换过的结点继续和它的孩子比较
-------------------------------------------------------------------------------*/
for (int i = 2 * k; i <= len; i *= 2)
{
if (i < len && A[i] < A[i + 1]) //如果右孩子大一些，只需要考虑和右孩子比较
{
i++;
}
if (A[0] >= A[i]) //如果这个结点的值不小于它的较大孩子结点值，则不需要交换
{
break;
}
else
{
A[k] = A[i]; //结点值则将较大的孩子结点值赋值给该结点
k = i; //从i开始，继续往下检查，直到所有及诶单检查结束
}
}
A[k] = A[0]; //检查到最后k的值就是最后一轮交换过的结点位置下标，将该结点换过去
}
void BuildMaxHeap(int A[], int len)
{
/*----------------------------------------------------------------
由数组小标高处往低处，从第一个可能需要调整的非叶结点开始检查，
直到根结点（注意根结点不是从0开始的，而是1）
------------------------------------------------------------------*/
for (int i = len / 2; i > 0; i--)
{
AdjustDown(A, i, len);
}
}
//算法实现
void HeapSort(int A[], int len)
{
BuildMaxHeap(A, len);//初始化建堆
for (int i = len; i > 1; i--) //n-1趟的交换和建堆过程
{
//输出对顶元素（和堆底元素交换）
swap(A[i], A[1]);
/*
int temp = A[i];
A[i] = A[1];
A[1] = temp;
*/
//printf(A[i]);
AdjustDown(A, 1, i - 1); //把余下的i-1个元素整理成堆
}
}

复制代码

归并排序

//归并排序
/*-------------------------------------------------------
思想：
表A的两段A[low...mid]和A[mid+1...high]各自有序，
将它们合并成一个有序表
--------------------------------------------------------*/
void Merge(int A[], int low, int mid, int high)
{
//辅助数组B
int *B = (int *)malloc((high + 1) * sizeof(int));
int i, j, k;
for (k = low; k <= high; k++)
{
B[k] = A[k]; //将A的元素复制到B中
}
for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++) //k是归并之后数组的下标计数器
{
if (B[i] <= B[j]) //比较B的左右两段中的元素
{
A[k] = B[i++]; //将最小值复制到A中
}
else
{
A[k] = B[j++];
}
}
while (i <= mid) //若第一个表未检测完，直接将剩下的元素复制过来
{
A[k++] = B[i++];
}
while (j <= high) //若第二个表未检测完，直接将剩下的元素复制过来
{
A[k++] = B[j++];
}
}
//归并排序算法实现
void MergeSort(int A[], int low, int high)
{
if (low < high)
{
int mid = (low + high) / 2; //从中间划分两个子序列
MergeSort(A, low, mid); //从左侧子序列进行归并排序
MergeSort(A, mid + 1, high); //从右侧子序列进行归并排序
Merge(A, low, mid, high); //归并为一个数组
}
}

复制代码

辅助函数

//测试数组打印的结果是否满足需求
void ArryShow(int A[], int n)
{
for (int i = 0; i < n; i++)
{
printf("%d ", A[i]);
}
printf("\n");
}

复制代码

main函数

int main()
{
printf("\n------直接插入排序（普通版）------\n");
int A0[] = { 49,38,65,97,76,13,27,49 };
printf("\n排序前："); ArryShow(A0, 8);
InsertSort0(A0, 8);
printf("\n排序后："); ArryShow(A0, 8);
printf("\n------直接插入排序（带哨兵）------\n");
int A1[] = { 55,23,45,78,97,11,24,65 };
printf("\n排序前："); ArryShow(A1, 8);
InsertSort1(A1, 7);
printf("\n排序后："); ArryShow(A1, 8);
printf("\n------折半插入排序------\n");
int A2[] = { 34,45,67,12,31,89,95,87 };
printf("\n排序前："); ArryShow(A2, 8);
InsertSort2(A2, 7);
printf("\n排序后："); ArryShow(A2, 8);
printf("\n------冒泡排序------\n");
int A3[] = { 1,4,8,7,3,6,2,5 };
printf("\n排序前："); ArryShow(A3, 8);
BubbleSort(A3, 8);
printf("\n排序后："); ArryShow(A3, 8);
printf("\n------快速排序------\n");
int A4[] = { 32,23,56,42,88,79,67,55 };
printf("\n排序前："); ArryShow(A4, 8);
QuickSort(A4, 0, 7);
printf("\n排序后："); ArryShow(A4, 8);
printf("\n------简单选择排序------\n");
int A5[] = { 23,45,89,87,54,45,32,66 };
printf("\n排序前："); ArryShow(A5, 8);
SelectSort(A5, 8);
printf("\n排序后："); ArryShow(A5, 8);
printf("\n------堆排序------\n");
int A6[] = { -1,52,45,23,100,45,92 };
printf("\n排序前："); ArryShow(A6, 7);
HeapSort(A6, 6);
printf("\n排序后："); ArryShow(A6, 7);
printf("\n------归并排序------\n");
int A7[] = { 49,38,65,97,76,13,27 };
printf("\n排序前："); ArryShow(A7, 7);
MergeSort(A7, 0,6);
printf("\n排序后："); ArryShow(A7, 7);
return 0;
}

复制代码

账号		自动登录	找回密码
密码			立即注册

[技术交流] 排序算法_期末复习笔记

马上注册，结交更多好友，享用更多功能^_^