在这里插入图片描述

📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：数据结构
🎯长路漫漫浩浩，万事皆有期待

文章目录

1.排序的概念和运用
- 1.1排序的概念：
- 1.2.常见排序应用：
- 2.常见的排序算法：
2、直接插入排序
- 2.1 排序思路
- 2.2 代码实现
- 2.3 特性及复杂度
3、希尔排序
- 3.1 排序思路
- 3.2 代码实现
- 3.3 特性及复杂度
4.总结：

1.排序的概念和运用

1.1排序的概念：

排序：所谓排序，就是将一串数据，按照某种规律，或者以某种特性或关键字，将数据按照递增或者递减，将数据从无序转变为有序的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，则称之为稳定。例如 a[i]=a[j]，且 a[i] 在a[j] 之前，而在排序后的序列中，a[i] 仍在a[j] 之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：内部排序也称为内排序，是指待排的记录全部在内存中完成排序的过程，是被排序的数据元素全部存放在计算机内存中的排序算法。
外部排序：外部排序指的是大文件的排序，即待排序的记录存储在外存储器上，待排序的文件无法一次装入内存，需要在内存和外部存储器之间进行多次数据交换，以达到排序整个文件的目的。根据排序过程的要求，是不能在内外存之间移动数据的排序。

1.2.常见排序应用：

而排序其实在我们生活中运用十分广泛，例如在购物网站上选购一个电脑，可以通过综合、销量、评论数、新品价格来排序，如果对价格有需求，也可以按照价格升序，或者降序来排序，通过这种方式来买到心仪的商品。
在这里插入图片描述

不难发现，在我们的日常生活中排序算的使用随处可见，充斥着我们的各项生产活动，我们的考试排名、绩效考核、综测排名，包括CSDN的各种排名都广泛的使用到了许多种不尽相同的排序算法。
在这里插入图片描述

而究其根本，这些都需要排序算法来实现。那么在编程中有什么排序算法，它们的性能如何？如何模拟实现这些算法？

接下来的几篇博客中，我们会依次学习常见的排序算法，并进行对比，以便于我们更好的理解这些算法的使用方式、使用条件与适用场景等等。

2.常见的排序算法：

在这里插入图片描述
最常用的排序算法可以分为四大类：插入排序、选择排序、交换排序与归并排序。插入排序的代表算法有直接插入排序与希尔排序；选择排序的排序算法代表是选择排序与堆排序；交换排序中我们要熟识冒泡排序与快速排序；归并排序则主要是以归并排序算法为主，及一些由归并思想衍生出的排序算法。

下图是常见八大排序的比较：
请添加图片描述

2、直接插入排序

2.1 排序思路

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

我们的扑克牌就使用了插入排序的思想：
在这里插入图片描述

比如拿到牌之后，我们都会理牌，那么通常就会按照大小顺序，将牌理成整体有序，或者局部有序。

其实插入排序的过程就可以想象成之前我们学习 顺序表的尾插 ，我们假定序列 array[] 只有 1 个数。假定每次都是插入一个元素，且插入的元素需要将这个 ”顺序表“ 构成有序，如果插入元素array[i]<arr[i−1] ，那么就至少需要向前调整 1次；如果array[i]≥array[i−1] 那么就直接插入在 i下标处即可。

动图演示插入排序过程：
在这里插入图片描述

2.2 代码实现

对于 单趟插入排序 ，假设 end 是上一次排序的最后一个位置，那么本次需要排序的元素为 tmp=a[end+1] 。

之后通过一个循环，如果a[end]>tmp ，说明 tmp 插入的位置在前面，所以把a[end+1]=a[end] ，将元素往后移 1 格，并将 end−− ，将索引向前调整；如果 a[end]<=tmp ，说明tmp 在当前位置：end+1 就可以直接插入，停止循环。

最后 end 停下来的位置永远是插入位置的前一个位置，比如看下图：
在这里插入图片描述

这是单趟，那么完整的就是n−1 趟，因为第一个元素是不用排的，第一趟其实就是排的序列的第二个元素了。每趟最终插入的位置为 end + 1 ，注意防止越界。

完整的多趟 实现步骤：
1.从第一个元素开始，该元素可以认为已经被排序。
2.取下一个元素作为 tmp，从已排序的元素序列从后向前扫描。
3.如果该元素大于 tmp，则将该元素移到下一位。
4.重复步骤 3，直到找到已排序元素中小于或等于 tmp 的元素。
5.将 temp 插入到该元素的后面，如果已排序所有元素都大于 tmp，则将 tmp 插入到下标为 0 的位置。
重复步骤 2 ~ 5，直至完成排序。

void InserSort(int* a, int n)
{
	//多趟控制
	int i = 0;
	for (i = 0; i < n - 1; i++)
	{
		//单趟控制
		int end = i ;
		int temp = a[end + 1];
		while (end >= 0)
		{
			//目标数小于其它数时，其它数就往后挪；大于则插入
			if (temp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = temp;
	//代码执行到此有两种情况:
	//1.待插入元素找到应插入位置（break跳出循环到此）
	//2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）
	}
}

2.3 特性及复杂度

插入排序的最坏的情况为原始序列为降序。此时，时间复杂度最坏，为O(N^2)。
如果目的是升序，序列也正好是升序的话，为最好情况，这时时间复杂度为O(N) 。

取其最坏，最终时间复杂度：O(N^2)
插入排序并没有开辟额外空间，所以空间复杂度：O(1)

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

3、希尔排序

3.1 排序思路

希尔排序也属于插入排序，但是和直接插入排序又略微不同。

概念：希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把所有待排序记录记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时，整个文件恰被分成一组，即所有记录在统一组内排好序。

简单来说，意思是取一个整数，作为间距gap ，对于每个元素，与其间隔为gap 的元素分成一个组，对每组排序。不断调整gap，对每组进行不断排序，在 gap调整到 1 后进行插入排序，就可以将数据排成有序。而按照间距gap分组并排序被称为预排序。

所以可以归纳希尔排序的步骤就是两点：

预排序 -目标：让数组接近有序（分组插排）
直接插入排序

比如，一次完整希尔排序就像下图：
在这里插入图片描述

3.2 代码实现

希尔排序属于插入排序，而它的思想其实是和直接插入排序差不多的，因为最后一次希尔排序为插入排序。希尔排序无非就是多了几组预排序的过程。所以它的代码和直接插入排序十分相似。

对于插入排序，我们其实就可以看做是 gap = 1的希尔排序，那么把插入排序一些数据做一下替换，就得出了单组希尔排序：

// 对于一组
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;
}

这里的gap不仅是每组中元素的间距，也是组数。上面代码只完成了单组，对于完整的一组需要在外面套上一层循环，需要循环gap次：

for (int j = 0; j < gap ;j++) 
{
	for (int i = j; i < n - gap; i += gap)
    {
        // ...
    }
}

我们发现，只需要把之前的挪动 1 位看成挪动 gap 位。

注意 对单组进行排序时的结束条件i < n - gap ，这里结束条件是这个的原因为最后一组的最后一个元素下标为 n - gap - 1 ，当元素进行插入时，不能越界。

但这样写，就套了三层循环了，看起来比较繁琐，我们可以做出一些调整，上方代码为排 gap 组，每次排一组。我们可以改进为gap 组并排 ：

for (int i = 0; i < n - gap; i++) // 注意这里从 i+= gap 变为 i++
{
    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;
}

这里就只有两层循环了，代码更加简洁，唯一改变的是i+=gap 变为i++

这里就相当于，每一次都是排其他组的数据，举个例子：当前 i = 0 ，那么此刻排的就是第一组，之后i++ ，i=1 ，那么此刻就是排的第二组 … 当循环结束，这gap 组数据也就都被排好了。这就是gap 组并排。

而希尔排序的预排序的 gap 越大时，那么对于单组中的数据就可以更快地到后面(挪动间距为gap)，但这时的数据并不接近有序；而 gap 越小时，数据跳动越慢，但是越来越接近有序(比如插入排序) 。综合这两点，所以我们一般进行希尔排序时，gap 是动态变化的，gap 的初值一般为数组长度。之后每次除以一半或者除以三分之一。

比如每次除以三分之一：

while (gap > 1)//gap=1 已经排过了
{
    gap = gap / 3 + 1; // 或 gap /= 2;
    // gap 组并排
    for (int i = 0; i < n - gap; i++)
    {
        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/3+1，为什么在这边+1 呢？原因是希尔排序最后 1 次为插入排序，所以最后 1 次gap=1 ，如果 gap 初值为 8，如果每次仅仅让 gap/=3 ，由于c语言中 / 是下取整，那么每次gap 就为 8 2 0 ，最后 1次为 0 ，无法完成希尔排序，所以要加上一个 1 ，这样就可以保证最后 1 次 gap=1 。

但是如果每次除以2的情况就不需要，因为每gap/=2 最终结果必定等于 1 ，可以通过举例子证明。

3.3 特性及复杂度

数据被分为 gap 组，每组有 N/gap 个数据。对于单组，最坏的挪动次数就是1+2+3+…+N/gap−1 ，是公差为 1 的等差数列。

一共有gap 组，那么对于一次预排序的总次数就为(1+2+3+…+N/gap−1)×gap ，但是这里gap 是不确定的。那对于每次预排序的时间复杂度，该怎么计算?
在这里插入图片描述
1.首先，根据代码分析
如果gap 每次除以 3 ，那么就大约进行 N / 3 / 3 / 3… / 3 = log ₃ N次；
如果gap 每次除以 2 ，那么就大约进行 N / 2 / 2 / 2… / 2 = log ₂N 次；

2.其次，假设gap 每次除以 3 ，一开始 N 很大，gap=N/3+1 ，将当前 gap 的取值带入上方对于一次预排序的次数的公式中，通过极限的思想， ( 1 + 2 + 3 + . . . + $N\over(N / 3 + 1)$ − 1 ) × ( N / 3 + 1 ) ≈ N ，那么起始处，预排总次数约为 N