数据结构C语言代码实战06-排序

红太狼 2022-10-28 14:23 171阅读 0赞

# Lesson6--排序 #

**【本节目标】**

**1.排序的概念及其运用**

**2.常见排序算法的实现**

**3.排序算法复杂度及稳定性分析**

### 1.排序的概念及其运用 ###

**1.1排序的概念**  
**排序**：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。  
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次  
序保持不变，即在原序列中，r\[i\]=r\[j\]，且r\[i\]在r\[j\]之前，而在排序后的序列中，r\[i\]仍在r\[j\]之前，则称这种排  
序算法是稳定的；否则称为不稳定的。  
**内部排序**：数据元素全部放在内存中的排序。  
**外部排序**：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

**1.2排序运用**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1][]

**1.3 常见的排序算法**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 2][]

// 排序实现的接口
    
    // 插入排序
    void InsertSort(int* a, int n);
    
    // 希尔排序
    void ShellSort(int* a, int n);
    
    // 选择排序
    void SelectSort(int* a, int n);
    
    // 堆排序
    void AdjustDwon(int* a, int n, int root);
    void HeapSort(int* a, int n);
    
    // 冒泡排序
    void BubbleSort(int* a, int n)
    
    // 快速排序递归实现
    // 快速排序hoare版本
    int PartSort1(int* a, int left, int right);
    // 快速排序挖坑法
    int PartSort2(int* a, int left, int right);
    // 快速排序前后指针法
    int PartSort3(int* a, int left, int right);
    void QuickSort(int* a, int left, int right);
    
    // 快速排序 非递归实现
    void QuickSortNonR(int* a, int left, int right)
    
    // 归并排序递归实现
    void MergeSort(int* a, int n)
    // 归并排序非递归实现
    void MergeSortNonR(int* a, int n)
    
    // 计数排序
    void CountSort(int* a, int n)
    
    // 测试排序的性能对比
    void TestOP()
    {
    	srand(time(0));
    	const int N = 100000;
    	int* a1 = (int*)malloc(sizeof(int) * N);
    	int* a2 = (int*)malloc(sizeof(int) * N);
    	int* a3 = (int*)malloc(sizeof(int) * N);
    	int* a4 = (int*)malloc(sizeof(int) * N);
    	int* a5 = (int*)malloc(sizeof(int) * N);
    	int* a6 = (int*)malloc(sizeof(int) * N);
    
    	for (int i = 0; i < N; ++i)
    	{
    		a1[i] = rand();
    		a2[i] = a1[i];
    
    		a3[i] = a1[i];
    		a4[i] = a1[i];
    		a5[i] = a1[i];
    		a6[i] = a1[i];
    
    	}
    
    	int begin1 = clock();
    	InsertSort(a1, N);
    	int end1 = clock();
    
    	int begin2 = clock();
    	ShellSort(a2, N);
    	int end2 = clock();
    
    	int begin3 = clock();
    	SelectSort(a3, N);
    	int end3 = clock();
    
    	int begin4 = clock();
    	HeapSort(a4, N);
    	int end4 = clock();
    
    	int begin5 = clock();
    	QuickSort(a5, 0, N - 1);
    	int end5 = clock();
    
    	int begin6 = clock();
    	MergeSort(a6, N);
    	int end6 = clock();
    
    	printf("InsertSort:%d\n", end1 - begin1);
    	printf("ShellSort:%d\n", end2 - begin2);
    	printf("SelectSort:%d\n", end3 - begin3);
    	printf("HeapSort:%d\n", end4 - begin4);
    	printf("QuickSort:%d\n", end5 - begin5);
    	printf("MergeSort:%d\n", end6 - begin6);
    
    	free(a1);
    	free(a2);
    	free(a3);
    	free(a4);
    	free(a5);
    	free(a6);
    }

排序OJ(可使用各种排序跑这个OJ)OJ链接[http://leetcode-cn.com/problems/sort-an-array/][http_leetcode-cn.com_problems_sort-an-array]

### **2.常见排序算法的实现** ###

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 3][]

**2.1.2直接插入排序：**

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

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

**2.1.3 希尔排序( 缩小增量排序 )**  
希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个  
组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工  
作。当到达=1时，所有记录在统一组内排好序。  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 5][]  
希尔排序的特性总结：  
1. 希尔排序是对直接插入排序的优化。  
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就  
会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。  
3. 希尔排序的时间复杂度不好计算，需要进行推导，推导出来平均时间复杂度： O(![N^1^.^3-N^2][N_1_._3-N_2]）  
4. 稳定性：不稳定

**2.2 选择排序**

**2.2.1基本思想：**  
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的  
数据元素排完 。

**2.2.2 直接选择排序:**

在元素集合array\[i\]--array\[n-1\]中选择关键码最大(小)的数据元素  
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换  
在剩余的array\[i\]--array\[n-2\]（array\[i+1\]--array\[n-1\]）集合中，重复上述步骤，直到集合剩余1个元素

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 6][]

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用  
2. 时间复杂度：O(N^2)  
3. 空间复杂度：O(1)  
4. 稳定性：不稳定

**2.2.3 堆排序**

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是  
通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 7][]

直接选择排序的特性总结：

1. 堆排序使用堆来选数，效率就高了很多。  
2. 时间复杂度：O(N\*logN)  
3. 空间复杂度：O(1)  
4. 稳定性：不稳定

**2.3 交换排序**  
基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排  
序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

**2.3.1冒泡排序**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 8][]

冒泡排序的特性总结：  
1. 冒泡排序是一种非常容易理解的排序  
2. 时间复杂度：O(N^2)  
3. 空间复杂度：O(1)  
4. 稳定性：稳定

**2.3.2 快速排序**

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中  
的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右  
子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。  
将区间按照基准值划分为左右两半部分的常见方式有：  
1. hoare版本  
2. 挖坑法  
3. 前后指针版本  
上面三种方法我们都会讲解实现一下：

![20210206192331975.jpg][]  
整体实现思想：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 9][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 10][]

**2.3.2 快速排序优化**

1. 三数取中法选key  
2. 递归到小的子区间时，可以考虑使用插入排序  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 11][]

**2.3.2 快速排序非递归**

void QuickSortNonR(int* a, int left, int right)
    {
    	Stack st;
    	StackInit(&st);
    
    	StackPush(&st, left);
    	StackPush(&st, right);
    
    	while (StackEmpty(&st) != 0)
    	{
    		int end = StackTop(&st);
    		StackPop(&st);
    		int begin = StackTop(&st);
    		StackPop(&st);
    
    		int div = PartSort1(a, begin, end);
    		if (begin < div - 1)
    		{
    			StackPush(&st, begin);
    			StackPush(&st, div - 1);
    		}
    
    		if (div + 1 < end)
    		{
    			StackPush(&st, div + 1);
    			StackPush(&st, end);
    		}
    	}
    }

快速排序的特性总结：

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序  
2. 时间复杂度：O(N\*logN)

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 12][]  
3. 空间复杂度：O(logN)  
4. 稳定性：不稳定

**2.4 归并排序**  
基本思想：  
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and  
Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有  
序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 13][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 14][]

归并排序的特性总结：  
1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。  
2. 时间复杂度：O(N\*logN)  
3. 空间复杂度：O(N)  
4. 稳定性：稳定

**2.5 非比较排序**  
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用。 操作步骤：  
1. 统计相同元素出现次数  
2. 根据统计的结果将序列回收到原来的序列中

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 15][]  
计数排序的特性总结：

1. 计数排序在数据范围集中时，效率很高，但是适用范围及场景有限。  
2. 时间复杂度：O(MAX(N,范围))  
3. 空间复杂度：O(范围)  
4. 稳定性：稳定

**3.排序算法复杂度及稳定性分析**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 16][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 17][]  
**4.选择题练习**

1. 快速排序算法是基于（）的一个排序算法。  
   
A分治法  
B贪心法  
C递归法  
D动态规划法

2.对记录（54,38,96,23,15,72,60,45,83）进行从小到大的直接插入排序时，当把第8个记录45插入到有序表  
时，为找到插入位置需比较（ ）次？（采用从后往前比较）  
A 3  
B 4  
C 5  
D 6

3.以下排序方式中占用O（n）辅助存储空间的是  
A 简单排序  
B 快速排序  
C 堆排序  
D 归并排序

4.下列排序算法中稳定且时间复杂度为O(n2)的是（ ）  
A 快速排序  
B 冒泡排序  
C 直接选择排序  
D 归并排序

5.关于排序，下面说法不正确的是  
A 快排时间复杂度为O(N\*logN)，空间复杂度为O(logN)  
B 归并排序是一种稳定的排序,堆排序和快排均不稳定  
C 序列基本有序时，快排退化成冒泡排序，直接插入排序最快  
D 归并排序空间复杂度为O(N), 堆排序空间复杂度的为O(logN)

6.下列排序法中，最坏情况下时间复杂度最小的是（ ）  
A 堆排序  
B 快速排序  
C 希尔排序  
D 冒泡排序

7.设一组初始记录关键字序列为(65,56,72,99,86,25,34,66)，则以第一个关键字65为基准而得到的一趟快速排  
   
序结果是（）  
A 34，56，25，65，86，99，72，66  
B 25，34，56，65，99，86，72，66  
C 34，56，25，65，66，99，86，72  
D 34，56，25，65，99，86，72，66

答案：  
1.A  
2.C  
3.D  
4.B  
5.D  
6.A  
7.A

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221024/75d969292aac47149f039e5a46f9b518.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1]: /images/20221024/5f20487379dd4c75abf2f4f497c8ee31.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 2]: /images/20221024/6ae8da579320419cacbe94a7320626cd.png
[http_leetcode-cn.com_problems_sort-an-array]: http://https/leetcode-cn.com/problems/sort-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 3]: /images/20221024/8dbb3f7f190e4353b9fb826b8f8f6c73.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 4]: /images/20221024/29b284603c704868a29268551efe1ed4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 5]: /images/20221024/14679fdc7dbc465fb6caa8509243eb21.png
[N_1_._3-N_2]: https://private.codecogs.com/gif.latex?N%5E1%5E.%5E3-N%5E2
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 6]: /images/20221024/fbad93f56ceb49429fcea0a53eb0a7db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 7]: /images/20221024/a2dceea52eba4beea2e0932c0aa75be2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 8]: /images/20221024/546f67875be9485dabf22f34a0c9b894.png
[20210206192331975.jpg]: /images/20221024/ce11578c140b40848fef3f7d4dc24b7b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 9]: /images/20221024/b5c62553a88c4382a8ebbb805c3cf134.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 10]: /images/20221024/6a6ecf6f92334d66a55fb649aae292b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 11]: /images/20221024/bd2cfc6dd2704504a9813ae7292b1333.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 12]: /images/20221024/610ab15a05384a4f99fdc0300da4b680.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 13]: /images/20221024/a3f05f7e26124247b1356116d7eec327.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 14]: /images/20221024/137ae96371b8418abb63b524f0c97b8b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 15]: /images/20221024/867507e36b95425ca38d492b8f5f7825.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 16]: /images/20221024/82cfe9c0e910427ea76b7b154c7995a5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 17]: /images/20221024/77d651fceb964a77b06cd7e605005bd3.png