C语言超详细梳理排序算法的使用

目录
  • 排序的概念及其运用
    • 排序的概念
    • 排序运用
  • 插入排序
    • 直接插入排序
    • 希尔排序
  • 选择排序
    • 直接选择排序
    • 堆排序
  • 交换排序之冒泡排序
  • 总结

排序的概念及其运用

排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次
序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排
序算法是稳定的；否则称为不稳定的。 内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

排序运用

高校排名：

接下来，我会一一介绍几种常见的排序算法

插入排序

直接插入排序

直接插入排序是一种简单的插入排序法

基本思想： 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列

代码的实现

//直接插入排序
void InsertSort(int* a, int n)
{
	assert(a);//传入数组不为空指针
	int i;
	for (i = 0; i < n - 1; i++)

	{
		int end = i;
		int x = a[end + 1];

		while (end >= 0)
		{
			//升序
			if (a[end] >x)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = x;
	}
}

希尔排序

解析

  • 希尔排序在直接排序之前，进行预排列，将某些极端数据更快的排列到数列前面，构成一个接近排列好的序列，最后再进行一次直接插入排序
  • 预排列的原理也是插入排列，只不过这里的将数组分成了gap组，分别对每一个小组进行插入排序
// 希尔排序
void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end-=gap;
				}
				else
					break;
			}
			a[end + gap] = x;
		}
	}
}

当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比

选择排序

直接选择排序

解析

每一次遍历待排序的数据元素从中选出最小（或最大）的一个元素，存放在序列的起始（或者末尾）位置，直到全部待排序的数据元素排完

代码的实现

// 选择排序
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;//记录下标
	while (begin < end)
	{
		int mini = begin;
		for (int i = begin; i <= end; i++)
		{
			//遍历找到最小数据并记录下标
			if (a[i] < a[mini])
				mini = i;
		}
		Swap(&a[begin], &a[mini]);//交换
		begin++;//缩小范围
	}
}

总结

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：不稳定

不推荐使用

堆排序

堆排序是指利用堆（数据结构）进行选择数据的一种排序算法

基础思想：

  • 原则：

先将原数组建成堆，需要注意的是排升序要建大堆，排降序建小堆
注：以大堆为例

  • 建堆：

一个根节点与子节点数据如果不符合大堆结构，那么则对根节点数据进行向下调整，而向下调整的前提是左右子树也符合大堆结构,所以从堆尾数据的根节点位置开始向下调整建大堆

  • 排序：

大堆堆顶数据一定是待排数据中最大的，将堆顶数据与堆尾数据交换,交换后将除堆尾数据看成新堆，对现堆顶数据进行向下调整成大堆,以此循环直至排列完毕

  • 向下调整：

找到子节点中的较大数据节点比较，如果父节点数据比大子节点小则交换，直到不符合则停止向下交换，此时再次构成了一个大堆结构.

代码的实现

void Adjustdown(int* a, int n,int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		//找到数据大的子结点
		if (child + 1 < n && a[child + 1] > a[child])
		{
			child++;
		}
		//父节点数据小于子节点就交换
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
			//更新下标
			parent = child;
			child = parent * 2 + 1;
		}
		else//否则向下调整完毕
			break;
	}
}

// 堆排序(升序)建大堆
void HeapSort(int* a, int n)
{
	int i;
	//建大堆
	for (i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		Adjustdown(a, n, i);
	}
	//交换调整
	for (i = n - 1; i >= 0; i--)
	{
		Swap(&a[0], &a[i]);//与当前堆尾数据交换
		Adjustdown(a, i, 0);//对交换后堆顶数据进行向下调整
	}
}

总结：

堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定

交换排序之冒泡排序

冒泡排序

每次遍历数组，对相邻数据进行比较，不符合排序要求则交换

代码的实现

// 冒泡排序
void BubbleSort(int* a, int n)
{
	int i, j;
	for (i = 0; i < n - 1; i++)//趟数
	{
		for (j = 0; j < n - 1 - i; j++)//比较次数
		{
			if (a[j] > a[j + 1])//满足条件
				Swap(&a[j], &a[j + 1]);//交换
		}
	}
}

总结

排序的第一篇就讲到这里了，下一篇还会讲快速排序和归并排序，希望大家多多支持！！

到此这篇关于C语言超详细梳理排序算法的使用的文章就介绍到这了,更多相关C语言 排序算法内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C语言数据结构经典10大排序算法刨析

    C语言数据结构经典10大排序算法刨析

    1.冒泡排序 // 冒泡排序 #include <stdlib.h> #include <stdio.h> // 采用两层循环实现的方法. // 参数arr是待排序数组的首地址,len是数组元素的个数. void bubblesort1(int *arr,unsigned int len) { if (len<2) return; // 数组小于2个元素不需要排序. int ii; // 排序的趟数的计数器. int jj; // 每趟排序的元素位置计数器. int itmp

  • C语言超详细讲解排序算法上篇

    C语言超详细讲解排序算法上篇

    目录 1.直接插入排序 2.希尔排序(缩小增量排序) 3.直接选择排序 4.堆排序 进入正式内容之前,我们先了解下初阶常见的排序分类 :我们今天讲前四个! 1.直接插入排序 基本思想:当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排 序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移! 直接插入排序的特性总结: 1. 元素集

  • C语言直接插入排序算法介绍

    C语言直接插入排序算法介绍

    目录 前言 一.什么是直接插入排序 二.代码讲解 总结 前言 直接 插入排序 (Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表.. 废话不多说先看看代码 #define _CRT_SECURE_NO_WARNINGS 1 //直接插入排序法 #include <stdio.h> void Compare(int arr[], int len) { int i = 0; for (i =

  • C语言中冒泡排序算法详解

    C语言中冒泡排序算法详解

    目录 一.算法描述 二.算法分析 三.完整代码 总结 一.算法描述 比较相邻两个元素,如果第一个比第二个大则交换两个值.遍历所有的元素,每一次都会将未排序序列中最大的元素放在后面.假设数组有 n 个元素,那么需要遍历 n - 1 次,因为剩下的一个元素一定是最小的,无需再遍历一次.因此需要两层循环,第一层是遍历次数,第二层是遍历未排序数组. 动图如下: 黄色部分表示已排好序的数组,蓝色部分表示未排序数组 核心代码如下: /** * @brief 冒泡排序 * * @param arr 待排序的数

  • C语言冒泡排序算法代码详解

    C语言冒泡排序算法代码详解

    今天我们来用C语言实现一下冒泡排序 首先我们来了解一下什么叫做冒泡排序,冒泡顾名思义把质量轻的气体(如二氧化碳一样)浮到水面上(如可乐中的二氧化碳),因此冒泡排序的原理就是N个元素在一个周期中,微观上依次进行两两元素的比较,小的元素就被放在前面,大的元素放在后面,以此来进行N-1个周期,来完成冒泡排序. 上文中的一个周期,即外循环,依次进行比较,即内循环. 文字看着很迷糊?没事儿,上图 如图所示,两两元素依次进行比较,小的元素往前移动,大的元素往后移动,直至元素顺序是升序的形式,即移动了 元素-

  • C语言库函数qsort及bsearch快速排序算法使用解析

    C语言库函数qsort及bsearch快速排序算法使用解析

    目录 qsort 含义 实现 格局打开 bsearch qsort qsrot 就是C语言库函数中的快速排序函数,对数组,结构体都可以实现快速排序, 他在头文件<stdlib.h>中使用,声明格式为: void qsort(void* base, size_t nums, size_t size, int (*compare)(const void *, const void*)) 这么烦人一长串的参数各是什么意思呢,base 是指向要排序的数组的第一个元素的指针.nums是由 base 指向

  • C语言实现单链表的快速排序算法

    C语言实现单链表的快速排序算法

    目录 背景 设计思路 算法主要步骤 快速排序算法实现 整个程序源代码 测试案例 总结 背景 传统QuickSort算法最大不足之处在于,由于其基于可索引存储结构设计(一般为数组或索引表),因而无法用于链式存储结构,而链式存储结构的实际应用非常广泛,例如动态存储管理.动态优先级调度等等,故本文针对于单向链表,以QuickSort的分治策略为基础,提出一种可用于单向链表的快速排序算法. 设计思路 将单向链表的首节点作为枢轴节点,然后从单向链表首部的第二个节点开始,逐一遍历所有后续节点,并将这些已遍历

  • C语言直接插入排序算法

    目录 1.算法模板 2.算法介绍 3.实例 总结 1.算法模板 void InsertSort(SqList *L) { int j; for (int i = 2; i <= L->length; i ++ ) { if (L->arr[i] < L->arr[i-1]) { L->arr[0] = L->arr[i]; // 设置哨兵 for (j = i - 1; L->arr[j] > L->arr[0]; j -- ) L->ar

  • C语言之直接插入排序算法的方法

    C语言之直接插入排序算法的方法

    目录 一.什么是直接插入排序 二.代码讲解 总结 直接 插入排序 (Straight Insertion Sort)是一种最简单的排序方法,其基本操作是将一条记录插入到已排好的有序表中,从而得到一个新的.记录数量增1的有序表.. 废话不多说先看看代码 #define _CRT_SECURE_NO_WARNINGS 1 //直接插入排序法 #include <stdio.h> void Compare(int arr[], int len) { int i = 0; for (i = 0; i

  • C语言超详细梳理排序算法的使用

    C语言超详细梳理排序算法的使用

    目录 排序的概念及其运用 排序的概念 排序运用 插入排序 直接插入排序 希尔排序 选择排序 直接选择排序 堆排序 交换排序之冒泡排序 总结 排序的概念及其运用 排序的概念 排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作. 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次 序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排 序算法

  • C语言超详细讲解排序算法下篇

    C语言超详细讲解排序算法下篇

    上期学习完了前四个排序，这期我们来学习剩下的三个排序：

  • C语言 超详细梳理总结动态内存管理

    C语言 超详细梳理总结动态内存管理

    目录 一.为什么存在动态内存分配 二.动态内存函数的介绍 1.malloc和free 2.calloc 3.realloc 三.常见的动态内存错误 1.对NULL指针的解引用操作 2.对动态开辟空间的越界访问 3.对非动态开辟的空间使用free释放 4.使用free释放一块动态开辟空间的一部分 5.对同一块开辟的空间多次释放 6.动态内存开辟忘记释放(内存泄漏) 四.几个经典的笔试题 一.为什么存在动态内存分配 我们已经掌握的内存开辟方式有: int a = 10://在栈空间开辟4个字节的连续

  • C语言 超详细梳理总结动态内存管理

    C语言 超详细梳理总结动态内存管理

    目录 一.为什么存在动态内存分配 二.动态内存函数的介绍 1.malloc和free 2.calloc 3.realloc 三.常见的动态内存错误 1.对NULL指针的解引用操作 2.对动态开辟空间的越界访问 3.对非动态开辟的空间使用free释放 4.使用free释放一块动态开辟空间的一部分 5.对同一块开辟的空间多次释放 6.动态内存开辟忘记释放(内存泄漏) 四.几个经典的笔试题 1. 一.为什么存在动态内存分配 我们已经掌握的内存开辟方式有: int a = 10://在栈空间开辟4个字节

  • C语言自定义类型超详细梳理之结构体 枚举 联合体

    C语言自定义类型超详细梳理之结构体 枚举 联合体

    目录 一.什么是结构体 1.结构体实现 2.匿名结构体类型 3.结构体自引用 4.结构体的内存对齐 5.结构体位段  二.什么是枚举 1.枚举类型的定义 2.枚举的优点 三.联合(共用体) 1.什么是联合(共用体) 2.联合(共用体)的定义 3.联合(共用体)的初始化 总结 一.什么是结构体 结构是一些值的集合,这些值称为成员变量.结构的每个成员可以是不同类型的变量. //结构体声明 struct tag //struct:结构体关键字,tag:标签名,合起来是结构体类型(类型名) { memb

  • C语言 超详细讲解算法的时间复杂度和空间复杂度

    C语言 超详细讲解算法的时间复杂度和空间复杂度

    目录 1.前言 1.1 什么是数据结构? 1.2 什么是算法? 2.算法效率 2.1 如何衡量一个算法的好坏 2.2 算法的复杂度 2.3 复杂度在校招中的考察 3.时间复杂度 3.1 时间复杂度的概念 3.2 大O的渐进表示法 3.3 常见时间复杂度计算举例 4.空间复杂度 5. 常见复杂度对比 1.前言 1.1 什么是数据结构? 数据结构(Data Structure)是计算机存储.组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合. 1.2 什么是算法? 算法(Algorit

  • C语言 语义陷阱超详细梳理总结

    目录 1 指针与数组 2 非数组的指针 3 作为参数的数组声明 4 空指针并非空字符串 5 边界计算与不对称边界 6 求值顺序 7 整数溢出 8 为函数提供返回值 1 指针与数组 C语言中只有一维数组.数组中的元素可以是任意类型的对象,这也是多维数组构建的理论基础所在 对于一个数组,我们只能做两件事:确定该数组的大小以及获得该数组下标为0的元素的指针.任何一个数组下标运算都等同于一个对应的指针运算. 数组名代表首元素的地址,无法对其进行++或者–操作,换句话说,我们无法改变数组名(表示的值),因

  • C语言超详细讲解数据结构中双向带头循环链表

    C语言超详细讲解数据结构中双向带头循环链表

    目录 一.概念 二.必备工作 2.1.创建双向链表结构 2.2.初始化链表 2.3.动态申请节点 2.4.打印链表 2.5.销毁链表 三.主要功能 3.1.在pos节点前插入数据 尾插 头插 3.2.删除pos处节点数据 尾删 头删 3.3.查找数据 四.总代码 List.h 文件 List.c 文件 Test.c 文件 五.拓展 一.概念 前文我们已经学习了单向链表,并通过oj题目深入了解了带头节点的链表以及带环链表,来画张图总体回顾下: 在我们学习的链表中,其实总共有8种,都是单双向和带不带

  • python 列表常用方法超详细梳理总结

    目录 列表是什么? 列表常用方法 1.append() 2.clear() 3.copy() 4.count() 5.extend() 6.index() 7.insert() 8.reverse() 9.remove() 10.pop() 11.sort() 列表是什么? 列表由一系列特定顺序排列的元素组成,你可以创建包含字母表中的所有字母.数字0~9.所有家庭成员姓名的列表等等,也可以将任何东西放入列表中,其中元素之间可以没有任何关系,鉴于列表通常包含多个元素,给列表指定一个表示复数的名称(

随机推荐