DS几大常见排序讲解和实现(上)(13)

文章目录

• 前言
• 一、排序的概念及其运用
• • 排序
  • 稳定性
  • 内部排序
  • 外部排序
  • 实际运用
• 二、常见排序算法
• 三、直接插入排序
• • 基本思想
  • 实现思路
  • 代码实现
  • 时间空间复杂度分析
  • 总结
• 总结

前言

  我们今天在这里学排序，可能会感概思维的巧妙、前人的智慧
  正文开始！

一、排序的概念及其运用

排序

  排序是一种将一组对象按照某种特定顺序重新排列的过程。在计算机科学中，排序是数据处理中非常基本且重要的操作，它可以帮助人们更有效地理解和分析数据。排序的顺序通常是升序或降序，也可以按照数字、字母、大小或其他标准进行排序

稳定性

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

内部排序

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

外部排序

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

实际运用

  排序的运用非常常见，在我们购物的软件上面，经常会根据不同的属性来进行排序，我们以前上学时候的成绩通常也会对各科进行排序！！！！

二、常见排序算法

这些排序我都会跟大家细细讲解，同时也是对我的一种有效复习~

三、直接插入排序

基本思想

  把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。实际中我们玩扑克牌时，就用了插入排序的思想

想象下你打牌，摸牌的时候摸到一张二，放手上，摸到一张五，放二的右边，再摸到4，这时候就要放在二和五的中间了

实现思路

  当插入第 i (i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

动图如下：

代码实现

合抱之木，生于毫末

我们应该依次思考一下问题：

一、函数头怎么设计，参数是什么？
  毋庸置疑的是需要传一个待排序的数组，其次进行排序的时候是需要遍历数组的，因此需要知道元素个数，那为什么我们不能直接传数组，然后在函数内部计算元素个数呢？

 答案是将数组作为形参传给函数，此数组的实质是一个地址，而计算大小是用数组大小/数组元素大小，此时sizeof(数组名) 计算的大小是4或者8，不能准确计算元素个数

// 因此正常的函数头为
// 采用升序
void InsertSort(int a[], int n); 

二、分析单趟排序的情况
这时候，我们会遇到两种情况：

1. 待排序的数大于其中任意一个已经排序好的数( tmp > a[i] )
   

这里的end代表已排序序列的最后一个元素的索引。将插入的数(tmp)依次往前比较，如果比前面的end位置的数小，则将此end位置的数放到end + 1 位置，并将end --，如果大于等于前面的数字，说明此位置就是插入的数的位置，将插入的数给end + 1下标即可

2. 待排序的数比所有已经排序好的数要小

通过上面两种情况可以总结出循环的条件是end >=0

int end;
int tmp = a[end + 1];

while (end >= 0)
{
	if (a[end] > tmp)
	{
		a[end + 1] = a[end];
		end--;
	}
	else
    {
		break;
    }
}
a[end+1]=tmp;

 此时，不管我们最终跳出循环是找到插入位置，还是达到有序数组的起点，最终都能跳出循环并用 a[end + 1] = tmp 来插入

三、封装整个排序

一个元素就是有序数组，因此end从0开始

// 升序
void InsertSort(int a[], int n)
{
	// [a,end]有序
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp) // 前面的数大于后面则覆盖前面
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;// 填充空位置
	}
}

时间空间复杂度分析

  最好情况：这种情况发生在数组已经完全有序时。在这种情况下，每次比较后，很快就会找到插入位置（在已排序元素的末尾），不需要进行额外的移动。因此，最好情况下插入排序的时间复杂度是O(N)，因为外层循环只会遍历一次数组，内层循环不会进行任何实际的比较和移动操作

  最坏情况：如果数组是完全逆序的，那么每次插入操作都需要将元素移到已排序部分的开头。这就意味着对于第i个元素，可能需要进行i次比较和移动。这种情况下，算法的时间复杂度是O(N2)，因为需要进行总计约1 + 2 + 3 + … + (n-1)次比较，这是一个n(n-1)/2的等差数列

  而很明显，这个排序并没有多开空间，都是在原数组上操作，所以空间复杂度为O(1)

总结

1. 元素集合越接近有序，直接插入排序算法的时间效率越高。
2. 时间复杂度：O(N^2)。
3. 空间复杂度：O(1)，它是一种稳定的排序算法。
4. 稳定性：稳定

总结

  哈哈，感觉如何，你最好先自己实现一下，由于是刚开一新篇，我就先来个直插排序，敬请期待后续！