IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> C语言排序方法锦集,思路讲解。 -> 正文阅读

[数据结构与算法]C语言排序方法锦集,思路讲解。

目录

1. 前言

2. 四种基本排序

2.1 冒泡排序

2.2 插入排序

2.3 选择排序

2.4 桶排序

3. 结语


1. 前言

?本文主要介绍冒泡排序,插入排序,桶排序,选择排序4种基本方法。

话不多说,直接进入正题。

2. 四种基本排序

2.1 冒泡排序

相信冒泡排序是大家第一次接触到的简单排序方法

?

?上图所示即为冒泡排序的主要思想所在,文字表述就是:将相邻数字比较,大的数字与小的数字交换,在第一轮交换中把最大的数排到最右边,然后缩小排序范围,将第二大的数排在次右边,直到将所有数排完。

这里的所有数存入数组中,然后进行排序,使用了以便调节需要排序的数字多少。

#include <stdio.h>
#define n 10
int main()
{
    //存入n个数进数组中
	int arr[n] = { 0 };
    //输入数组中元素的具体值
	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
    //进行第k轮排序
	int k = 0;
	for (k = n - 1; k > 0; k--)//也可以k = 0;k < n;k++
	{
        //每一轮排序j次
		int j = 0;
        //flag用于判断数组是否已经有序,以减少不必要的判断
        int flag = 0;
		for (j = 0; j < k; j++)//同上改j < n - 1 - k
		{
			if (arr[j] > arr[j + 1])
			{
                //交换左大右小的数
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;
                //若该代码块执行,则该数组还未有序
                flag = 1;
			}
		}
        //如果数组已经有序,则无需进行下一轮排序
        if (flag == 0)
        	break;
	}
    //打印排序后的数组
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

?需要重视的是代码中引入了flag来优化运行速度,同样的操作在我判断素数的文章中有讲到,这次也用到了排序中,可见,每一点积累都是长远的进步!与大家共勉!

另外交换值时,我们还有另外一种方法:

这就是冒泡排序的思想以及代码实现方法,是较为初级的排序方法,但是效率会有一点低。

2.2 插入排序

插入排序是一种思想方法较为复杂的排序方法,但同时也是一种在线排序的方法。

这就是插入排序的具体思想,那么代码该如何实现呢?我将在代码中插入注释讲解。

 //插入排序
void sort(int ARR[], int len)
{
    //进来的数字用key备份

	int key = ARR[len];

    //判断该数字是不是第一个进来的数字(主函数 i==0)
    //如果是,则无需排序,从第二个数开始进行排序

	if (len > 0)
	{
        //使用循环是为了能将key与前几位的数字进行比较,使该数字插入正确位置

		while (ARR[len - 1] > key)
		{
			ARR[len] = ARR[len - 1];
			len--;
		}
	}
    //将key的值插入正确排序的位置中
	ARR[len] = key;
}
//宏来决定排序数组元素个数
#define n 5
int main()
{
    //创建一个数组,可以随机输入数字
	int arr[n] = { 0 };
	int i = 0;
	for (i = 0; i < n; i++)
	{
        //根据思路,可以知道是一个元素接一个元素来判断并插入正确位置的
        //输入一个数字后立刻进行排序
		scanf("%d", &arr[i]);
        //进入函数进行排序
		sort(arr, i);
	}
	for (i = 0; i < 5; i++)
	{
		printf("%d ",arr[i]);
	}
	return 0;
}

?以上便是插入排序的思想及代码实现方法。

2.3 选择排序

?这个代码是作者第一次自己尝试写的排序

先讲思路,我们要从数组中挑出最大的元素,将其放在数组最后一位,然后将第二大的放在倒数第二位,类似冒泡排序一样循环操作。

思想很简单,下面是代码的实现方法

先上一个复杂版(作者第一次自己写出来的版本):

//选择排序
#include <stdio.h>
void sort(int ARR[],int len)
{
    //max为后面的找出数组元素最大值做准备
	int max = 0;
    //px为后面得到最大元素的地址做准备
	int* px = 0;

    //第j轮排序 在第j轮中排序i次
	int i = 0, j = 0;
	for (j = 0; j < len; j++)
	{
        //假定第1个元素为数组中元素的最大值
		max = ARR[0];
		for (i = 0; i < len - j; i++)
		{
            //在数组中寻找比第一个元素值大的元素
			if (ARR[i] >= max)
			{
				max = ARR[i];
                //得到最大元素的地址
				px = &ARR[i];
			}
		}
        //将值最大的元素交换到最后一位(类似冒泡)
        //然后次最大的元素放在次最后一位.....
		int sum = 0;
		sum = max + ARR[len - 1 - j];
		ARR[len - 1 - j] = sum - ARR[len - 1 - j];
		*px = sum - ARR[len - 1 - j];
	}
}
#define n 5
int main()
{
    //创建一个乱序数组
	int arr[n] = { 0 };
	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
    //进入函数排序
	sort(arr,n);
    //打印排序后数组
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

?但是这并不是最简单,且有效的代码。在函数中交换数组的值也许比较麻烦,但是我们可以避开难点,使用函数来找到下标,在主函数中交换数组元素的值即可!

以下代码最精髓的地方莫过于操作下标来间接比较数组间元素的值!!

include <stdio.h>
int sort(int ARR[], int len)
{
    //max为数组值最大元素的下标
	int i = 0;
	int max = 0;
	for (i = 0; i < len; i++)
	{
        //精髓!!!!!!!
		if (ARR[i] >= ARR[max])
		{
            //更新下标继续比较
			max = i;
		}
	}
	return max;
}
#define n 5
int main()
{
    //设置一个乱序数组
	int arr[n] = { 0 };
	int i = 0;
	for (i = 0; i < n; i++)
	{
		scanf("%d", &arr[i]);
	}
    //MAX为最大元素的下标
	int MAX = 0;
	for (i = 0; i < n; i++)
	{
        int tmp = 0;
        //交换数组中的元素
		MAX = sort(arr, n - i);
		tmp = arr[MAX];
		arr[MAX] = arr[n - i - 1];
		arr[n - i - 1] = tmp;
	}
    //打印排序后数组
	for (i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

以上便是选择排序的思想及代码实现。

2.4 桶排序

作者认为这是最友好的一个排序方法了!毕竟思路简单,效率也高!

简单的说,桶排序的原理是用一个没有侧板的桶(数组)作为摸具,另一个需要排序的数组中的元素作为木板,来装填磨具,最后一个一个由短到长拆解出全部木板。

#define n 10
int main()
{
    //arr1作为摸具桶,装另一个数组的每一个元素的值
    //这里n的含义是:arr2元素的值最大值不能超过n

	int arr1[n] = { 0 };

    //arr2为需要排序的桶
    //这里n的含义是,需要排序的元素个数为n

	int arr2[n] = { 0 };

	int i = 0;
	for (i = 0; i < 10; i++)
	{
        //输入arr2的元素值,作为下标存入arr1中,使对应下标的数组元素的值加1(装木板)
		scanf("%d", &arr2[i]);
		arr1[arr2[i]]++;
	}
    //装填木板完毕
	printf("排序后:");
	for (i = 0; i < n; i++)
	{
        //arr2中的元素不包含某些值(没有某些木板),此时可以跳过进行下一个木板的拆解
		if (arr1[i] == 0)
		{
			continue;
		}
        //判断条件的意思是要把对应长度的木板全部拆下
		while (arr1[i])
		{
            //不要忘记arr1的下标就对应着arr2中元素的值哦
			printf("%d ", i);
            //拆下一个,木板就少一个,直到没有
			arr1[i]--;
		}
	}
	return 0;
}

桶排序比较简单,但是也同样难想,只有不断积累,才有可能诞生出这类新颖的排序方法!

3. 结语

这是作者总结出的几个偏向初级的排序方法介绍,希望对大家的学习有所帮助,最后不忘给作者来个3连哦,关注我,一起进步吧!

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-10-08 21:07:03  更:2022-10-08 21:11:17 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年12日历 -2024/12/28 1:51:54-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码
数据统计