【数据结构】——排序详解_将键值较大的记录向序列的尾部移动

在日常生活中我们遇到了很多排序问题，无论是你你所见到的商品标签还是学校里面的成绩排名，这篇文章就让我们来好好看看直接插入、希尔、直接选择、堆、冒泡、归并排序吧~

1、排序概述

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

常见的排序算法

2、插入排序

2.1直接插入排序

1、基本思想（类似于玩扑克）
把要进行排序的记录按照关键码值的大小，挨个儿插入到已经排好序的有序序列当中，直到把所有的记录插完了为止。

2、实现流程
当插入第i个元素的时候，前面的数据已经排好序，此时用i位置上面的数字与前面i-1个数字作比较，再插入到合适位置。合适位置之后的元素都后移一位。

3、特点

• 元素集合越接近有序，直接插入排序算法的时间效率越高
• 时间复杂度：O(n²)
• 空间复杂度：O(1)
• 稳定

4、代码实现

• 总体上分为两层循环，外层循环主要是遍历未排序数组，内层循环主要是在已排序数组中找到合适的位置将数据插入。

• 细节上要注意用一个temp保存当前要插入元素的值，并且数组整体往后移的过程要是arr[j+1]=arr[j],而不能是arr[j]=arr[j-1]因为可能存在到0号下标越界的情况。

• 最后找到了位置，是通过arr[j+1]=temp的形式填充

void SelectSort1(int arr[], int n)
{
   
	int i, j, temp;
	for (i = 1; i < n; i++)
	{
   
		temp = arr[i];
		for (j = i - 1; j >= 0; j--)
		{
   
			if (arr[j] > temp)
			{
   
				arr[j + 1] = arr[j];
			}
			else
			{
   
				break;
			}
		}
		arr[j + 1] = temp;
	}
}
void show(int arr[], int n)
{
   
	for (int i = 0; i < n; i++)
	{
   
		std::cout << arr[i] << " ";
	}
	std::cout << std::endl;
}
int main()
{
   
	int arrrr[] = {
    0,5,2,6,1,3 };
	int n = sizeof(arrrr) / sizeof(arrrr[0]);
	show(arrrr, n);
	SelectSort1(arrrr, n);
	show(arrrr, n);	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

运行结果如下所示：

2.2希尔排序

1、基本思想（缩小增量法）
先选定一个一个整数n,n为分组的元素个数，然后将待排序的所有元素，从头开始分成含有n个元素的个组，在个组里面元素进行排序。然后，取、重复上述分组和排序的工作。当n=1时，所有记录在同一组内排好序。

2、实现流程
n=5的时候第一趟排序

n=2的时候第二趟排序结果

n=1的时候第三趟排序结果

3、特点

• 希尔排序是对直接插入排序的优化
• 当n>1时都是预排序，目的是让数组更接近于有序。当n=1时，数组已经接近有序了，这样就会很快。这样整体而言，可以达到优化的效果
• 时间复杂度：O(nlogⁿ)
• 不稳定

4、代码实现

#include<iostream>

//每一组组内排序，流程和直接插入排序一样
void Shell(int* arr,int n, int gap)
{
   
	int i,j, temp;
	for (i = gap; i < n; i++)
	{
   
		temp = arr[i];
		for (j = i - gap; j >= 0; j 
1
2
3
4
5
6
7
8
9
10
11