开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 数据结构-第5节-排序 -> 正文阅读

[数据结构与算法]数据结构-第5节-排序

1.排序的概念及其运用

1.1.排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

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

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

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

1.2.排序运用

1.3.常见的排序算法

2.常见排序算法的实现

2.1.直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际中我们玩扑克牌时，就用了插入排序的思想

代码思想：

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

Test.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void TestInsertSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	InsertSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}


int main()
{
	TestInsertSort();

	return 0;
}

Sort.h文件：

#pragma once
#include <stdio.h>

void PrintArray(int* a, int n);
void InsertSort(int* a, int n);

Sort.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}


void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		int end = i;
		// 单趟排序：[0, end]有序 end+1位置的值，插入进入，保持他依旧有序
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

注：

1.如果单趟排序代码如下图第一行左所示，那么当下面右图所示情况的话（就是插入的数值要放在第一个位置），到最后所有的数都往后移动一个位置，并且end指向-1的位置，此时end小于0结束，数据并没有放进去，改进代码如下图第二行所示

???

2.插入排序的时间复杂度：O( $N^{2}$ )

最坏：逆序的情况，O( $N^{2}$ )?

最好：顺序有序，O(N)

当要排序的序列大部分都已排好，只有个别数据有错时，插入排序的效率很高

2.2.希尔排序( 缩小增量排序 )

思路（以从小到大排序为例）：

1.预排序：分组排序，使大的数更快的到后面，小的数更快的到前面，使序列接近有序

（1）将序列进行分组（gap为几就分成了几组）

? ? ? ? ?

（2）分别使用插入排序的思想对这gap组数据进行排序

? ? ? ?

? ? ? ? 注：如果gap越小，越接近有序，大的数据到最后的速度较慢，小的数据到前面的速度? ? ? ? ? ? ? ? ?较慢

? ? ? ? ? ? ? ?如果gap越大，大的数据可以更快的到后面，小的数据可以更快的到前面，但是他? ? ? ? ? ? ? ? ?越不接近有序

2.直接插入排序

Test.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void TestShellSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	ShellSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));

}


int main()
{
	TestShellSort();

	return 0;
}

Sort.h文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void PrintArray(int* a, int n);

void ShellSort(int* a, int n);

Sort.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		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;
		}
	}
}

注：

1.预排序有两种写法：

第一种是使用三层循环，其中最里面的while循环是将一个tmp插入到前面排好的序列中，中间的for循环是控制一组数据进行排序，外面的for循环控制gap组数据进行排序

第二种是使用两层循环，其中里面的while循环是将一个tmp插入到前面排好的序列中，外面的for循环是从前往后多组同时进行排序

2.gap到底取多少（到底分多少组），取决于需要排序序列的数据个数，数据越多，gap的取值也应该越大。我们可以让gap从大到小多次预排列，到最后gap等于一时，就是直接插入排序，希尔排序结束。让gap每次减小进行预排序，我们使用gap=gap/3+1，这样我们就保证了最后一次一定是gap=1进行直接插入排序。

3.希尔排序的时间复杂度：

gap开始很大，到后面慢慢gap=gap/3+1变小

开始当gap很大时，数据跳的很快，里面的while循环可以忽略不计，时间复杂度约为O(N)

后来当gap很小时，此时序列已经很接近有序了，时间复杂度约为O(N)

因此，无论gap很大还是很小，总体可以理解为下面红框里的程序只要运行一次，时间复杂度就为O(N)，因为gap初始为n，gap=gap/3+1，那么红框里的程序运行约 $log_{3}^{N}$ 次，因此总的时间复杂度约为O( $N\times log_{3}^{N}$ )（log以3为底是因为我们这里是gap=gap/3+1变小，如果gap=gap/2那么就是log以2为底）

根据研究者们研究，综合各种情况，发现希尔排序的时间复杂度约为O( $N^{1.3}$ )

4.那么希尔排序和直接插入排序孰优孰劣，我们可以通过代码运行时间来判断，clock函数是获取计算机执行到该函数时的毫秒数，代码如下图所示，我们可以看出希尔排序比直接插入排序效率要高很多
Test.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void TestOP()
{
	srand(time(0));
	const int N = 10000;
	int* a1 = (int*)malloc(sizeof(int) * N);
	int* a2 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
		a2[i] = a1[i];
	}

	int begin1 = clock();
	InsertSort(a1, N);
	int end1 = clock();

	int begin2 = clock();
	ShellSort(a2, N);
	int end2 = clock();


	printf("InsertSort:%d\n", end1 - begin1);
	printf("ShellSort:%d\n", end2 - begin2);
	
	free(a1);
	free(a2);
	
}


int main()
{

	TestOP();

	return 0;
}

Sort.h文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void PrintArray(int* a, int n);

void InsertSort(int* a, int n);

void ShellSort(int* a, int n);

Sort.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

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
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}


void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		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;
		}
	}
}

运行结果：

2.3.冒泡排序

Test.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void TestBubbleSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	BubbleSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}

int main()
{
	TestBubbleSort();

	return 0;
}

Sort.h文件：

#pragma once
#include <stdio.h>

void PrintArray(int* a, int n);

void BubbleSort(int* a, int n);

Sort.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void BubbleSort(int* a, int n)
{
	for (int j = 0; j < n; ++j)
	{
		int exchange = 0;
		// 单趟
		for (int i = 1; i < n-j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				exchange = 1;
				Swap(&a[i - 1], &a[i]);
			}
		}

		if (exchange == 0)
		{
			break;
		}
	}
}

注：

1.冒泡排序的时间复杂度：O( $N^{2}$ )

最坏：逆序的情况，O( $N^{2}$ )?

最好：上面代码用exchange置零的方法进行优化，如果遇到刚好是顺序有序的序列，第一次大循环两两比较发现没有进行交换，直接跳出循环，时间复杂度O(N)，如果不是顺序有序序列，时间复杂度?O( $N^{2}$ )。如果不进行优化，那么冒泡排序时间复杂度都为 O( $N^{2}$ ) 。

2.冒泡排序和插入排序想比较：

如果是顺序有序，那么插入和冒泡是一样的

如果是局部有序或者接近有序，那么插入适应性和比较次数更少

2.4.直接选择排序

基本思想：

每一次从待排序的数据元素中选出最小（或最大）的一个元素，与起始位置元素交换，然后剩下的元素重复前面操作，直到最后剩一个元素为止

优化版本：

每一次从待排序的数据元素中选出最小和最大的两个元素，分别与起始位置和末尾位置元素交换，然后剩下的元素重复前面操作，直到最后剩一个元素或没有剩下元素为止

Test.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void TestSelectSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	SelectSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}


int main()
{
	TestSelectSort();

	return 0;
}

Sort.h文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void PrintArray(int* a, int n);

void SelectSort(int* a, int n);

Sort.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void SelectSort(int* a, int n)
{
	int left = 0, right = n - 1;
	while (left < right)
	{
		int mini = left, maxi = left;
		for (int i = left + 1; i <= right; ++i)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[left], &a[mini]);
		Swap(&a[right], &a[maxi]);

		left++;
		right--;
	}
}

注：

1.下面左代码是有问题的，因为如果序列是9 1 2 5 7 4 8 6 3 5，那么第一次，left=0? right=9 mini=1 maxi=0，先执行Swap(&a[left], &a[mini])，此时序列为1 9 2 5 7 4 8 6 3 5，然后执行Swap(&a[right], &a[maxi])，此时序列为5?9 2 5 7 4 8 6 3 1，这并不是我们预想的结果，这种情况是因为left和maxi重叠，最小值换到left时，max被掉包换走了，换在了mini的位置。我们需要进行修正，如下图右代码

2.直接选择排序的时间复杂度：

最坏情况：O( $N^{2}$ )

最好情况：O( $N^{2}$ )

直接选择排序的时间复杂度：?O( $N^{2}$ )

2.4.堆排序

Test.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void TestHeapSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	HeapSort(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}


int main()
{
	TestHeapSort();

	return 0;
}

Sort.h文件：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void PrintArray(int* a, int n);

void AdjustDwon(int* a, int n, int root);
void HeapSort(int* a, int n);

Sort.c文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

void AdjustDown(int* a, size_t size, size_t root)
{
	size_t parent = root;
	size_t child = parent * 2 + 1;
	while (child < size)
	{
		// 1、选出左右孩子中小的那个
		if (child + 1 < size && a[child + 1] > a[child])
		{
			++child;
		}

		// 2、如果孩子小于父亲，则交换，并继续往下调整
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

// O（logN*N）
void HeapSort(int* a, int n)
{
	// 向上调整--建堆 O(N*logN)
	//for (int i = 1; i < n; ++i)
	//{
	//	AdjustUp(a, i);
	//}

	// 向下调整--建堆 O(N)
	for (int i = (n - 1 - 1) / 2; i >= 0; --i)
	{
		AdjustDown(a, n, i);
	}

	size_t end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

2.5.快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法

其基本思想为：

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

将区间按照基准值划分为左右两半部分（单趟排序）进行分类，常见方式有：

一.hoare版本

hoare版本单趟排序：

1.思路（升序排序为例）：

假设key取第一个位置的值，R从右往左找比Key小的值，L从左往右找比Key大的值，找到之后交换，再继续找，相遇以后（这里一定会相遇，因为最后一定是一个不动另一个在往下找然后相遇）把相遇位置的值跟key位置的值交换。

因为key是第一个位置的值，所以最后要保证交换前相遇点位置的值比key要小，这样才能确保交换后相遇点左边的值都比key小右边的值都比key大。如何保证交换前相遇点位置的值比key要小呢？答案是让右边先走（左右交换完了也是右边先走），解释如下（两种情况）：

（1）如果相遇是因为右边停下左边来相遇，那么相遇点就是右边停下的这个位置一定比key? ? ? ? ? ?小

（2）如果相遇是因为左边停下右边来相遇，那么相遇点就是左边停下的这个位置，这个位? ? ? ? ? ? ?置的数因为是之前和右交换过的数，因此也一定是比key小的

注：如果key取第一个位置的值，那么应该让右边先走

? ? ? ?如果key取最后一个位置的值，那么应该让左边先走

2.过程：

1.2.

3.?4.

5.?6.

7.?8.

9.?10.

11.?12.

13.?14.

15.?16.

3.代码：
int PartSort(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		// 找小
		while (left < right && a[right] >= a[keyi])
			--right;

		// 找大
		while (left < right && a[left] <= a[keyi])
			++left;

		Swap(&a[left], &a[right]);
	}

	Swap(&a[keyi], &a[left]);

	return left;
}
注：

1.下面代码是有问题的，因为如果序列是5 5 2 3 5，那么right永远指向最右边的5，left永远指向最左边的5，程序死循环，因此应该改成当a[right]>=a[keyi]时--right，当a[left]<=a[keyi]时++left。

但是如果两个修改成大于等于的话，如下图所示，对于序列1 2 3 4 5，right从最右边开始遍历整个序列都大于等于keyi，然后再--，越界访问。因此条件应改成当left < right && a[right] >= a[keyi]时--right，当left < right && a[left] <= a[keyi]时++left。

正确代码如下图所示

hoare版本快速排序：

1.思路：

1.一次单趟排序完后的key对应元素在该位置就不会再动了，已经放在了正确的位置，因此可以分为key左边的序列和key右边的序列，左边右边两个序列都有序那么整个序列都有序了。左边和右边如何有序呢？

答案是分支解决子问题，分别对左边序列和右边序列再进行单趟排序，以此类推，当子序列只有一个值或者不存在（begin>=end）就结束

注：这里面不是以子序列只有一个值（begin=end）作为结束标志，因为子序列是有可能不存在的（begin>end），如下图所示，左下角2 1序列进行单趟排序为1 2序列，此时keyi为1，再往下递归左序列的begin=0 、end=keyi-1=0，右序列begin=keyi+1=2、end=1，做序列有一个数据，右序列不存在，都应结束

?2.代码：

Test.c文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void TestQuickSort()
{
	int a[] = { 9, 1, 2, 5, 7, 4, 8, 6, 3, 5 };
	QuickSort(a, 0, sizeof(a) / sizeof(int) - 1);

	PrintArray(a, sizeof(a) / sizeof(int));
}


int main()
{
	TestQuickSort();

	return 0;
}
Sort.h文件：
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void PrintArray(int* a, int n);

void QuickSort(int* a, int begin, int end);
Sort.c文件：
#define _CRT_SECURE_NO_WARNINGS 1
#include "Sort.h"

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* pa, int* pb)
{
	int tmp = *pa;
	*pa = *pb;
	*pb = tmp;
}

int PartSort(int* a, int left, int right)
{
	int keyi = left;
	while (left < right)
	{
		// 找小
		while (left < right && a[right] >= a[keyi])
			--right;

		// 找大
		while (left < right && a[left] <= a[keyi])
			++left;

		Swap(&a[left], &a[right]);
	}

	Swap(&a[keyi], &a[left]);

	return left;
}

void QuickSort(int* a, int begin, int end)
{
	// 子区间相等只有一个值或者不存在那么就是递归结束的子问题
	if (begin >= end)
		return;

	int keyi = PartSort(a, begin, end);
	// [begin, keyi-1]keyi[keyi+1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);
}