C语言数据结构与算法之排序总结(一)

目录
  • 一、前言
  • 二、基本概念
    • 1.排序
    • 2.排序方法的稳定性
    • 3.内部和外部排序
  • 三、插入类排序
    • 1.直接插入排序
    • 2.折半插入排序
    • 3.希尔排序
  • 四、交换类排序
    • 1.冒泡排序
    • 2.快速排序
  • 五、总结比较

一、前言

学习目标:

排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确

理解各种排序算法的定义和特点,并能将代码灵活运用

掌握各种排序方法时间复杂度与空间复杂度

理解排序稳定和不稳定的概念                

重点和难点: 希尔、快速、堆、归并排序这几种快速排序

二、基本概念

1.排序

定义:将一个无序的数据元素任意序列,重新排列成有序的过程

代码:

typedef struct{
       int key;   //假设关键字为int型
       OtherType  other_data;
} RecordType;

2.排序方法的稳定性

0 1 2 3 4 5 6 7 8 9
5 4 10 11 22 8 10 76 1 2

解读:如上个表格这样的一个无序数组,想要将它按照从小到大排序。上图下标2和6对应的数字都是10,排序后假如红色的10任然在黑色的10前面,那这种排序方法就是稳定的,否则排序方法不稳定。

3.内部和外部排序

  • 内部排序:整个排序过程在内存中
  • 外部排序:需要排序的数过大,需要借助外部设备

三、插入类排序

插入类:在一个有序序列插入一个新的记录,使之仍然有序

1.直接插入排序

动态演示:

算法讲解: 

  1. 上面的动态图可以很好的表达直接插入的过程,只是动态图有点长
  2. 首先将0作为监视哨,用一个指针从前往后找后面的数字比前面数字小的,找到了放到0
  3. 指针开始向前移动,如果指向的值比监视哨里的值大,数字向后移
  4. 如果指向的值比监视哨里的值小,那把监视哨里的值存入这个元素之后
  5. 以此类推

代码:

void InsSort(RecordType  r[],  int length)
/* 对记录数组r做直接插入排序,length为数组中待排序记录的数目*/
{
	int i,j;
	for (i=2;  i<=length;  i++)
	{
		r[0]=r[i];      /*将待插入记录存放到监视哨r[0]中*/
		j=i-1;
		while (r[0].key< r[j].key )     /* 寻找插入位置 */
		{
			r[j+1]= r[j];
			j=j-1;
		}
		r[j+1]=r[0];	/*将待插入记录插入到已排序的序列中*/
	}
} /*  InsSort  */ 

特点: 

稳定排序

时间复杂度O(n*n), 空间复杂度O(1)

2.折半插入排序

算法讲解:

  1. 动态图没找到,只能用上面这张图片了
  2. 折半插入和折半查找思想差不多,对于一个有序的数组,将一个数字插入之后任然有序
  3. k=要插入的值  low=1, high=length , mid=(low+high)+1   mid对应的值比k大, high=low-1,否则 low=mid+1,
  4. 当low >high ,low后面就是k插入的位置

代码:

void BinSort (RecordType  r[],  int length)
/*对记录数组r进行折半插入排序,length为数组的长度*/
{
	int i,j;
    RecordType x;
    int low,high,mid;
	for (i=2; i<=length ; ++i )
	{
		x= r[i];  low=1;  high=i-1;
		while (low<=high )                  /* 确定插入位置*/
		{
			mid=(low+high) / 2;
			if ( x.key< r[mid].key) high=mid-1;
			else 	low=mid+1;
		}
		for ( j=i-1 ; j>= low; --j )   r[j+1]= r[j];    /*  记录依次向后移动 */
		r[low]=x;   /* 插入记录 */
	}
}/*BinSort*/

特点: 

稳定排序

时间复杂度O(n*n), 空间复杂度O(1)

3.希尔排序

动态演示:

算法讲解: 

  1. 对于希尔排序来说取增量 d (d一般为奇数,并且逐次递减)
  2. 上图第一次排序d等于5,将第一个作为起始点,下标+5取下一个值,一直到最后,将去到的值从小到达排序,然后将第二个作为起始点,3 4 5依次作为起始点排序
  3. 第二次是d等于3
  4. 第三次是d等于1

代码:

void  ShellInsert(RecordType r[], int length,  int  delta)
/*对记录数组r做一趟希尔插入排序,length为数组的长度,delta 为增量*/
{	int i,j;
	for(i=1+delta;i<= length; i++)     /* 1+delta为第一个子序列的第二个元素的下标 */
		if(r[i].key < r[i-delta].key)
		{
			r[0]= r[i];          /*  备份r[i]  (不做监视哨) */
			for(j=i-delta; j>0 &&r[0].key < r[j].key; j-=delta)
				r[j+delta]= r[j];
				r[j+delta]= r[0];
		}
}/*ShellInsert*/

特点:

不稳定排序方法

增量序列的d取值无除1之外的公因子,最后一个增量值必须为1

时间复杂度O(nlogn)  空间复杂度O(1)

四、交换类排序

1.冒泡排序

动态演示:

算法讲解: 

  1. 设立两个指针,i,j
  2. 每一次排序都会把最大的一个数放到后面,依次类推,假设执行2次以后,那么最后2个数就不需要比较了
  3. 执行n-1次排序,结果完成

代码:

void  BubbleSort(RecordType r[], int length )
/*对记录数组r做冒泡排序,length为数组的长度*/
{	int n,i,j; nt change; RecordType x; n=length;  change=TRUE;
		for ( i=1 ; i<= n-1 && change ;++i )
		{	change=FALSE;
				for ( j=1 ; j<= n-i ; ++j)
					if (r[j].key > r[j+1].key )
					{
						x= r[j];
						r[j]= r[j+1];
						r[j+1]= x;
						change=TRUE;
					}
		}
} /*  BubbleSort

特点:

稳定排序

时间复杂度O(n*n), 空间复杂度O(1)

2.快速排序

动态演示:

算法讲解:

  1. 快速排序讲起来稍微有点复杂,其实就是划分区域
  2. 建立两个指针low high 分别指向第一个和第二个元素,把第一个元素的值赋给x变量
  3. high向前移动,假如high指向的值小于x,则high指向的值与x互换
  4. low向后移动,假如low指向的值大于x,则low指向的值与x互换
  5. 重复3 4两步,知道high==low,第一次结束
  6. 将low指向第二个元素,把第二个元素的值赋给x变量
  7. 重复操作,知道元素有序

代码:

1.递归算法:

void QKSort(RecordType r[],int low, int high )
/*对记录数组r[low..high]用快速排序算法进行排序*/
{
	int pos;
	if(low<high)
	{
		pos=QKPass(r, low, high);  /*调用一趟快速排序,将枢轴元素为界划分两个子表*/
		QKSort(r, low, pos-1);     /*对左部子表快速排序*/
		QKSort(r, pos+1, high); /*对右部子表快速排序*/

	}
}

2.非递归算法:

int QKPass(RecordType r[],int left,int right)
/*对记录数组r 中的r[left]至r[right]部分进行一趟排序,并得到基准的位置,使得排序后的结果满足其之后(前)的记录的关键字均不小于(大于)于基准记录*/
{
	RecordType x;	int low,high;
	x= r[left];             /* 选择基准记录*/
	low=left;  	high=right;
	while ( low<high )
	{
		while (low< high && r[high].key>=x.key )   /* high从右到左找小于x.key的记录 */
			high--;
		if ( low <high ) {r[low]= r[high];  low++;}  /* 找到小于x.key的记录,则进行交换*/
		while (low<high && r[low].key<x.key  )   /* low从左到右找大于x.key的记录 */
			low++;
		if (  low<high  ){ r[high]= r[low]; high--; } /* 找到大于x.key的记录,则交换*/
	}
	r[low]=x;                     /*将基准记录保存到low=high的位置*/
	return low;                     /*返回基准记录的位置*/
} /* QKPass */ 

特点:

不稳定排序,但内部排序中公认效率最好的一种

时间复杂度O(nlogn)  空间复杂度O(logn)

五、总结比较

以上就是C语言数据结构与算法之排序总结(一)的详细内容,更多关于C语言 数据结构 排序的资料请关注我们其它相关文章!

(0)

相关推荐

  • C语言中数据结构之链式基数排序

    C语言中数据结构之链式基数排序 实现效果图: 实例代码: #include<stdio.h> #include<string.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; typedef int ElemType; #define MAX_NUM_OF_KEY 8 //关

  • C语言数据结构 快速排序实例详解

    C语言数据结构 快速排序实例详解 一.快速排序简介 快速排序采用分治的思想,第一趟先将一串数字分为两部分,第一部分的数值都比第二部分要小,然后按照这种方法,依次对两边的数据进行排序. 二.代码实现 #include <stdio.h> /* 将两个数据交换 */ void swap(int* Ina , int* Inb) { int temp = *Ina; *Ina = *Inb; *Inb = temp; } /* 进行一趟的快速排序,把一个序列分为两个部分 */ int getPart

  • C语言数据结构 链表与归并排序实例详解

    C语言数据结构 链表与归并排序实例详解 归并排序适合于对链表进行原址排序,即只改变指针的连接方式,不交换链表结点的内容. 归并排序的基本思想是分治法:先把一个链表分割成只有一个节点的链表,然后按照一定顺序.自底向上合并相邻的两个链表. 只要保证各种大小的子链表是有序的,那么最后返回的链表就一定是有序的. 归并排序分为分割和合并两个子过程.分割是用递归的方法,把链表对半分割成两个子链表:合并是在递归返回(回朔)的时候,把两个有序链表合并成一个有序链表. (注意:只有一个节点的链表一定是有序的) 这

  • C语言 数据结构堆排序顺序存储(升序)

    堆排序顺序存储(升序) 一: 完全二叉树的概念:前h-1层为满二叉树,最后一层连续缺失右结点! 二:首先堆是一棵全完二叉树: a:构建一个堆分为两步:⑴创建一棵完全二叉树      ⑵调整为一个堆 (标注:大根堆为升序,小根堆为降序) b:算法描述:①创建一棵完全二叉树 ②while(有双亲){ A:调整为大根堆: B:交换根和叶子结点: C:砍掉叶子结点: } c:时间复杂度为 O(nlogn)  ,空间复杂度为 O(1), 是不稳定排序! 代码实现: /*堆排序思想:[完全二叉树的定义:前

  • C语言数据结构之堆排序源代码

    本文实例为大家分享了C语言堆排序源代码,供大家参考,具体内容如下 1. 堆排序 堆排序的定义及思想可以参考百度百科: 用一句概括,堆排序就是一种改进的选择排序,改进的地方在于,每次做选择的时候,不单单把最大的数字选择出来,而且把排序过程中的一些操作进行了记录,这样在后续排序中可以利用,并且有分组的思想在里面,从而提高了排序效率,其效率为O(n*logn). 2. 源代码 堆排序中有两个核心的操作,一个是创建大顶堆(或者小顶堆,这里用的是大顶堆),再一个就是对堆进行调整.这里需要注意的是,并没有真

  • C语言数据结构与算法之排序总结(二)

    目录 一.前言 二.选择类排序 1.简单选择排序 2.树形选择排序 3.堆选择排序 三.归并排序 四.分配类排序 1.多关键字排序 2.链式基数排序 五.总结归纳 一.前言 之前的排序总结(一)对插入类和交换类排序作了比较详细的总结,对于直接插入.希尔排序.冒泡排序.快速排序要求熟练掌握 这篇排序全面总结(二)主要介绍选择类排序中的简单.树形和堆排序,归并排序.分配类排序的基数排序 二.选择类排序 选择类:每次从待排序的无序序列中,选择一个最大或最小的数字,放到前面,数据元素为空时排序结束 1.

  • C语言数据结构与算法之排序总结(一)

    目录 一.前言 二.基本概念 1.排序 2.排序方法的稳定性 3.内部和外部排序 三.插入类排序 1.直接插入排序 2.折半插入排序 3.希尔排序 四.交换类排序 1.冒泡排序 2.快速排序 五.总结比较 一.前言 学习目标: 排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确 理解各种排序算法的定义和特点,并能将代码灵活运用 掌握各种排序方法时间复杂度与空间复杂度 理解排序稳定和不稳定的概念                 重点和难点: 希尔.快速.堆.归并排序这几种快

  • java 数据结构基本算法希尔排序

    C语言数据结构基本算法希尔排序 前言: 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序, 然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序.当增量减到1时,进行直接插入排序后,排序完成. 实现代码: public class ShellSort { /** * 原理:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的 * 下标相差d.对每组

  • 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语言数据结构与算法之链表(一)

    目录 引言 链表的相关思考 链表结点结构 建立链表 实现插入操作 完整代码 引言 在存储一大波数的时候,我们通常使用的是数组,但是数组有时候又会显得不够灵活,比如下面这个例子: 有一串已经排序好的数 2,3,5,8,9 ,10 如果我们想要往数组中插入6 这个元素,需要把 8 以后的元素全部往后挪一位 这样操作显然很耗费时间,如果使用链表的话则会快很多.那么什么是链表呢?请看下图: 此时如果需要在8前面加入一个6,那么只需要向下图一样更改一下就可以了,而不用向像最开始那样把每个数向后挪. 链表的

  • C语言数据结构与算法之图的遍历(二)

    目录 前言  广度优先搜索过程 主要思想  代码实现   前言  在上一章的内容中我们使用了深度优先搜索来进行遍历,这一章我们选择使用广度优先搜索来完成这个图的遍历 --> 结果如下: 广度优先搜索过程 使用广度优先搜索来遍历这个图的过程如下. 首先以一个未被访问过的顶点作为起始顶点,比如以1号点作为起始顶点. 将1号点放到队列中,然后将与1号点相邻的未访问过的顶点 即 2,3,5号顶点依次放入队列中,如下图: 接下来将2号顶点相邻的未访问过的顶点4号放入到队列中.到此所有的顶点都访问过了,遍历

  • C语言数据结构与算法之图的遍历

    目录 引入  深度优先搜索 代码实现  完整代码   引入  在数据结构中常见的有深度优先搜索和广度优先搜索.为什么叫深度和广度呢?其实是针对图的遍历而言的,请看下面这个图: 图是由一些小圆点(称为顶点) 和 连接这些点的直线 (称为边)组成的. 例如上图就是由5个顶点(编号为 1,2,3,4,5) 和5条边(1-2,1-3,1-4,2-4)组成. 现在我们从1号顶点开始遍历这个图,遍历就是把图的每一个顶点都访问一次.使用深度优先搜索将会得到如下的结果. 图中每个顶点旁边的数表示这个顶点是第几个

  • C语言数据结构与算法之链表(二)

    目录 引入 模拟链表介绍 插入代码实现 代码实现   引入 在上一节的学习中我们介绍了C语言如何实现链表,但是,在这一章,我们将抛开令人头秃的指针和结构体,我们将另外使用一种数组来实现的方式,叫做模拟链表.让我们一起来看看. 模拟链表介绍 链表中的每一个结点都只有两个部分. 我们可以使用一个数组date来储存每序列中的每一个数.那每一个数右边的数是谁,这一点该如何解决呢?在上一章的内容中我们是使用指针来解决的,这里我们只需再用一个数组right来存放序列中每一个数右边的数是谁就可以了.具体要怎么

  • C语言数据结构与算法之单链表

    目录 基本概念 读取数据元素 获取第i个结点的数据元素 插入数据元素  初始化链表 打印链表 顺序表查空 顺序表的删除  删除第i个结点及其数据元素 情况1:当删除的是第一个元素 情况2:除第一个结点外 完整代码 删除单链表整表 单链表VS顺序表 基本概念 链表的每一个结点中只包含一个指针域 优点 : 储存空间利用高效 举例来说: typedef struct student{ int id; //学生编号 char* name; //学生名称 //指向下一结点的指针 struct Studen

  • C语言 数据结构与算法之字符串详解

    目录 串的定义 串的比较 串的抽象数据类型 串的初始化 相关定义初始化 定长类初始化 串的堆式顺序存储结构(Heap) 初始化堆字符串 赋值操作 比较两个堆字符串的大小 串的定义 零个或多个字符组成的有限序列 串的比较 串的比较实际上是在比较串中字符的编码 存在某个k < min(n,m),使得ai = bi (i = 1,2,3,4..k) 如果 ak < bk  -->  那么srt1 < srt2 (反之也成立) 除去相等的字符,在第一个不相等的字符位置以Ascii码进行比较

随机推荐