- 1JVM实战(一)： dump文件的产生以及执行shell脚本_-xx:heapdumppath
- 2chromium中mojom通信开发实例（render进程-＞brower进程）
- 3微信小程序实现数值监听（页面和组件属性）_微信小程序怎么监听页面数据变化
- 4Java |与|| 、&与&& ，或与非的使用和区别
- 5shell变量_shell ++
- 6机器学习和人工智能的关系_机器学习与人工智能之间的关系
- 7js对象数组添加元素_js对象后面添加数组
- 8python小知识_python 小知识
- 9【Node Red 】 mysql数据库节点介绍_node-red 数据库
- 10联想rd650管理口地址_MegaRAID Storage Manager RAID管理工具基本操作
【C语言】八大排序算法_c语言排序算法
赞
踩
1.排序的概念及其应用
1.1排序的概念
排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字(如价格，销量，好评率，排名等)的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j],且r[i]在r[j]之前，而在排序后的序列中，依然保持此规律，则称这种排序算法是稳定的，否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：待排序的数据量很大，以致于内存不能一次容纳全部数据，所以在排序过程中需要对外存进行访问。
二者衡量效率的方法：内部排序：时间复杂度；外部排序：IO次数，也就是读写外存（如磁盘上的文件）的次数。
1.2排序的应用
1.3常见的排序算法
1.4时间性能的测试（测试排序算法的好坏）
1.排序OJ（可以使用多种排序算法来跑这个题）(注意有些算法会超出时间限制，如选择排序)。
2.时间性能
//测试排序函数性能(直观看出算法的好坏：通过排序的所消耗的时间)
void TestOP()
{
srand((unsigned int)time(NULL));//生成随机数
//带排序的数据量
int N = 100000;
//测试多个排序算法的方法：开辟多个相同数据的数组（动态，栈区空间可能会溢出）
int* a1 = (int*)malloc(sizeof(int)*N);
assert(a1);
int* a2 = (int*)malloc(sizeof(int)*N);
assert(a2);
int* a3 = (int*)malloc(sizeof(int)*N);
assert(a3);
int* a4 = (int*)malloc(sizeof(int)*N);
assert(a4);
int* a5 = (int*)malloc(sizeof(int)*N);
assert(a5);
int* a6 = (int*)malloc(sizeof(int)*N);
assert(a6);
int* a7 = (int*)malloc(sizeof(int)*N);
assert(a7);
int* a8 = (int*)malloc(sizeof(int)*N);
assert(a8);
//空间开辟完后，我们开始给这些数组相同的随机数据
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];
a7[i] = a1[i];
a8[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();
QuickSort1(a5, 0, N - 1);
int end5 = clock();
int begin5 = clock();
QuickSort2(a5, 0, N - 1);
int end5 = clock();
int begin5 = clock();
QuickSort3(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("QuickSort1:%d\n", end5 - begin5);
printf("QuickSort2:%d\n", end5 - begin5);
printf("QuickSort3:%d\n", end5 - begin5);
printf("MergeSort:%d\n", end6 - begin6);
free(a1);
free(a2);
free(a3);
free(a4);
free(a5);
free(a6);
free(a7);
free(a8);
}
int main()
{
TestOP();
return 0;
}
- 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
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
2.常见排序算法的实现
2.1直接插入排序
插入排序，又叫直接插入排序，我们在玩扑克牌的时候，就用到了直接插入排序的思想。在待排序的元素中，假设前n-1个元素已经有序，将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此思想，直到整个序列有序。但一开始的数据是随机的，所以我们不知道序列的哪个部分有序，所以一开始我们只能认为第一个元素是有序的，从第2个元素开始，依次向前面排好的序列插入。
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;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
直接插入排序算法特性：
1.数据越接近有序，直接插入排序算法效率越高。
2.最坏时间复杂度:O(N^2),最好时间复杂度：O(N)。
3.空间复杂度：O(1)
4.稳定性：稳定，
2.2希尔排序
希尔排序也是插入排序，但是它是对直接插入排序的一种优化。它又称为缩小增量排序，算法思想是：
1.先预排序：先选定一个小于N的整数gap作为第一次的增量，然后将所有距离为gap的元素分在同一组，并对每一组进行直接插入排序。然后gap增量减小，作为第二增量，重复以上操作。
2.再直接插入排序：当gap增量减小到1的时候，进行一次直接插入排序，则排序完成。
问题：为什么要让gap增量从大到小呢？
原因：当代排序的数据量很大时，如果gap过小，效率就较低，gap越大数据挪动的距离就越大，gap越小，数据挪动排序的距离就越小。前期让gap较大，可以让数据更快的挪动到自己对应的位置附近，减少挪动次数。直到gap的增量为1（缩小gap：gap=gap/2或gap=gap/3+1）。
void ShellSort(int* a, int n)
{
int gap = n;
while (gap > 1)//gap>1预排序，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
- 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
希尔排序算法特征总结：
1.平均时间复杂度：O(N^1.3)
2.空间复杂度：O(1)
3.稳定性：不稳定
2.3选择排序
选择排序，即每次从待排序的序列中选出一个最小值，然后放在序列的起始位置begin（排好一个元素之后，begin递增），直到全部待排序数据排序完成。
时间复杂度O(N^2),空间复杂度O(1)。
void SelectSort(int* a, int n)
{
//先假设第一个元素最小
for (int i = 0; i < n; i++)
{
int begin = i;
int minindex = i;
while (begin < n)
{
if (a[begin] < a[minindex])
{
minindex = begin;
}
begin++;
}
Swap(&a[minindex], &a[i]);
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
选择排序的优化版本：
实际上，我们可以一趟选出两个值，一个最大值，一个最小值，然后将最小值放在开头，最大值放在末尾，然后left++,right–,依次继续在剩下的数据当中找最大值和最小值，这样可以使选择排序的效率快一倍。
void SelectSort2(int* a, int n)
{
int left = 0;
int right = n - 1;
while (left < right)
{
int minindex = left;
int maxindex = left;
for (int i = left; i <= right; i++)
{
if (a[i] < a[minindex])
{
minindex = i;
}
if (a[i] > a[maxindex])
{
maxindex = i;
}
}
Swap(&a[minindex], &a[left]);
if (maxindex == left)
{
maxindex = minindex;
}
Swap(&a[maxindex], &a[right]);
left++;
right--;
}
}
- 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
直接选择排序的特性总结：
1.直接选择排序较其它排序较好理解，但是效率比较低，实际中少用。
2.最好和最坏的时间复杂度都是O(N^2)。
3.稳定性：不稳定。
2.4堆排序
要学习堆排序，首先要学习基础的二叉树结构，学习堆的向下调整算法，使用堆排序之前，我们得先建一个堆出来，堆的向下调整算法的前提是：根节点的左右子树均是大堆或小堆。由于堆排序在向下调整的过程中，需要从孩子中选择出较大或较小的那个孩子，父亲才与孩子进行交换，所以堆排序是一种选择排序。堆排序的详解请至博客：堆排序
void AdjustDown(int* a,int n,int parent)
{
int minchild=2*parent+1;
while(minchild<n)
{
//找较大的那个孩子
if(minchild+1<n&&a[minchild+1]>a[minchild])
{
minchild++;
}
if(a[parent]<a[minchild])
{
Swap(&a[parent],&a[minchild]);
parent=minchild;
minchild=parent*2+1;
}
else
{
break;
}
}
}
void HeapSort(int* a,int n)
{
//先建堆，升序——建大堆
for(int i=(n-1-1)/2;i>=0;i--)
{
AdjustDown(a,n,i);
}
//向下调整建堆
int i=1;//此时最大的数据已经在堆顶
while(i<n)
{
Swap(&a[0],&a[n-i]);
AdjustDown(a,n-i,0);
i++;
}
}
- 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
堆排序特性总结：
1.堆排序使用堆来选数，效率较高。
2.时间复杂度：O(N*logN)。
3.空间复杂度：O(1)。
4.稳定性：不稳定。
2.5冒泡排序
冒泡排序是一种交换排序，冒泡排序是从第一个元素开始，相邻的两个数俩俩比较，若后面一个数大于前一个数则交换，一直到把每趟的最大元素都排在末尾，所以冒泡排序是比较函数的一种。根据动图来观察，冒泡排序算法跟直接选择排序有点像，排好的元素，相对的位置之间就不再变动了。
void bubble_Sort(int* a, int n)
{
int i = 0;
int j = 0;
int flag = 0;
for (i = 0; i < n - 1; i++)//趟数
{
flag = 0;
for (j = 0; j < n - 1 - i; j++)//相邻元素之间的比较次数
{
if (a[j + 1] < a[j])
{
Swap(&a[j], &a[j + 1]);
flag = 1;
}
}
if (flag == 0)
{
break;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
冒泡排序法特性总结：
1.冒泡排序法是一种常见的排序算法。
2.最坏时间复杂度：O(N^2)，最好时间复杂度：O(N)。
3.空间复杂度:O(1)。
4.稳定性：稳定。
2.6快速排序
快速排序是公认的排序之王，快速排序是Hoare在1962年提出的一种二叉树结构的排序算法，他是一种交换排序，基本思想为:
任取待排序元素中的某元素作为基准值key，按照该基准值将带排序序列分为两个子序列，左边子序列的值都小于基准值，右边则都大于基准值，然后左右序列重复该过程（递归），直到所有元素都排列在相遇的位置上为止。
关于如何按照基准值将待排序序列分为两个子序列，常见的三种方式是：
1.Hoare版本
2.挖坑法
3.前后指针法
Hoare版本
方法：
我们先写出单趟排序PartSort(int* a,int left,int right)；因为是递归式的二叉树结构。
1.先选出一个key，一般是最左边或者最右边的。
2.定义left和right，left向右遍历序列，right向左遍历序列（如果定义最左边的那个元素为key,那么right先走，若定义最右边的那个元素为key，则left先走）。
3.在走的过程中，若R遇到小于key的数则停下，到L开始走，直到L遇到比key大的数时，L也停下，将下标为left，right的数据交换，直到L与R相撞，假设它们相遇的位置meeti，最后把a[meeti]和a[keyi]交换，返回L与R相遇的位置。
4.经过一次单趟排序，最终使得key左边的数据都小于key，右边的数据都大于key。
5.然后我们再将key的左序列和右序列再次进行这种单趟排序，每进行一次单趟排序就可以确定一个数据的排序位置，如此递归操作下去，直到最后左右序列只有一个数据或没有数据，则层层返回，此时序列就排好啦。
int PartSort1(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++;
}
if (left < right)
{
Swap(&a[left], &a[right]);
}
}
int meeti = left;
Swap(&a[meeti], &a[keyi]);
return meeti;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
int keyi = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
- 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
快速排序的两个优化
1.小区间优化：在二叉树的结构中，最后一层的结点个数是2^(h-1),占比约50%，倒数第二层的结点个数占比约25%，倒数第三次占比约12.5%，如果我们直接使用以上的方法就会导致递归调用的层数太多了，每一层的递归次数会以2倍的形式快速增长。那么递归得太深最容易导致的问题就是——栈溢出，所以我们要对其进行优化。优化方式：设置一个判断句，当一趟中数据量长度小于等于一定数值，如8，就不再进行快速排序，转而采用直接插入排序。
问：为什么不采用希尔排序？
答：希尔排序还要进行预排序，对于数据量大的时候采用希尔排序比较合适，数量较小时，还要进行预排序，不一定就效率高。
2.优化选key逻辑:快速排序的时间复杂度是O(NlogN),这是我们在理想情况下计算的结果。在理想情况下，我们每次进行完单趟排序后，key的左右序列的长度相同（如图2）。可是谁能保证你每次选取的key都是正中间的数呢？针对有序或接近有序的序列，如果我们依然选择最左边的作为基准值，那么我们的递归深度就为N（如图1），这种情况下，快速排序的时间复杂度退化为O(N^2)。且容易导致栈溢出。
所以我们优化key的思想是：三数取中，取序列的中间值作为key，再与a[left]交换，此时定义key时，依然为left，但实际上是原序列的中间值，这就确保了我们所选取的key，不会是最大值或最小值了，所以接下来的总体逻辑不变。
时间复杂度O(N*logN)。
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[left] < a[mid])
{
if (a[mid] < a[right])
{
return mid;
}
else if (a[right] < a[left])
{
return left;
}
else
{
return right;
}
}
else
{
if (a[mid] > a[right])
{
return mid;
}
else if (a[left] < a[right])
{
return left;
}
else
{
return right;
}
}
}
int PartSort1(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
while (left < right)
{
while (left < right&&a[right] >= a[keyi])
{
right--;
}
while (left < right&&a[left] <= a[keyi])
{
left++;
}
if (left < right)
{
Swap(&a[left], &a[right]);
}
}
int meeti = left;
Swap(&a[meeti], &a[keyi]);
return meeti;
}
void QuickSort(int* a, int begin, int end)
{
if (begin >= end)
{
return;
}
if (end - begin <= 8)
{
InsertSort(a + begin, end - begin + 1);
}
int keyi = PartSort1(a, begin, end);
QuickSort(a, begin, keyi - 1);
QuickSort(a, keyi + 1, end);
}
- 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
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
挖坑法
时间复杂度：O(N*logN)。
挖坑法的基本思想：
1.利用优化后的选key逻辑：三数取中， 选出key变量作为坑位，保存作为坑位的值（保存起来就可以覆盖了，就相当于坑位）。
2.定义一个L，一个R，L从左向右走，R从右向左走（若在最左边挖坑，则R先走；若在最右边挖坑，则L先走）。
3.假设我们定义最右边为坑位，在R走的过程中，若R遇到小于key的数，则将这个数抛入坑位，然后这个数原来的位置变成坑位，然后L向右走走，若遇到大于key的数则停下，将这个数抛入坑位，这个数的位置又形成新的坑位，如此循环下去，直到最终L与R相遇，最后再将key抛入最后形成的坑位。
4.经过一次单趟排序，也能使得key左边的数据都小于key，右边的数据都大于key。
5.然后也是跟Hoare法一样，key的左右子序列不断的进行单趟排序（递归），直到左右序列只有一个数据或者没有数据，便停止递归，层层返回。
int PartSort2(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[mid], &a[left]);
//1.保存坑位
int key = a[left];
int hole = left;
while (left < right)
{
//2.挖坑
while (left < right&&a[right] >= key)
{
right--;
}
a[hole] = a[right];
hole = right;
while (left < right&&a[left] <= key)
{
left++;
}
a[hole] = a[left];
hole = left;
}
//L与R相遇
a[hole] = key;
return hole;
}
- 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
前后指针法
时间复杂度：O(N*logN)。
前后指针法基本思想：
1.用三数取中法，选出一个key，最左边的或最右边的。
2.刚开始prev指向序列开头，cur指向prev+1的位置。
3.若cur指向的值比key小，则cur停下来，++prev，交换prev和cur位置上的数据，然后cur继续往后++，prev紧跟cur，但若cur指向的数据大于等于key，则cur继续++，但prev不动，如此规律进行下去，直到cur越界，跳出循环，最后将prev指向的数据和keyi指向的数据交换即可。
4.经过一次单趟排序，也能使得key左边的数据都小于key，右边的数据都大于key。
5.然后也是跟Hoare法一样，key的左右子序列不断的进行单趟排序（递归），直到左右序列只有一个数据或者没有数据，便停止递归，层层返回。
int PartSort3(int* a, int left, int right)
{
int mid = GetMidIndex(a, left, right);
Swap(&a[left], &a[mid]);
int keyi = left;
int prev = left;
int cur = prev + 1;
while (cur <= right)
{
if (a[cur] < a[keyi]&&++prev!=cur)
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
Swap(&a[keyi], &a[prev]);
return prev;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
非递归实现快速排序
基本思想：我们学过的递归改非递归的算法，如斐波那契数列呀，n的k次方等，它们都是利用while循环，或for循环实现的非递归，思想比较简单。那么我们进入正题， 要将一个递归实现的快速排序算法改为非递归时，一般需要先模拟一个栈出来，还要清楚递归调用函数栈帧时，调用的数据，或区间的先后。注意栈是后进先出的，所以我们就利用压栈，出栈这两个功能去模拟递归的思想。
//非递归实现快速排序算法
//注意栈是：后进先出
void QuickSort(int* a, int begin, int end)
{
ST st;
StackInit(&st);
//先压左数据，再压右数据
StackPush(&st, begin);
StackPush(&st, end);
while (!StackEmpty(&st))
{
//先取右数据（因为后压的右数据，所以栈顶元素此时是右数据）
int right = StackTop(&st);
StackPop(&st);
//再拿左数据
int left = StackTop(&st);
StackPop(&st);
//这也是终止“递归”的一种方式
/*if (left >= right)
{
continue;
}*/
int keyi = PartSort3(a, left, right);
//先压keyi的右区间，再压左区间
//这样才能符合先递归左区间，再递归右区间
//只剩下一个数据的数据就没必要压入了
if(keyi + 1 < right)
{
StackPush(&st, keyi + 1);
StackPush(&st, right);
}
if(keyi - 1>left)
{
StackPush(&st, left);
StackPush(&st, keyi-1);
}
}
StackDestroy(&st);
}
- 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
快速排序特性总结：
1.时间复杂度:O(NlogN)。（h=logN层，每层需要遍历每个元素）
2.空间复杂度：O(logN)。
3.稳定性：不稳定
2.7归并排序
递归实现
归并排序的基本思想：
类似一棵二叉树的后序遍历，先遍历左右子树，再遍历根。即先排序左右的子序列，最后才排序根部的序列。归并排序对序列的元素先进行逐层折半分组，直到递归到一个序列中只有一个元素的时候，才开始返回到上层函数，然后从最小的分组开始归并排序，因为我们额外开辟了N个空间，所以取小的尾插，和并层一个有序序列，逐层向上进行归并排序，最终所有的元素都是有序的。
void _MergeSort(int* a, int begin, int end, int* tmp)
{
//递归到最底层，序列中只有一个元素的时候返回
//返回到上一层，开始进行归并排序
if (begin >= end)
{
return;
}
int mid = begin + (end - begin) / 2;
// [begin, mid] [mid+1, end]
_MergeSort(a, begin, mid, tmp);
_MergeSort(a, mid+1, end, tmp);
//开始进行归并排序,取小的元素尾插到tmp的对应位置
// [begin, mid] [mid+1, end]
int begin1 = begin, end1 = mid;
int begin2 = mid + 1, end2 = end;
int i = begin;
while (begin1 <= end1 && begin2 <= end2)
{
if (a[begin1] <= a[begin2])
{
tmp[i++] = a[begin1++];
}
else
{
tmp[i++] = a[begin2++];
}
}
while (begin1 <= end1)
{
tmp[i++] = a[begin1++];
}
while (begin2 <= end2)
{
tmp[i++] = a[begin2++];
}
//将排序完的，拷贝到原数组的对应位置
//归并哪部分就拷贝哪部分
memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
//归并排序需要额外开辟n个空间,以空间换时间
//空间复杂度为O(N)
int* tmp = (int*)malloc(sizeof(int)*n);
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
//子函数实现归并排序
_MergeSort(a, 0, n - 1, tmp);
free(tmp);
tmp = NULL;
}
- 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
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
归并排序特性总结：
1.归并排序算法每次将序列折半分组，这个的时间复杂度就为O(logN),又因为每一层都要对两组序列进行遍历比较，从而完成一次归并排序，所以这里的时间复杂度为O(N),合起来，归并排序的时间复杂度就为O(NlogN)。
2.归并排序是以空间换取时间，需要开辟额外的空间，空间复杂度为O(N)。
3.稳定性：稳定。
非递归实现
//归并排序（子函数）
void _MergeSortNonR(int* a, int* tmp, int begin1, int end1, int begin2, int end2)
{
int j = begin1;
//将两段子区间进行归并，归并结果放在tmp中
int i = begin1;
while (begin1 <= end1&&begin2 <= end2)
{
//将较小的数据优先放入tmp
if (a[begin1] < a[begin2])
tmp[i++] = a[begin1++];
else
tmp[i++] = a[begin2++];
}
//当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面
while (begin1 <= end1)
tmp[i++] = a[begin1++];
while (begin2 <= end2)
tmp[i++] = a[begin2++];
//归并完后，拷贝回原数组
for (; j <= end2; j++)
a[j] = tmp[j];
}
//归并排序（主体函数）
void MergeSortNonR(int* a, int n)
{
int* tmp = (int*)malloc(sizeof(int)*n);//申请一个与待排序列大小相同的空间，用于辅助合并序列
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
int gap = 1;//需合并的子序列中元素的个数
while (gap < n)
{
int i = 0;
for (i = 0; i < n; i += 2 * gap)
{
int begin1 = i, end1 = i + gap - 1;
int begin2 = i + gap, end2 = i + 2 * gap - 1;
if (begin2 >= n)//最后一组的第二个小区间不存在或是第一个小区间不够gap个，此时不需要对该小组进行合并
break;
if (end2 >= n)//最后一组的第二个小区间不够gap个，则第二个小区间的后界变为数组的后界
end2 = n - 1;
_MergeSortNonR(a, tmp, begin1, end1, begin2, end2);//合并两个有序序列
}
gap = 2 * gap;//下一趟需合并的子序列中元素的个数翻倍
}
free(tmp);//释放空间
}
- 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
- 46
- 47
- 48
- 49
- 50
- 51
- 52
2.8外排序
首先，我们得清楚什么是内排序，什么是外排序。
内排序：数据量相对较少，可以存放到内存中进行排序。
外排序：数据量较大时，由于内存的空间比磁盘小很多，数据就只能存放到磁盘文件中。
上面介绍的算法都是在内存中进行的，那么当我们面对大量的数据时，我们可以采用归并排序。下面解析如何用归并排序实现外排序。
1.一开始，大量的数据存储在磁盘上的一个文件当中，我们将其分割成能储存进内存的大小，假设代码中的待排序的数据量是100个，那么我们每次从中读取10个数据到内存中，进行内排序，然后再将排序结果创建并写到第一个文件中，然后再继续读取接下来的10个数据，写到第二个文件中，最终会生成10个各自有序的小文件（1,2…10）
2.然后我们再对这10个小文件进行归并排序（利用文件的输入输出函数，从两个文件中各读取一个数据，然后进行比较，将较小的数据写入到一个新文件中去，然后再读取，再比较，再写入），最后就归并成了一个有序文件了。
//将file1文件和file2文件中的数据归并到mfile文件中
void _MergeFile(const char* file1, const char* file2, const char* mfile)
{
FILE* fout1 = fopen(file1, "r");//打开file1文件
if (fout1 == NULL)
{
printf("打开文件夹\n");
exit(-1);
}
FILE* fout2 = fopen(file2, "r");//打开file2文件
if (fout2 == NULL)
{
printf("打开文件夹失败\n");
exit(-1);
}
FILE* fin = fopen(mfile, "w");//打开mfile文件
if (fin == NULL)
{
printf("打开文件失败\n");
exit(-1);
}
int num1, num2;
int ret1 = fscanf(fout1, "%d\n", &num1);//读取file1文件中的数据
int ret2 = fscanf(fout2, "%d\n", &num2);//读取file2文件中的数据
while (ret1 != EOF && ret2 != EOF)
{
//将读取到的较小值写入到mfile文件中，继续从file1和file2中读取数据进行比较
if (num1 < num2)
{
fprintf(fin, "%d\n", num1);
ret1 = fscanf(fout1, "%d\n", &num1);//继续读取文件1的下一个数据
}
else
{
fprintf(fin, "%d\n", num2);
ret2 = fscanf(fout2, "%d\n", &num2);
}
}
//将file1文件中未读取完的数据写入文件mfile中
while (ret1 != EOF)
{
fprintf(fin, "%d\n", num1);
ret1 = fscanf(fout1, "%d\n", &num1);
}
while (ret2 != EOF)
{
fprintf(fin, "%d\n", num2);
ret2 = fscanf(fout2, "%d\n", &num2);
}
fclose(fout1);
fclose(fout2);
fclose(fin);
}
//将文件中的数据进行排序
void MergeSortFile(const char* file)//文件名不允许被修改
{
FILE* fout = fopen(file, "r");//以读的形式打开文件名为"Sort.txt"的文件
if (fout == NULL)
{
printf("打开文件失败\n");
exit(-1);
}
//假设文件中待排序的数据有100个，我们将其分成10份，将每份读入内存中，
//然后进行排序，内存排序之后再写入小文件中
int n = 10;//一次读取10个数据进行内排序
int a[10];//读取的数据放到数组中，准备进行内排序
int i = 0;
int num = 0;//读取的每个数据
char subfile[20];//文件名
int filei = 1;//存储第i组内排序后的数据的文件名
memset(a, 0, sizeof(int)*n);//将数组a的空间置0
while (fscanf(fout, "%d\n", &num) != EOF)
{
if (i < n - 1)//先读取前9个数据
{
a[i++] = num;
}
else
{
//读取第10个数据
a[i] = num;
QuickSort(a, 0, n - 1);//将这10个数据进行快速排序
sprintf(subfile, "%d",filei++);//将储存第i组内排序后的数据的文件的文件名
//例如，第一个内排序完的小文件，就被命名为1，问：subfile是一个字符数组，和文件名有何关系？
FILE* fin = fopen(subfile, "w");//创建并打开文件名为subfile的文件
//即，第一次循环，我们打开的是文件名为1的文件，这个文件里即将要存的是第一批内排序完的10个数据
if (fin == NULL)
{
printf("打开文件失败\n");
exit(-1);
}
//将内排序好的10个数据写入到subfile文件中
for (int i = 0; i < n; i++)
{
fprintf(fin, "%d\n", a[i]);
}
//完成内排序的一个小文件
fclose(fin);
i = 0;
memset(a, 0, sizeof(int)*n);//将数组内存置0，准备再次读取10个数据进行内排序
}
}
//归并文件，实现整体有序
char mfile[100] = "12";//归并后文件的文件名
char file1[100] = "1";//待归并的第一个文件的文件名
char file2[100] = "2";//待归并的第二个文件的文件名
for (int i = 2; i < n; i++)
{
//将file1文件和file2文件中的数据归并到mfile文件中
_MergeFile(file1, file2, mfile);
strcpy(file1, mfile);//下一次待归并的文件file1，就是上一次归并好的文件
//更新文件名
sprintf(file2, "%d", i + 1);//i为3，就是下一次待归并的第二个文件
sprintf(mfile, "%s%d", mfile, i + 1);//下一次归并完的文件名为"123"，第一次归并的文件名为"12"
}
fclose(fout);
}
//主函数
int main()
{
MergeSortFile("Sort.txt");//Sort.txt是待排序文件的文件名，传过去的是：字符串首元素的地址，将文件名传给函数
return 0;
}
- 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
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
2.9计数排序
计数排序，又叫非比较排序，又称为鸽巢原理，是对哈希直接定址法的变形应用。它是通过统计数组中元素出现的次数，再通过统计结果将序列回收到原来的序列中。基本思想如图：
上述的方法，为绝对映射。那么当数据量较大时，如1010 1016 1010 1018 3000这样的数据进行排序，难道我们要额外开辟3031个整型空间吗？这样的话，空间的利用率就不高了。所以若是使用计数排序，我们应该使用相对映射，简单来说，就是数组中的最小值就对应count数组中的0下标，最大值对应count数组最后一个下标。这样对于这个数据，我们就只需要开辟3031-1010+1个空间了。
注意：计数排序只适用于数据范围较集中的序列进行排序，如果待排序序列较分散，则会导致空间浪费，并且计数排序只适用于整型排序。
//计数排序
void CountSort(int* a, int n)
{
int min = a[0];//记录数组中的最小值
int max = a[0];//记录数组中的最大值
for (int i = 0; i < n; i++)
{
if (a[i] < min)
min = a[i];
if (a[i] > max)
max = a[i];
}
int range = max - min + 1;//min和max之间的自然数个数（包括min和max本身）
int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间，并将内存空间置0
if (count == NULL)
{
printf("malloc fail\n");
exit(-1);
}
//统计相同元素出现次数（相对映射）
for (int i = 0; i < n; i++)
{
count[a[i] - min]++;
}
int i = 0;
//根据统计结果将序列回收到原来的序列中
for (int j = 0; j < range; j++)
{
while (count[j]--)
{
a[i++] = j + min;
}
}
free(count);//释放空间
}
- 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
计数排序特性总结：
1.时间复杂度：O(N+range)。
2.空间复杂度：O(range)。
3.稳定性：稳定
3.排序算法时间空间复杂度即稳定性总结
