排序算法_期末复习笔记
头文件#include <stdio.h>
#include <string>
直接插入排序
//直接插入排序（普通版本）
void InsertSort0(int A[], int n)
{
int i, j, temp;
for (i = 1; i < n; i++)
{
if (A < A)
{
temp = A;
for (j = i - 1; j >= 0 && A > temp; --j)
{
A = A;
}
A = temp;
}
}
}
//直接插入排序（带哨兵）
void InsertSort1(int A[], int n)
{
int i, j;
for (i = 2; i <= n; i++)
{
if (A < A)
{
A = A;//A为哨兵，不带元素
for (j = i - 1; A < A; --j)
{
A = A;
}
A = A;
}
}
}
折半插入排序
//折半插入排序
void InsertSort2(int A[], int n)
{
int i, j, low, high, mid;
for (i = 2; i <= n; i++)
{
A = A;
low = 1; high = i - 1; //设置折半查找范围
while (low <= high)
{
mid = (low + high) / 2;//取中间点
if (A > A)
{
high = mid - 1;//查找左半值表
}
else
{
low = mid + 1; //查找右半值表
}
}
for (j = i - 1; j >= high + 1; j--)
{
A = A; //统一后移元素，空出插入位置
}
A = A;//插入操作
}
}
冒泡排序
//冒泡排序
//交换函数（可用于堆排序）
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 > A)
{
swap(A, A);
flag = true;
}
}
if (flag == false)
{
return;
}
}
}
快速排序
//快速排序
//满足条件左右划分函数
int Partition(int A[], int low, int high)
{
int pivot = A;
while (low < high)
{
while (low < high && A >= pivot)
{
--high;
}
A = A;
while (low < high && A <= pivot)
{
++low;
}
A = A;
}
A = 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 < A)
{
min = j;
}
}
if (min != i)
{
int temp = A;
A = A;
A = temp;
}
}
}
堆排序
//堆排序算法
/*-----------------------------------------------------------
A是存储堆的数组，k是需要检查的结点小标，len是堆中结点个数
-----------------------------------------------------------*/
void AdjustDown(int A[], int k, int len)
{
A = A; //A暂存这个需要检查的结点值
/*------------------------------------------------------------------------------
从这个结点的左孩子开始往下比较,
如果发生交换，对交换过的结点继续和它的孩子比较
-------------------------------------------------------------------------------*/
for (int i = 2 * k; i <= len; i *= 2)
{
if (i < len && A < A)//如果右孩子大一些，只需要考虑和右孩子比较
{
i++;
}
if (A >= A)//如果这个结点的值不小于它的较大孩子结点值，则不需要交换
{
break;
}
else
{
A = A;//结点值则将较大的孩子结点值赋值给该结点
k = i;//从i开始，继续往下检查，直到所有及诶单检查结束
}
}
A = A;//检查到最后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, A);
/*
int temp = A;
A = A;
A = temp;
*/
//printf(A);
AdjustDown(A, 1, i - 1); //把余下的i-1个元素整理成堆
}
}
归并排序
//归并排序
/*-------------------------------------------------------
思想：
表A的两段A和A各自有序，
将它们合并成一个有序表
--------------------------------------------------------*/
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 = A;//将A的元素复制到B中
}
for (i = low, j = mid + 1, k = i; i <= mid && j <= high; k++)//k是归并之后数组的下标计数器
{
if (B <= B)//比较B的左右两段中的元素
{
A = B;//将最小值复制到A中
}
else
{
A = B;
}
}
while (i <= mid)//若第一个表未检测完，直接将剩下的元素复制过来
{
A = B;
}
while (j <= high)//若第二个表未检测完，直接将剩下的元素复制过来
{
A = B;
}
}
//归并排序算法实现
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);
}
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;
}
页:
[1]