Java教程

【数据结构】经典八大排序(算法+动图+代码详解)

本文主要是介绍【数据结构】经典八大排序(算法+动图+代码详解),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 前言
  • 八大排序算法的实现
    • 1、插入排序(直接插入排序、希尔排序)
    • 2、选择排序(简单选择排序、堆排序)
    • 3、交换排序(冒泡排序、快速排序)
    • 4、归并排序
    • 5、基数排序
  • 总结


前言

我们在学习数据结构或者算法的过程中不可避免地需要用到排序,所谓排序就是将记录按照一定的次序排列起来。
而在数据结构中主要介绍了,八种常见排序,本次就让我们一起来学习吧。
在这里插入图片描述


提示:以下是本篇文章正文内容,下面讲解可供参考

八大排序算法的实现

1、插入排序(直接插入排序、希尔排序)

核心思想:
将待排序的序列分成有序区和无序区两部分,将无序区中一记录在有序区内排序插入,使得有序区长+1.

(1)直接插入排序:

思想:
先循环找到无序区中待插入的记录,并置于“哨兵位”,然后将有序区中最后一位逐一与其比较,若大则后移让位,若小则不动,直到确定插入位置并插入。

动图演示:
在这里插入图片描述

参考代码:

void InsertSort(RcdType &L) {	//对顺序表进行直接插入排序 
	int i,j;
	for (i=1;i<L.length;++i) {
		if (L.rcd[i].key>L.rcd[i+1].key) {	
		//循环找到无序区中待插入的记录L.rcd[i+1]
		//将其存放在“哨兵位” 
			L.rcd[0] = L.rcd[i+1];
			j = i+1;
			while (L.rcd[j-1].key>L.rcd[0].key) {
				L.rcd[j] = L.rcd[j-1];
				j--;	
			} 
			L.rcd[j] = L.rcd[0];	//插入 
		}
	} 
} 

(2)希尔排序:
希尔排序是对直接插入排序的一种改良,但也是一种不稳定的排序算法。
思想:
将待排序序列看成是一个等差数列,按一定的公差从中选出若干个子数列,并对各子数列进行直接插入排序,依次减少公差,重复以上操作,直至公差为1.
动图演示:
在这里插入图片描述

参考代码:

一趟希尔排序:

//对顺序表做一次希尔排序,增量为d(可理解为公差) 
void ShellInsert(RcdSqList &L,int d) {
	int i,j;
	for (i=1;i<L.length-d;++i) {
		if (L.rcd[i].key>L.rcd[i+d].key) {	
		//循环找到无序区中待插入的记录L.rcd[i+d]
		//将其存放在“哨兵位” 
			L.rcd[0] = L.rcd[i+d];
			j = i+d;
			while (L.rcd[j-d].key>L.rcd[0].key) {
				L.rcd[j] = L.rcd[j-d];
				j--;	
			} 
			L.rcd[j] = L.rcd[0];	//插入 
		}
	} 	 
} 

由此可见,一趟希尔排序的代码和直接插入排序的代码高度相似。其实,直接插入排序可以看成是增量为1的希尔排序。

希尔排序:

void ShellSort(RcdSqList &L,int d[],int t) {
	//按照增量序列d[0...t-1]对顺序表L做希尔排序
	int k;
	for (k=0;k<t;k++) {
		ShellInsert(L,d[k]);	//一趟增量为d[k]的插入排序 
	}
} 

2、选择排序(简单选择排序、堆排序)

**思想:**选择排序是指在无序区中选出关键字最小的记录,置于有序区的最后,直到全部记录有序。

(1)简单选择排序:

动图演示:
在这里插入图片描述

参考代码:

void select_sort(int a[],int n) {       //传入数组的要排序的元素个
	int i,j,min,t;
	for(i=0;i<n-1;i++) { 
		min=i;      //min:当前最小值下标
		for(j=i+1;j<n;j++) {       //扫描余下的部分
			if(a[min]>a[j])        //若有其它元素更小,就记录其下标
			min=j;
			if(min!=i) {       //保若最小值不在排序区首位,就换到首位
				t=a[min]; a[min]=a[i]; a[i]=t;
			}
		}
	} 
}

(2)堆排序:

核心思想:
将待排序序列构造成一个大顶堆(或者小顶堆),此时,整个序列的最大值(最小值)就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值(最小值)。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值(次大值)。如此反复执行,便能得到一个有序序列了。

大顶堆进行升序,小顶堆进行降序

动图演示:
在这里插入图片描述

3、交换排序(冒泡排序、快速排序)

两两比较(可相邻或否),逆序交换

(1)冒泡排序

思想:相邻两两比较,逆序交换

但是在这里要注意的是需要比较的趟数和次数。
n个记录需要比较n-1趟,就好比两个数只需要比较1一趟;第i趟只需要比较n-i次(每一趟之后的比较次数都会减一)
动图演示:
在这里插入图片描述
参考代码:

void bubble_sort(int a[], int n) {       //传入数组的要排序的元素个数
	int i, j, t;
	for (j=0; j<n-1; j++) {       //n个元素比较n-1轮
		for (i= 0; i<n-1-j;i++) {  //比较相邻的两个数
			if(a[i]>a[i+1]) {          //若大小顺序不符,就交换
				t=a[i];  a[i]=a[i+1]; a[i+1]=t;
				}
		}
	} 
}

(2)快速排序
动图演示:
在这里插入图片描述

参考代码:

对记录的顺序表L进行快速排序:

void QuickSort(RcdSqList &L) {	//对记录的顺序表L进行快速排序 
	QSort(L.rcd,1,L.length);
} 

对记录序列rcd[s…t]进行快速排序:

void QSort (RcdType rcd[],int s,int t) {
	//对记录序列rcd[s...t]进行快速排序
	int pivotloc ;
	if (s<t) {	//长度大于一
		 pivotloc = Partition(rcd,s,t);
		 QSort(rcd,s,pivotloc-1);z
		 QSort(rcd,pivotloc+1,t) ;
	} 
} 

划分算法:

int Partition (RcdType rcd[],int low,int high) {
	//对子序列rcd[low...high]进行一次划分,并返回枢轴应当所处的位置
	//使得在枢轴之前的关键字均不大于它的关键字,
	//枢轴之后的关键字均不小于它的关键字
	rcd[0] = rcd[low];
	while (low < high) {
		//low和high从待排序序列的两端交替地向中间移动
		while (low < high && rcd[high].key >= rcd[0].key) {
			--high;
		} 
		rcd[low] = rcd[high];	//将比枢轴关键字小的关键字移到低端 
		while (low < high && rcd[low].key <= rcd[0].key) {
			++low;
		} 
		rcd[high] = rcd[low];	//将比枢轴关键字大的关键字移到高端 
	} 
}

4、归并排序

核心思想:
将待排序序列等比例划分成几个子序列,重复以上步骤,直至子序列长度为1,逐层将各子序列有序合并组成有序序列。

2-路归并:

分别对两个子序列中标志位的元素进行比较大小,小的移到大序列中,且该子数列的标志位+1(后移一位),待其中一个子序列全部移到大序列中,而另外一个子序列还有元素,则直接复制到大序列中。 .

动图演示:

在这里插入图片描述

参考代码:

void Merge(RcdType SR[],RcdType TR[],int i,int m,int n) {
	//将相邻的有序区间SR[i..m]和SR[m+1...n]归并为有序的TR[i..n] 
	int k,j;
	for (j = m+1,k=1;i<=m && j<=n;++k) {
		//SR中的记录按关键字从小到大复制到TR中
		if (SR[i].key<=SR[j].key) {
		//此处注意,若<=改为<,则归并排序不稳定 
			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 MSort(RcdType R1[],RcdType R2[],int i,int s,int t) {
	//对R1[s..t]进行归并排序,若i%2==1,则排序后的记录存入R2[s...t],
	//否则存入R1[s..t]
	int m;
	if (s == t) {	//此时子序列长度为 1 
		if (1 == i%2) {		
		//排序过程是交替使用R1和R2的,而最后要回到R1
		//所以才会有这个要求 
			R2[s] = R1[s];
		}
	} 
	else {
		m = (s+t)/2;		//拆分 
		MSort(R1,R2,i+1,s,m);
		MSort(R1,R2,i+1,m+1,t);
		if (1 == i%2) {
			Merge(R1,R2,s,m,t);		//归并 
		}
		else {
			Merge(R2,R1,s,m,t);
		}
	}
}

对顺序表进行2-路归并排序:

void MergeSort(RcdSqList &L) {
	//对顺序表L进行2-路归并排序
	RcdType *R;
	//申请辅助空间 
	R = (RcdType*)malloc((L.lenght+1)*sizeof(RcdType)); 
	//对L.rcd[1..L.lenght]归并排序 
	MSort(L.rcd,R,0,1,L.lenght); 
	free(R); 
} 

5、基数排序

核心思想:
(在这里,为了更好的理解,我们以一个三位数的关键字为例,如:321)
“312”这个关键字可以看成是由多个关键字组合而成,个位、十位、百位。如果从最低位(个位)的关键字起,先按关键字的不同值将记录“分配”到r个子序列,再从小到大将各子序列依次首尾相接“收集”在一起,如此重复m趟(由m个关键字组合而成的关键字),最终完成整个记录的排序。

动图演示:
在这里插入图片描述
在这里插入图片描述
参考代码:

//一趟基数排序
void Radixpass(KeysRcdType rcd[],KeysRcdType rcd[],int n,int i,int count[],int pos[],int radix) {
	//对数组rcd中记录关键字的第i位计数,计算得到起始位置数组pos[]
 	//并按照pos[]数组将rcd中记录复制到数组rcd1中
	 int k,j;
	 for (k=1;k<=n;k++) {
	 	count[rcd[k].keys[i]]++;	//对各种取值计数 
	 } 
	 pos[0] = 1;
	 for (j=1;j<radix;++j) {
	 	pos[j] = count[j-1] + pos[j-1];		//求起始位置 
	 } 
	 for (k=1;k<=n;k++) {	//收集
	 	j = rad[k].keys[i]; 
	 	rcd1[pos[j]++] = rcd[k];	//复制记录,对应起始位置+1 
	 } 
} 

总结

在这里插入图片描述

这篇关于【数据结构】经典八大排序(算法+动图+代码详解)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!