【数据结构】八大排序(一)

这篇具有很好参考价值的文章主要介绍了【数据结构】八大排序(一)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

前言:

直接插入排序

直接插入排序代码实现

直接插入排序特性总结

希尔排序

希尔排序代码实现

希尔排序特性总结

直接选择排序

直接选择排序代码实现

直接选择排序特性总结

堆排序

堆的向下调整算法

建堆

堆排序代码实现

堆排序特性总结


前言:

排序即使得一串记录,按照其中某个或某些关键字的大小,递增或递减的排列起来的操作;

排序分为内部排序外部排序稳定排序非稳定排序

内部排序数据元素全部放在内存中的排序;

外部排序:数据元素太多不能同时存储于内存中,根据排序过程的要求不能在内外存之间移动数据的排序;

稳定性:假定在待排序的序列中,如果元素a位于元素b前面,且a=b,经过某种排序方法进行排序之后,元素a依然位于元素b前面,那么这种排序方法就是稳定的,否则就是不稳定的;

衡量一个排序方法的好坏可以根据时间复杂度与空间复杂度,稳定性等综合考虑

常见的排序算法:

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

本篇主要详细介绍前四种排序,均以升序为例 ;

直接插入排序

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

直接插入排序的基本思想:

对于一个长度为n的数组a,当插入第 i (i>=1)个元素时,前面的a[0],a[1],......,a[i-1]已经有序,此时只需将a[i]元素与a[i-1],a[i-2],.....的元素进行比较,找到插入位置先将原来位置上的元素依次向后移动,然后在插入位置插入元素a[i];

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

具体步骤如下

  1. 将待排序的序列分为有序区和无序区,初始时有序区只有一个元素,即序列的第一个元素,无序区包括除第一个元素外的所有元素;
  2. 从无序区中取出第一个元素,将其插入到有序区中的适当位置,使之成为新的有序区;
  3. 重复步骤2,直到无序区中的所有元素都插入到有序区中;
  • 单个数据必然有序,所以将元素3划分为有序区,其他元素均位于无序区,假设有序区最后一个元素下标为end,为防止移动过程中插入元素被覆盖,用tmp保存插入元素的数值;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

  • 寻找插入位置,将tmp与数组有序区尾元素a[end]进行比较,若a[end]>tmp,先将有序区尾元素向后移动一位,然后通过控制end即end每次自减1,向左查找下一位,按此循环,直至a[end]<tmp出现或者end = -1;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

  • 此时单趟排序已完成,end继续回到有序区的尾元素的位置,进行下一趟排序,若a[end]<tmp,直接插入到end的下一位置即a[end+1]=tmp;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法 【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法 【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

.......

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

直接插入排序代码实现

void InsertSort(int* a, int n)
{
	//先写单趟,再写整体;
	for (int i = 0; i <n-1 ; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				//向后挪动一位
				a[end + 1] = a[end];
                end--;
			}
			else
			{
			//考虑极端情况,当插入的数值小于有序区数组每个元素,不断向前挪动过程中,直至end=-1;
			//出现插入的数值大于a[end];
				break;
			}
		}
		a[end + 1] = tmp;
	 }
} 

直接插入排序特性总结

1.时间复杂度

最好情况就是全部有序,此时只需遍历一次,最好的时间复杂度为O(n)
最坏情况全部逆序,内层每次遍历已排序部分,最坏时间复杂度为O(n^2)

综上,因此直接插入排序的平均时间复杂度为O(n^2)

2. 空间复杂度

额外开辟的空间为常数个,所以空间复杂度为O(1);

3.算法稳定性

稳定性指相同元素的前后顺序是否改变,当插入元素小于a[end]时,插入到比它大的数前面,所以直接插入排序是稳定的;

希尔排序

希尔排序的基本思想

希尔排序是一种改进的插入排序算法,其基本思想是将待排序的序列按照一定的间隔(gap)分成若干个子序列,通过插入排序对大间隔的子序列进行排序,使得整个序列基本有序,然后逐步缩小间隔,重复上述操作,直到间隔gap为1,最后对整个序列进行直接插入排序;每次排序让数组接近有序的过程叫做预排序,最后一次排序为直接插入排序

1.  取间隔gap=3对下述序列进行分组,该序列被分成3组,每组之间都是以3的等差数列;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

2. 对每一组进行插入排序,得到如下数组

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

3.缩小间隔,取间隔gap=2对数组进行分组,数组被分成2份,每组之间都是2的等差数列;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

4. 对每一组进行插入排序,得到如下数组

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

5.缩小间隔,取间隔gap=1对数组进行分组,数组相当于没有分组,进行插入排序,当gap=1时为直接插入排序;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

  • 如何选择希尔增量gap?

最初Shell提出的增量是 gap = [n / 2],每一次排序完让增量减少一半gap =[ gap / 2],直到gap = 1时排序变成了直接插入排序;后来Knuth提出的gap = [gap / 3] + 1,每次排序让增量成为原来的三分之一,加一是防止gap <= 3时gap = [gap / 3] = 0的发生,导致希尔增量最后不为1,无法完成插入排序;

上述无论哪一种主张都没有得到证明,本文代码实现部分采取gap=[n/2],gap=[gap/2];

希尔排序代码实现

  • 长度为n的数组间距为gap分为一组,共计gap组,定义遍历变量i,首先遍历第一组数据,i从0开始遍历,i每次移动gap步,由于数组尾元素下标为n-1,则i+gap=n-1,为防止数组越界访问,i最后访问位置为 n-1-gap ;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

......

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

第一组排序代码如下:

    for (int i = 0; i < n - gap; i += gap)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
  • 第一组排序完成,外面套一层循环,遍历其余组,便可完成第一趟排序,定义循环变量j,j从0开始,每次自增1,一共有gap组,j小于gap即可排序其他组;
	for (int j = 0; j < gap; j++)
	{
		for (int i = j; i < n - gap; i += gap)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
	}
  • 然后缩小增量 gap = gap /2 直到gap = 1,继续插入排序,直到排序完成;
void ShellSort(int* arr, int n)
{
	int gap = n;
	//预排序:分组排序,间距为gap分为一组,共计gap组;
	//最后进行直接插入排序,即gap==1;
	while (gap > 1)
	{
		gap = gap / 2;
		//其次排序其余gap组,一次预排序完成,会进行多次预排序;
		for (int j = 0; j < gap; j++)
		{
			//首先排序以第一个元素为起点,间距为gap的第一组;相当于整个数组排序;
			for (int i = j; i < n - gap; i += gap)
			{
				//保证[0,end]有序,每个元素间隔为gap,控制[0,end+gap]有序;
				int end = i;
				int tmp = arr[end + gap];
				while (end >= 0)
				{
					if (tmp < arr[end])
					{
						arr[end + gap] = arr[end];
						end = end - gap;
					}
					//else会出现俩种情况;
					//第一种为第一个元素以后且间距为gap的某个位置插入;
					//第二种会不断满足tmp<arr[end],直至end=-gap;
					else
					{
						break;
					}
					//end=-gap的位置,直接将arr[end+gap]=tmp;
					arr[end + gap] = tmp;
				}
			}
		}
	}
}

希尔排序特性总结

1.时间复杂度

希尔排序的时间复杂度取决于增量序列的选择,由于gap取值有多种方法,导致希尔排序的时间复杂度并不固定,一般来说,希尔排序的平均时间复杂度界于 O(n)到 O(n^2)之间, 最好的时间复杂度为 O(n^1.3)

2. 空间复杂度

希尔排序的空间复杂度为O(1),因为在希尔排序时是对原数组进行直接排序,并没有创建其他新的数组;

3.算法稳定性

希尔排序是一种非稳定的排序算法;希尔排序的精髓在于按照某个增量来划分子序列,实现跳跃式移动来提高排序效率,而也正是这种跳跃性带来了不稳定性。如果不同子序列中有相等的数,但它们不在同一子序列中,可能会因为子序列内部排序而改变原有的顺序

直接选择排序

直接选择排序的基本思想:

每一次从待排序的数据元素中选出最小(或最大)的一个元素,通过交换存放在序列的起始位置(或最后一个位置),直到全部待排序的数据元素排完;

具体来说,就是在待排序序列中,首先找到最小的元素和最大的元素,然后将最小的元素与序列的第一个元素交换位置,最大的元素与序列的最后一个元素交换位置,接着在剩下的元素中找到最小的元素与最大的元素,将最小元素与序列的第二个元素交换位置,最大元素与序列的倒数第二个元素交换位置,以此类推,直到序列中只剩一个元素为止

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

具体步骤如下:

  1.   遍历整个序列,找到最小的元素与最大的元素;
  2.   将最小的元素与序列的第一个元素交换位置,最大的元素与序列尾元素交换位置;
  3.   序列遍历范围从第二个元素开始到倒数第二个元素,遍历序列,找到剩余元素中的最   小元素与最大元素;
  4.   将最小的元素与序列的第二个元素交换位置,最大的元素与序列倒数第二个元素交换位置;
  5.   重复上述步骤,直到整个列表都被排序;

 1. 定义变量begin,end,确定遍历范围[begin,end] ;定义maxi,mini记录遍历范围内的最大值下标  和最小值下标,最初maxi ,mini 指向遍历范围内的首元素,当在遍历范围内查找到最大值,最小值时更新maxi,mini ;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

2. 遍历结束后查找到最大值,最小值,此时将最小的元素与遍历范围内的第一个元素交换位置,最大的元素与遍历范围内的尾元素交换位置;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

3.交换完成后,begin自增1,end自减1,确定新的遍历范围,同时maxi ,mini 指向遍历范围内的首元素,当在遍历范围内查找到最大值,最小值时更新maxi,mini ;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

4. 交换时先将遍历范围内的最小值与遍历范围的首元素交换,其次将遍历范围内的最大值与遍历范围内的尾元素交换;

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

当出现上述情况即出现 最大的位置恰好位于begin位置,说明mini是和最大的交换位置,这个时候max的位置就发生了变换, maxi变到了mini的位置,需要 更新max的位置,否则易导致错误,正确做法如下图所示
 

 【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法......

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

直接选择排序代码实现

//交换
void swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = tmp;
}
//选择排序
void SelectSort(int* arr, int n)
{
	int begin = 0;
	int end = n - 1;
	while (begin < end)
	{
		//单趟排序,将[begin,end]范围内最大与最小的数据调整于左右;
		int maxi = begin;//最大元素的下标,假设最大元素在最左边;
		int mini = begin;//最小元素的下标,假设最小元素在最左边;
		for (int i = begin+1; i <=end; i++)
		{
			if (arr[i]>arr[maxi])
			{
				maxi = i;
			}
			if (arr[i]<arr[mini])
			{
				mini = i;
			}
		}
		swap(&arr[begin], &arr[mini]);
        //如果最大元素的位置位于begin位置,说明mini和最大的交换位置;
        //maxi的位置变化到mini的位置,要更新maxi;
		if (maxi == begin)
		{
			maxi = mini;
		}
		swap(&arr[end], &arr[maxi]);
		end--;
		begin++;
	}
}

直接选择排序特性总结

1.时间复杂度

数据的比较次数为(n-1)+(n-2)+(n-3)+......1 = n*(n-1)/2,数据的交换次数为n-1,所以 时间复杂度为O(n^2)

2. 空间复杂度

选择排序的空间复杂度为O(1),因为在选择排序时是对原数组进行直接排序,并没有创建其他新的数组;

3.算法稳定性

选择排序是一种非稳定的排序算法,具体参见上图红五与白五排序前后的位置;

堆排序

大根堆:任意父节点的数值大于等于孩子节点的数值(a[i] >= a[2i+1] && a[i] >= a[2i+2]);

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

对堆中的结点按层进行编号,映射到数组便可得其存储结构

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

小根堆:任意父节点的数值小于等于孩子节点的数值(a[i] <= a[2i+1] && a[i] <= a[2i+2]);

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

对堆中的结点按层进行编号,映射到数组便可得其存储结构

【数据结构】八大排序(一),数据结构,数据结构,排序算法,算法

结论: 大堆堆顶数据的数值最大; 小堆堆顶数据数值最小

堆排序是利用大堆或者小堆堆顶数据最大或最小的特性来进行排序的,所以,我们排序的对象必须是大堆或者小堆,但给定的数据不一定是大堆或者小堆,所以必须先建堆;

堆的向下调整算法

建堆的核心为堆的向下调整算法,堆的向下调整算法的基本思想

从根结点开始,利用假设法寻找同一高度处值最小的孩子,根据其左右子树为小堆还是大堆,按照小堆或大堆的原则将其交换,若为小堆,父节点处的数值大于孩子结点出的数值,则交换彼此位置;若为大堆,父节点处的数值小于孩子结点出的数值,则交换彼此位置;直至叶节点为止或出现满足其逻辑上不满足大小堆的数值为止;

//堆的向下调整算法(建大堆)
void AdjustDown(int* nums, int n, int parent)
{
	//假设法求同一深度左右孩子最小的一个,假设左孩子为最小
	int child = parent * 2 + 1;
	while (child<n)
	{
		if (child + 1 < n && nums[child] < nums[child + 1])
		{
			child++;
		}
		//无论左右孩子,child为最大,调整为大堆;
		if (nums[child] > nums[parent])
		{
			swap(&nums[child], &nums[parent]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

建堆

由于向下调整算法的使用前提是左右子树必须是大堆或者小堆,从倒数第一个非叶子结点开始调整,一定能够保证待排序序列的左右子树都是大堆或者小堆,此时即可看作大堆又可以看作小堆,根据需要进行调整即可;

倒数第一个非叶子结点恰好是最后一个结点的父亲,最后一个结点的下标为n-1,套用公式:parent=(child-1)/2,则该结点下标为:(n-1-1) / 2;

	//建堆 升序建大堆,降序建小堆
    for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}

 详细图解可参考:数据结构之堆-CSDN博客

堆排序的基本思想:

  1. 将待排序序列构造成一个大根堆
  2. 整个序列的最大值就是堆顶的根节点
  3. 堆顶元素数组尾元素进行交换,此时数组尾元素就为最大值;
  4. 将数组尾元素不看做堆里面的数据,前n-1个数继续向下调整为堆,选出次大的数,和倒数第二个位置的数交换;反复执行,得到升序序列;

堆排序代码实现

void HeapSort(int* arr, int n)
{
    //建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(arr, n, i);
	}
    //排序
	int end = n - 1;
	while (end > 0)
	{
		swap(&arr[0], &arr[end]);
		AdjustDown(arr, end, 0);
		end--;
	}
}

堆排序特性总结

1.时间复杂度

堆向下调整算法的时间复杂度为O(logn),堆排序由建堆与排序俩部分组成,建堆的时间复杂度O(n) ;  假设节点数为n,需要进行n-1次交换,每次调整的时间复杂度O(logn),总的时间复杂度为(n-1)*O(logn),所以 堆排序的时间复杂度O(n)+O(n*logn)=O(n*logn)

2. 空间复杂度

堆排序的空间复杂度为O(1),因为在堆排序时是对原数组进行直接排序,并没有创建其他新的数组;

3.算法稳定性

堆排序是一种非稳定的排序算法,堆排序时需要交换堆顶和堆尾的数据,交换时两个相等的数据在序列中的相对位置就可能发生改变,所以堆排序不是一个稳定排序;文章来源地址https://www.toymoban.com/news/detail-775248.html

到了这里,关于【数据结构】八大排序(一)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】--八大排序算法【完整版】

    本文主要讲解代码及代码思路,涵盖八大排序的全面知识点 ———————————————— 目录 一、直接插入排序 二、希尔排序(直接插入排序的改良版) 三、选择排序(直接选择排序) 四、堆排序 五、冒泡排序 六、快速排序 1、 左右指针法 2、挖坑法: 3、前后指针

    2024年02月16日
    浏览(46)
  • 【数据结构】 常见的八大排序算法

    排序有 内部排序和外部排序 ,内部排序是数据记录在内存中进行排序,这里八大排序就是内部排序,指直接插入,希尔,选择,堆排,冒泡,快排,归并,计数。 下面让我们来共同学习这八大排序吧!🤗🤗🤗 什么是外部排序: 外排序是数据量较大,内存放不下,数据放到外

    2024年02月12日
    浏览(112)
  • 第五章 数据结构与算法——八大排序

    目录 一、排序的概念及其运用 二、八大排序的原理及其实现(升序为例) (一)、直接插入排序 (二)、希尔排序(也叫缩小增量排序)(重要) 1.原理: 2.该排序一般分为两个步骤: 3.预排序过程: 4.预排序的意义(升序为例): 5.希尔排序的特点: 6.希尔排序代码实现

    2024年02月19日
    浏览(52)
  • 【数据结构初阶】八大排序算法+时空复杂度

    学会控制自己是人生的必修课 1.直接插入排序思想: 假设现在已经有一个有序序列,如果有一个数字插入到这段序列的末尾,我们会选择拿这个数和它前面的每个数字都比较一遍,如果前面的数字比他大,那我们就让前面的数字赋值到这个被插入的数字位置,依次与前面的数

    2024年02月01日
    浏览(117)
  • 【数据结构】八大排序算法(内含思维导图和画图分析)

    作者主页: paper jie_博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于《JAVA数据结构》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将javaSE基础知识一网打尽,希望可以帮到读者们哦。 其他专栏:

    2024年02月08日
    浏览(63)
  • 手把手教你 ,带你彻底掌握八大排序算法【数据结构】

    直接插入排序是一种简单的插入排序法,其基本思想:是把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 可以理解为一遍摸扑克牌,一边进行排序 在待排序的元素中,假设前面n-1(其中n=2)个数

    2024年02月02日
    浏览(67)
  • 【数据结构与算法】万字剖析八大排序(直接插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、计数排序)

    初窥直接插入排序我们先来看一张动图: 由动图我们可以分析出直接插入排序是从 第二个数据开始遍历 ,与 前面的数据进行比较 如果小于 则让前面的数据向前移动 自己接着向前面的数据比较 直到比较到 大于等于自己的 数据或者 没有数据能进行比较 时停止 插入当前的位

    2023年04月13日
    浏览(67)
  • 【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)

    ​👻内容专栏: 《数据结构与算法篇》 🐨本文概括: 利用数据结构栈(Stack)来模拟递归,实现快排的非递归版本;递归版本测试OJ题时,有大量重复元素样例不能通过,导致性能下降,优化快速排序通过将数组划分为三个区域,可以更有效地处理重复元素。 🐼本文作者:

    2024年02月11日
    浏览(83)
  • 【数据结构--八大排序】之希尔排序

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 前言: 本篇将开始希

    2024年02月08日
    浏览(43)
  • 【数据结构--八大排序】之堆排序

    💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃 个人主页 :阿然成长日记 👈点击可跳转 📆 个人专栏: 🔹数据结构与算法🔹C语言进阶 🚩 不能则学,不知则问,耻于问人,决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍 口诀:排降序,建小

    2024年02月08日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包