关于我的数据结构与算法——初阶第二篇（排序）

（叠甲：如有侵权请联系，内容都是自己学习的总结，一定不全面，仅当互相交流（轻点骂）我也只是站在巨人肩膀上的一个小卡拉米，已老实，求放过）。

排序的概念及其运用

排序的概率

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

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

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

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

常见的排序算法

常见排序算法的实现

插入排序

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

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

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"int main()
{int a[5] = { 44,8,63,45,10};//插入排序InsertSort(a, 5);PrintArray(a, 5);return 0;
}

Sort.c

void InsertSort(int* a, int n)
{assert(a);for (int i = 0; i < n-1; i++){int end = i;int tem = a[end + 1];while (end>=0){if (tem < a[end]){a[end + 1] = a[end];end--;}else{break;}}a[end + 1] = tem;}
}//打印
void PrintArray(int* a, int n)
{assert(a);for (int i = 0; i < n; i++){printf("%d ", a[i]);}printf("\n");
}

Sort.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//插入排序
void InsertSort(int* a, int n);//希尔排序(缩小增量排序)
void ShellSort(int* a, int n);//选择排序
void SelectSort(int* a, int n);//堆排序
void AdjustDown(int* a, int n, int root);
void HeapSort(int* a, int n);//冒泡排序
void BubbleSort(int* a, int n);int GetMidIndex(int* a, int left, int right);//快速排序Hoare版本
int ParSort1(int* a, int left, int right);//快速排序挖坑法版本
int ParSort2(int* a, int left, int right);//快速排序前后指针版本
int ParSort3(int* a, int left, int right);void QuickSort(int* a, int left, int right);//快速排序非递归实现
void QuickSort(int* a, int left, int right);//归并排序递归实现
void MergeSort(int* a, int n);//归并排序非递归实现
void MergeSort(int* a, int n);//计数排序
void CountSort(int* a, int n);//打印
void PrintArray(int* a, int n);//交换
void Swap(int* pa, int* pb);

直接插入排序的特性总结：

1）元素集合越接近有序，直接插入排序算法的时间效率越高；

2）时间复杂度：O（ $N^{2}$ ）;

3）空间复杂度：O（1），它是一种稳定的排序算法；

4)稳定性：稳定

希尔排序（缩小增量排序）

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"int main()
{int a[5] = { 44,8,63,45,10};//希尔排序ShellSort(a, 5);PrintArray(a, 5);return 0;
}

Sort.c

//希尔排序(缩小增量排序)
void ShellSort(int* a, int n)
{assert(a);int gap = 0;gap = n;while (gap >1){gap = gap / 3 + 1;for (int i = 0; i < n - gap; i += gap){int end = i;int tem = a[end + gap];while (end >= 0){if (tem < a[end]){a[end + gap] = a[end];end--;}else{break;}}a[end + gap] = tem;}}
}

希尔排序又称缩小增量法，希尔排序的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为记录在同一组内，并对一组内的记录进行排序，然后，取，重复上述分组和排序的工作，当达到= 1时，所有记录在统一组内排好序。

希尔排序的特性总结：

1）希尔排序是对直接插入排序的优化；

2）当 gap>1时都是预排序，目的是让数组更接近有序，当gap ==1 时，数组已经接近有序了，这样就很快，这样整体而言，可以达到优化的效果；

3）希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在哼多树中给出的希尔排序的时间复杂度都不固定；根据大量实验可以暂时的按照O( $N^{1.25}$ )到

O( $1.6*N^{1.25}$ )来算。

4）稳定性：不稳定

选择排序

基本思想

每次从待排序的数据元素中选出最小（或最大）的元素，存放在序列的起始位置，直到全部排序的数据元素排完。

直接选择排序：

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"int main()
{int a[5] = { 44,8,63,45,10};//选择排序SelectSort(a, 5);PrintArray(a, 5);return 0;
}

Sort.c

//交换
void Swap(int* pa, int* pb)
{assert(pa);assert(pb);int tem = *pa;*pa = *pb;*pb = tem;
}//选择排序
void SelectSort(int* a, int n)
{assert(a);int left = 0;int right = n - 1;while (left <= right){int mini = left;int maxs = right;for (int i = 0; i <= right; i++){if (a[i] < a[mini]){mini = i;}if (a[i] > a[right]){maxs = i;}}Swap(&a[left], &a[mini]);if (maxs == left){maxs = mini;}Swap(&a[right], &a[maxs]);left++;right--;}
}

1）在元素集合array[i]--array[n-1])中选择关键码最大（小）的数据元素；

2）若它不是这组元素中的最后一个（第一个）元素，则将它与这组元素中的最后一个（第一个）元素交换；

3）在剩余的arrqy[i]--array[n-2] (arry[i+1]--array[n-1])集合中，重复上述步骤，直集合剩余1个元素；

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

1）直接选择排序思考非常好理解，但是效率不是很好，实际中很少使用；

2）时间复杂度：O（ $N^{2}$ ）；

3）空间复杂度：O(1)

4)稳定性：不稳定

堆排序

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"int main()
{int a[5] = { 44,8,63,45,10};//堆排序HeapSort(a,5);PrintArray(a, 5);return 0;
}

Sort.c

//交换
void Swap(int* pa, int* pb)
{assert(pa);assert(pb);int tem = *pa;*pa = *pb;*pb = tem;
}//堆排序(建大堆)
void AdjustUp(int* a, int n)
{int child = n - 1;int parent = (child-1) / 2;while (child>0){if (a[child] > a[parent]){Swap(&a[child] ,&a[parent]);child = parent;parent = (child-1) / 2;}else{break;}}
}//堆排序(向下调整)
void AdjustDown(int* a, int n)
{assert(a);int parent = 0;int child = 2 * parent + 1;while (child<n){if (child+1<n && a[child + 1] >a[child]){child++;}if (a[child] > a[parent]){Swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}//堆排序(排序)
void HeapSort(int* a, int n)
{for (int i = 0; i <= n; i++){AdjustUp(a, i);}assert(a);while (n>0){Swap(&a[0], &a[n-1]);n--;AdjustDown(a, n);}}

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

堆排序的特性总结：

1）堆排序使用堆来选数，效率就高很多

2）时间复杂度：O（N* $log^{N}$ ）

3)空间复杂度：O（1）

4）稳定性：不稳定

交换排序

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

冒泡排序

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Sort.h"int main()
{int a[5] = { 44,8,63,45,10};//冒泡排序BubbleSort(a, 5);PrintArray(a, 5);return 0;
}

Sort.c

//冒泡排序
void BubbleSort(int* a, int n)
{for (int i = 0; i < n; i++){for (int j = 1; j < n - i; j++){if (a[j - 1] > a[j]){int tem = a[j];a[j] = a[j - 1];a[j - 1] = tem;}}}
}

冒泡排序的特性总结

1）冒泡排序是一种非常容易理解的排序

2）时间复杂度：O( $N^{2}$ )

3)空间复杂度：O(1)

4)稳定性：稳定

快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素为基准值，按照该排序码将排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序递归实现的主框架，发现与二叉树前序遍历很相似，同学们在写递归框架时，可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

将区间按照基准值划分为左右两半部分的常见方式有：

1)hoare版本

Sort.h

//交换
void Swap(int* pa, int* pb)
{assert(pa);assert(pb);int tem = *pa;*pa = *pb;*pb = tem;
}//快速排序Hoare版本
int ParSort1(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[right]);return left;
}

2)挖坑法

Sort.c

//快速排序挖坑法版本
int ParSort2(int* a, int left, int right)
{int keyi = a[left];int pia = left;while (left < right){while ((left < right) && (a[right] >= keyi)){right--;}a[pia] = a[right];pia = right;while ((left < right) && (a[left] <= keyi)){left++;}a[pia] = a[left];pia = left;}a[pia] = keyi;return pia;
}

3)前后指针法

Sort.c

//交换
void Swap(int* pa, int* pb)
{assert(pa);assert(pb);int tem = *pa;*pa = *pb;*pb = tem;
}//快速排序前后指针版本
int ParSort3(int* a, int left, int right)
{int prev = left;int cur = prev+1;int keyi = left;while (cur <= right){if (a[cur] <= a[keyi] && a[++prev] != a[cur]){Swap(&a[prev], &a[cur]);}cur++;}Swap(&a[prev], &a[keyi]);return prev;
}

快速排序优化

1）三数取中法选key

Sort.c

//快速排序找中间值
int GetMidIndex(int* a, int left, int right)
{int mid = left + (right / 2);if (mid >= right){mid = left;}if (a[mid] > a[left]){if (a[mid] < a[right]){return mid;}else if (a[right] > a[left]){return right;}else{return left;}}else{if (a[mid] < a[right]){return mid;}else{return right;}}
}void QuickSort1(int* a, int left, int right)
{if (left >= right){return;}int mid = GetMidIndex(a, left, right);ParSort1(a, left, right);QuickSort1(a, left, mid);QuickSort1(a, mid+1, right);}

2）递归到小的子区间时，可以考虑使用插入排序

快速排序非递归

快速排序的特性总结：

1）快速排序整体的综合性能和使用场景都是比较好的；

2）时间复杂度：O(N* $log^{N}$ )

3)空间复杂度：O( $log^{N}$ )

4)稳定性：不稳定

归并排序

基本思想：

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

归并排序的特性总结：

1）归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题；

2）时间复杂度：O(N* $log^{N}$ )

3)空间复杂度：O(N)

4)稳定性：稳定