C语言版常见的各种排序算法(…

2024-08-31 19:38
文章标签 算法 常见 排序 语言版

本文主要是介绍C语言版常见的各种排序算法(…,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

原文地址:C语言版常见的各种排序算法(原文网址:http://hi.baidu.com/david%5Fjun/blog/item/c59afe350ae285bc5f 作者:面包会有的

#include <iostream>
#include
<ctime>
constint SIZE =100;
constint MAX =1000;
usingnamespace std;

//交换数据
void Swap(int&a, int&b)
{
int temp = a;
a
= b;
b
= temp;
}

//冒泡排序
void BubbleSort(int*arr, int size)
{
int i, j;
for(i=0;i<size-1;i++)
for(j=size-1;j>i;j--)
if(arr[j] < arr[j-1])
Swap(arr[j], arr[j
-1]);
}

//选择排序
void SelectionSort(int*arr, int size)
{
int i, j, min;
//找出从a[i]到a[size-1]的最小元素的位置
for(i=0;i<size-1;i++)
{
min
= i;
for(j=i+1;j<size;j++)
if(arr[min] > arr[j])
min
= j;
//将a[i]与a[min]的数据交换
Swap(arr[i], arr[min]);
}
}

//插入排序
void InsertSort(int*arr, int size)
{
int fOut, loc, temp;
for(fOut=1;fOut<size;fOut++)
if(arr[fOut] < arr[fOut-1])
{
temp
= arr[fOut];
loc
= fOut;
do
{
arr[loc]
= arr[loc-1];
loc
--;
}
while(loc>0&& arr[loc-1]>temp);
arr[loc]
= temp;
}
}

//快速排序
int Partition(int*arr, int first, int last)
{
int i, small, x;
//为了减少最差情况的出现频率而作的一种优化
swap(arr[first], arr[ (first+last)/2 ]);
x
= arr[first];
small
= first;
for(i=first+1;i<=last;i++)
if(arr[i] < x)
{
small
++;
swap(arr[small], arr[i]);
}
swap(arr[first], arr[small]);
return small;
}

void RecQuick(int*arr, int first, int last)
{
int pivotLoc;
if(first < last)
{
pivotLoc
= Partition(arr, first, last);
RecQuick(arr, first, pivotLoc
-1);
RecQuick(arr, pivotLoc
+1, last);
}
}

void QuickSort(int*arr, int size)
{
RecQuick(arr,
0, size-1);
}

//计数排序
void CountSort(int*arr, int size)
{
int temp[MAX] = {0};
int i, j;
for(i=0;i<size;i++)
temp[arr[i]]
++;
j
=0;
for(i=0;i<MAX;i++)
{
while(0!= temp[i])
{
arr[j]
= i;
temp[i]
--;
j
++;
}
}
}

//归并排序
void Merge(int*arr, int start, int mid, int end)
{
int temp1[SIZE], temp2[SIZE];
int n1, n2;
int i, j, k;
n1
= mid - start +1;
n2
= end - mid;
//拷贝前半部分数组
for(i=0;i<n1;i++)
temp1[i]
= arr[start + i];
//拷贝后半部分数组
for(i=0;i<n2;i++)
temp2[i]
= arr[mid + i +1];
//把后面的元素设置的很大
temp1[n1] = temp2[n2] = INT_MAX;
i
= j =0;
// 逐个扫描两部分数组然后放到相应的位置去
for(k=start;k<=end;k++)
{
if(temp1[i] <= temp2[j])
{
arr[k]
= temp1[i];
i
++;
}
else
{
arr[k]
= temp2[j];
j
++;
}
}
}

void RecMerge(int*arr, int start, int end)
{
int i;
if(start < end)
{
i
= (start + end) /2;
RecMerge(arr, start, i);
RecMerge(arr, i
+1, end);
Merge(arr, start, i, end);
}
}

void MergeSort(int*arr, int size)
{
RecMerge(arr,
0, size-1);
}

//堆排序
void Heapify(int*arr, int low, int high)
{
int large;
int temp = arr[low];
large
=2* low +1;
while(large <= high)
{
if(large<high && arr[large]<arr[large+1])
large
= large +1;
if(temp > arr[large])
break;
else
{
arr[low]
= arr[large];
low
= large;
large
=2* low +1;
}
}
arr[low]
= temp;
}

void BuildHeap(int*arr, int size)
{
int i;
for(i=size/2-1;i>=0;i--)
Heapify(arr, i, size
-1);
}

void HeapSort(int*arr, int size)
{
int i; //lastOfOrder
BuildHeap(arr, size);
for(i=size-1;i>=0;i--)
{
swap(arr[
0], arr[i]);
Heapify(arr,
0, i-1);
}
}

//希尔排序
void ShellSort(int*arr, int size)
{
int i, j, k, temp;
//i为增量
for(i=size/2;i>0;i/=2)
{
for(j=i;j<size;j+=i)
{
temp
= arr[j];
k
= j;
while(k-i>=0&& temp<arr[k-i])
{
arr[k]
= arr[k-i];
k
-= i;
}
arr[k]
= temp;
}
}
}

//输出数组里的数据
void Print(int*arr, int size)
{
int i;
for(i=0;i<size;i++)
{
printf(
"m ", arr[i]);
if(0== (i+1) %10)
cout
<< endl;
}
cout
<< endl;
}

//主函数
//先随机选择100个整型数据放入数组中,并输出
//然后将其从小到大排序,并输出
int main()
{
int arr[SIZE], i;
cout
<<"The array is: "<< endl;
srand((unsigned)time(
0));
for(i=0;i<SIZE;i++)
arr[i]
= rand() % MAX;
Print(arr, SIZE);

//请选择其中一个排序算法,以运行该程序
//BubbleSort(arr, SIZE);
//SelectionSort(arr, SIZE);
//CountSort(arr, SIZE);
//InsertSort(arr, SIZE);
//SelectionSort(arr, SIZE);
//QuickSort(arr, SIZE);
//MergeSort(arr, SIZE);
//HeapSort(arr, SIZE);
ShellSort(arr, SIZE);

cout
<<"After sorting, the array is:"<< endl;
Print(arr, SIZE);
return0;
}

这篇关于C语言版常见的各种排序算法(…的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1124818

相关文章

Python中反转字符串的常见方法小结

《Python中反转字符串的常见方法小结》在Python中,字符串对象没有内置的反转方法,然而,在实际开发中,我们经常会遇到需要反转字符串的场景,比如处理回文字符串、文本加密等,因此,掌握如何在Pyt... 目录python中反转字符串的方法技术背景实现步骤1. 使用切片2. 使用 reversed() 函

MySQL 中的 CAST 函数详解及常见用法

《MySQL中的CAST函数详解及常见用法》CAST函数是MySQL中用于数据类型转换的重要函数,它允许你将一个值从一种数据类型转换为另一种数据类型,本文给大家介绍MySQL中的CAST... 目录mysql 中的 CAST 函数详解一、基本语法二、支持的数据类型三、常见用法示例1. 字符串转数字2. 数字

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Python中win32包的安装及常见用途介绍

《Python中win32包的安装及常见用途介绍》在Windows环境下,PythonWin32模块通常随Python安装包一起安装,:本文主要介绍Python中win32包的安装及常见用途的相关... 目录前言主要组件安装方法常见用途1. 操作Windows注册表2. 操作Windows服务3. 窗口操作

ModelMapper基本使用和常见场景示例详解

《ModelMapper基本使用和常见场景示例详解》ModelMapper是Java对象映射库,支持自动映射、自定义规则、集合转换及高级配置(如匹配策略、转换器),可集成SpringBoot,减少样板... 目录1. 添加依赖2. 基本用法示例:简单对象映射3. 自定义映射规则4. 集合映射5. 高级配置匹

深度解析Python装饰器常见用法与进阶技巧

《深度解析Python装饰器常见用法与进阶技巧》Python装饰器(Decorator)是提升代码可读性与复用性的强大工具,本文将深入解析Python装饰器的原理,常见用法,进阶技巧与最佳实践,希望可... 目录装饰器的基本原理函数装饰器的常见用法带参数的装饰器类装饰器与方法装饰器装饰器的嵌套与组合进阶技巧

Mysql常见的SQL语句格式及实用技巧

《Mysql常见的SQL语句格式及实用技巧》本文系统梳理MySQL常见SQL语句格式,涵盖数据库与表的创建、删除、修改、查询操作,以及记录增删改查和多表关联等高级查询,同时提供索引优化、事务处理、临时... 目录一、常用语法汇总二、示例1.数据库操作2.表操作3.记录操作 4.高级查询三、实用技巧一、常用语

python 常见数学公式函数使用详解(最新推荐)

《python常见数学公式函数使用详解(最新推荐)》文章介绍了Python的数学计算工具,涵盖内置函数、math/cmath标准库及numpy/scipy/sympy第三方库,支持从基础算术到复杂数... 目录python 数学公式与函数大全1. 基本数学运算1.1 算术运算1.2 分数与小数2. 数学函数

一文详解Java Stream的sorted自定义排序

《一文详解JavaStream的sorted自定义排序》Javastream中的sorted方法是用于对流中的元素进行排序的方法,它可以接受一个comparator参数,用于指定排序规则,sorte... 目录一、sorted 操作的基础原理二、自定义排序的实现方式1. Comparator 接口的 Lam

SpringBoot开发中十大常见陷阱深度解析与避坑指南

《SpringBoot开发中十大常见陷阱深度解析与避坑指南》在SpringBoot的开发过程中,即使是经验丰富的开发者也难免会遇到各种棘手的问题,本文将针对SpringBoot开发中十大常见的“坑... 目录引言一、配置总出错?是不是同时用了.properties和.yml?二、换个位置配置就失效?搞清楚加