#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define FALSE 0
#define MaxSize 100000
#define TRUE 1
typedef int KeyType;
typedef int DataType;
typedef int BOOL;
typedef struct entry
{
KeyType key;
DataType data;
}Entry;
typedef struct list
{
int n;
Entry D[MaxSize];
}List;
int FindMin(List list, int startIndex) //在stretIndex至表尾范围内找到最小关键字元素下标
{
int i, minIndex = startIndex;
for (i = startIndex + 1; i < list.n; i++)
{
if (list.D[i].key < list.D[minIndex].key)
minIndex = i;
}
return minIndex;
}
void Swap(Entry* D, int i, int j) //交换顺序表中两个元素位置
{
Entry temp;
if (i == j)
return;
temp = *(D + i);
*(D + i) = *(D + j);
*(D + j) = temp;
}
void SelectSort(List* list)
{
int minIndex, startIndex = 0;
while (startIndex < list->n - 1)
{
minIndex = FindMin(*list, startIndex);
Swap(list->D, startIndex, minIndex);
startIndex++;
}
}
void InsertSort(List* list)
{
int i, j; //i为待插入元素下标
Entry insertItem; //每一趟待插入元素
for (i = 1; i < list->n; i++)
{
insertItem = list->D[i];
for (j = i - 1; j >= 0; j--)
{
//不断将有序序列中元素向后移动,为待插入元素空出一个位置
if (insertItem.key < list->D[i].key)
list->D[j + 1] = list->D[j];
else break;
}
list->D[j + 1] = insertItem; //待插入元素有序存放至有序序列中
}
}
void BubbleSort(List* list)
{
int i, j; //i标识每趟排序范围最后一个元素下标,每趟排序元素下表范围是0~i
for (i = list->n - 1; i > 0; i--)
{
BOOL isSwap = FALSE; //标记一趟排序中是否发生了元素交换
for (j = 0; j < i; j++)
{
if (list->D[j].key > list->D[j + 1].key)
{
Swap(list->D, j, j + 1);
isSwap = TRUE;
}
}
if (!isSwap) break; //如果本趟排序没有发生元素交换,排序完成
}
}
int Partition(List* list, int low, int high) {
int i = low, j = high + 1;
Entry pivot = list->D[low]; //pivot是分割元素
do {
do i++;
while (list->D[i].key < pivot.key); //i前进
do j--;
while (list->D[j].key > pivot.key); //j前进
if (i < j) Swap(list->D, i,j);
} while (i < j);
Swap(list ->D, low, j);
return j; //此时j是分割元素下标
}
void QuickSort(List* list, int low, int high) { //快速排序的递归函数
int k;
if (low < high) { //当前待排序序列至少包含2个元素
k = Partition(list, low, high);
QuickSort(list, low, k - 1);
QuickSort(list, k + 1, high);
}
}
void Merge(List* list, Entry* temp, int low, int n1, int n2) {
int i = low, j = low + n1; //i,j初始时分别指向两个序列的第一个元素
while (i <= low + n1 - 1 && j <= low + n1 + n2 - 1) {
if (list->D[i].key <= list->D[j].key)
*temp++ = list->D[i++];
else *temp++ = list->D[j++];
}
while (i <= low + n1 - 1)
*temp++ = list->D[i++]; //剩余元素直接拷贝至temp
while (j <= low + n1 + n2 - 1)
*temp++ = list->D[j++]; //剩余元素直接拷贝至temp
}
//两路合并排序算法
void MergeSort(List* list) {
Entry temp[MaxSize];
int low, n1, n2, i, size = 1;
while (size < list->n) {
low = 0; //low是一对待合并序列中第一个序列的第一个元素下标
while (low + size < list->n) {
//low+size < list->n说明至少存在两个子序列需要合并
n1 = size;
if (low + size * 2 < list->n) n2 = size; //计算第二个序列长度
else n2 = list->n - low - size;
Merge(list, temp, low, n1, n2);
low += n1 + n2; //确定下一对待合并序列中第一个序列的第一个元素下标
}
for (i = 0; i < list->n; i++) {
list->D[i] = temp[i]; //复制一趟合并排序结果
}
size *= 2; //子序列长度翻倍
}
}
void Down(int array[], int i, int n) { // 最后结果就是大顶堆
int parent = i; // 父节点下标
int child = 2 * i + 1; // 子节点下标
while (child < n) {
if (array[child] < array[child + 1] && child + 1 < n) { // 判断子节点那个大,大的与父节点比较
child++;
}
if (array[parent] < array[child]) { // 判断父节点是否小于子节点
Swap(array, parent, child); // 交换父节点和子节点
parent = child; // 子节点下标 赋给 父节点下标
}
child = child * 2 + 1; // 换行,比较下面的父节点和子节点
}
}
void BuildHeap(int array[], int size) {
for (int i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆,必须从下往上比较
Down(array, i, size); // 否则有的不符合大顶堆定义
}
}
void HeapSort(int array[], int size) {
BuildHeap(array, size); // 初始化堆
for (int i = size - 1; i > 0; i--) {
Swap(array, 0, i); // 交换顶点和第 i 个数据
// 因为只有array[0]改变,其它都符合大顶堆的定义,所以可以从上往下重新建立
Down(array, 0, i); // 重新建立大顶堆
}
}
void timeprint()
{
printf("%.2lf\n", 1000*((double)clock() / CLOCKS_PER_SEC));
}
int start(int n)
{
int *a=0;
int i;
a = (int*)malloc(sizeof(int) * n);
for (i = 0; i < n; i++)
{
a[i] = rand();
}
return a;
}
int main()
{
int* a;
a=start(500);
SelectSort(a);
printf("简单选择排序算法时间为:");
timeprint();
free(a);
a = start(500);
InsertSort(a);
printf("\n直接插入排序算法时间为:");
timeprint();
free(a);
a = start(500);
BubbleSort(a);
printf("\n冒泡排序算法时间为:");
timeprint();
free(a);
a = start(500);
QuickSort(a, 0, 499);
printf("\n快速排序算法时间为:");
timeprint();
free(a);
a = start(500);
MergeSort(a);
printf("\n两路合并排序算法时间为:");
timeprint();
free(a);
a = start(500);
HeapSort(a,500);
printf("\n堆排序算法时间为:");
timeprint();
free(a);
return 0;
}
各位大佬帮我看一下,为啥我这个没有东西输出来,程序运行是成功的
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
1条回答 默认 最新
悬赏问题
- ¥15 做个有关计算的小程序
- ¥15 MPI读取tif文件无法正常给各进程分配路径
- ¥15 如何用MATLAB实现以下三个公式(有相互嵌套)
- ¥30 关于#算法#的问题:运用EViews第九版本进行一系列计量经济学的时间数列数据回归分析预测问题 求各位帮我解答一下
- ¥15 setInterval 页面闪烁,怎么解决
- ¥15 如何让企业微信机器人实现消息汇总整合
- ¥50 关于#ui#的问题:做yolov8的ui界面出现的问题
- ¥15 如何用Python爬取各高校教师公开的教育和工作经历
- ¥15 TLE9879QXA40 电机驱动
- ¥20 对于工程问题的非线性数学模型进行线性化