C/C++教程
C语言——常见排序算法与查找算法
本文主要是介绍C语言——常见排序算法与查找算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
排序算法
冒泡排序
从要排序序列的第一个元素开始，不断比较相邻元素的值，发现逆序则交换，将值较大的元素逐渐从前向后移动。
每找到待排序序列的最大值时，就将该最大值固定在待排序序列的尾部，且每找到一个待排序序列最大值需要循环一次，n 个值则需要循环 n 次，但最后一个值无需比较，则实际需循环 n-1 次，即 i < arr.length - 1 。
void bubbleSort (int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
当然，该方法还可以进行优化。
定义一个布尔变量 flag，用来标记每轮是否进行了交换。在每轮遍历开始时，将 flag 设置为 false。若当轮没有发生交换，即此时 flag 依然为 false，说明此时数组已经按照升序排列。此时外层循环直接退出，排序结束。
void bubbleSort (int arr[]) {
boolean flag = false;
for (int i = 0; i < arr.length - 1; i++) {
flag = false;
for (int j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
flag = true; //该轮发生交换
}
}
if (!flag) {
break; //数组已有序
}
}
}
复杂度分析：
-
时间复杂度 O(n^2)
-
空间复杂度 O(1)
选择排序
选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。同样，选择排序也需要比较 n - 1轮，最后一轮无需比较。
void selectSort (int arr[]) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i; //初始化最小值索引
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
复杂度分析：
-
时间复杂度 O(n^2)
-
空间复杂度 O(1)
直接插入排序
- 数据类型定义
typedef int ElemType;
typedef struct
{
ElemType *elem; //顺序表基址，elem[0]闲置或作为监视哨
int length; //顺序表长度
} SqList;
- 算法实现
/**
* 直接插入排序
*/
void insertSort(SqList &L)
{
int i, j;
for (i = 2; i <= L.length; i++)
{
if (L.elem[i] < L.elem[i - 1])
{
//将L.elem[i]保存在空闲的0号单元，并作为哨兵
L.elem[0] = L.elem[i];
L.elem[i] = L.elem[i - 1];
//因为有哨兵L.elem[0]，所以条件 j>0 可写可不写
for (j = i - 2; L.elem[0] < L.elem[j]; j--)
{
L.elem[j + 1] = L.elem[j]; //记录后移
}
L.elem[j + 1] = L.elem[0]; //插入到正确位置
}
}
}
希尔排序
- 数据类型定义
typedef int ElemType;
typedef struct
{
ElemType *elem; //顺序表基址，elem[0]闲置或作为监视哨
int length; //顺序表长度
} SqList;
- 算法实现
/**
* 一趟希尔插入排序
*/
void shellInsert(SqList &L, int dk)
{
int i, j;
for (i = dk + 1; i <= L.length; i++)
{
if (L.elem[i] < L.elem[i - dk])
{
L.elem[0] = L.elem[i];
//条件j>0不能省，因为插入的步长为dk，L.elem[0]无法再充当哨兵
for (j = i - dk; j > 0 && L.elem[0] < L.elem[j]; j -= dk)
{
L.elem[j + dk] = L.elem[j]; //记录后移
}
L.elem[j + dk] = L.elem[0]; //插入到正确位置
}
}
}
/**
* 希尔排序
*/
void shellSort(SqList &L, int dlta[], int t)
{
int k;
//按增量dlta[0..t-1]对顺序表L进行希尔插入排序
for (k = 0; k < t; k++)
{
shellInsert(L, dlta[k]);
}
}
快速排序
- 算法实现（版本一）
/**
* 划分算法
*/
int Partition(int rcd[], int low, int high)
{
int pivot = rcd[low]; //记录枢纽关键字
while (low < high) //从 low 和 high 两端交替向中间移动
{
while (low < high && rcd[high] >= pivot)
high--;
rcd[low] = rcd[high]; //比枢纽关键字小的关键字移到低端
while (low < high && rcd[low] <= pivot)
low++;
rcd[high] = rcd[low]; //比枢纽关键字大的关键字移到高端
}
rcd[low] = pivot; //枢纽移到正确位置
return low; //返回枢纽位置
}
/**
* 快速排序（版本一）
*/
void QuickSort(int rcd[], int low, int high)
{
int pivotloc; //枢纽位序
if (low < high)
{
pivotloc = Partition(rcd, low, high);
QuickSort(rcd, low, pivotloc - 1); //对枢纽之前的子序列递归快排
QuickSort(rcd, pivotloc + 1, high); //对枢纽之后的子序列递归快排
}
}
- 算法实现（版本二）
/**
* 快速排序（版本二）
*/
void quick_sort(int rcd[], int low, int high){
if(low >= high){ //递归结束条件
return;
}
int pivot = rcd[low];
int left = low;
int right = high;
while (low < high){
while (low < high && rcd[high] >= pivot)
high--;
rcd[low] = rcd[high];
while (low < high && rcd[low] <= pivot)
low++;
rcd[high] = rcd[low];
}
rcd[low] = pivot;
quick_sort(rcd, left, low-1); //对枢纽之前的子序列递归快排
quick_sort(rcd, high+1, right); //对枢纽之后的子序列递归快排
}
归并排序
- 算法实现（版本一）
/**
* 2-路归并
*/
void Merge(int SR[], int TR[], int i, int m, int n){
//将相邻的有序序列SR[i..m]和SR[m+1..n]归并为有序的TR[i,n]
int k, j;
for (k = i, j = m + 1; i <= m && j <= n; k++){
//将SR中关键字从小到大复制到TR中
if (SR[i] <= SR[j]){
TR[k] = SR[i++];
}else{
TR[k] = SR[j++];
}
}
while (i <= m) //将剩余的SR[i..m]复制到TR
TR[k++] = SR[i++];
while(j <= n) //将剩余的SR[j..n]复制到TR
TR[k++] = SR[j++];
}
/**
* 归并排序（版本一）
*/
void MergeSort(int R1[], int R2[], int i, int low, int high){
//对R1[s..t]归并排序，若i%2==1，则排序后的记录存入R2[s..t]，否则存入R1[s..t]
int mid;
if(low == high){ //结束拆分，准备归并
if(i%2 == 1){
R2[low] = R1[low]; //为保证最后一趟归并到 R1 数组
}
}else{
mid = (low + high) / 2; //将区间[s..t]平分为[s..mid]和[mid..t]
MergeSort(R1, R2, i+1, low, mid); //对区间[s..mid]递归
MergeSort(R1, R2, i+1, mid+1, high); //对区间[mid..t]递归
if(i%2 == 1){
Merge(R1, R2, low, mid, high); //将R1[s..mid]和R1[mid+1..t]归并到R2[s..t]
}else{
Merge(R2, R1, low, mid, high); //将R2[s..mid]和R2[mid+1..t]归并到R1[s..t]
}
}
}
- 算法实现（版本二）
/**
* 归并排序（版本二）
*/
void merge_sort(int SR[], int TR[], int low, int high){
int i, j, k;
if(low >= high){ //直到有序（即只剩一个数）
return;
}
int mid = (low + high) / 2;
merge_sort(SR, TR, low, mid);
merge_sort(SR, TR, mid+1, high);
//将相邻的有序序列SR[i..m]和SR[m+1..n]归并为有序的TR[i,n]
for(k=low, i=low, j=mid+1; i<=mid && j<=high; k++){
if(SR[i] <= SR[j]){
TR[k] = SR[i++];
}else{
TR[k] = SR[j++];
}
}
while(i <= mid)
TR[k++] = SR[i++];
while(j <= high)
TR[k++] = SR[j++];
for(k=low; k<=high; k++){
SR[k] = TR[k]; //复制回待排数组
}
}
查找算法
折半查找
- 算法实现（递归版）
int BinSearch(int rcd[], int key, int low, int high){
//在有序序列rcd[low..high]中折半查找目标关键字key
int mid = (low + high) / 2;
if(low > high)
return -1; //找不到key，返回-1
if(rcd[mid] == key)
return mid; //中间关键字与目标关键字匹配，返回中间关键字下标
else if(rcd[mid] > key)
return BinSearch(rcd, key, low, mid-1); //在前半区折半查找
else
return BinSearch(rcd, key, mid+1, high); //在后半区折半查找
}
- 算法实现（非递归版）
int bin_search(int rcd[], int key, int low, int high){
//在有序序列rcd[low..high]中折半查找目标关键字key
int mid;
while(low <= high){
mid = (low + high) / 2;
if(rcd[mid] == key)
return mid;
else if(rcd[mid] > key)
high = mid - 1; //在前半区折半查找
else
low = mid + 1; //在后半区折半查找
}
return -1; //找不到key，返回-1
}
这篇关于C语言——常见排序算法与查找算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
增量更新怎么做？-icode9专业技术文章分享11-23
-
压缩包加密方案有哪些？-icode9专业技术文章分享11-23
-
用shell怎么写一个开机时自动同步远程仓库的代码？-icode9专业技术文章分享11-23
-
webman可以同步自己的仓库吗？-icode9专业技术文章分享11-23
-
在 Webman 中怎么判断是否有某命令进程正在运行？-icode9专业技术文章分享11-23
-
如何重置new Swiper?-icode9专业技术文章分享11-23
-
oss直传有什么好处？-icode9专业技术文章分享11-23
-
如何将oss直传封装成一个组件在其他页面调用时都可以使用？-icode9专业技术文章分享11-23
-
怎么使用laravel 11在代码里获取路由列表？-icode9专业技术文章分享11-23
-
怎么实现ansible playbook 备份代码中命名包含时间戳功能？-icode9专业技术文章分享11-22
-
ansible 的archive 参数是什么意思？-icode9专业技术文章分享11-22
-
ansible 中怎么只用archive 排除某个目录？-icode9专业技术文章分享11-22
-
exclude_path参数是什么作用？-icode9专业技术文章分享11-22
-
微信开放平台第三方平台什么时候调用数据预拉取和数据周期性更新接口？-icode9专业技术文章分享11-22
-
uniapp 实现聊天消息会话的列表功能怎么实现？-icode9专业技术文章分享11-22
栏目导航
