数据结构——排序（提高篇）
前言
与查找一样，写一篇对于排序的总结，主要参考《大话数据结构》
关于查找提高篇——链接：https://blog.csdn.net/weixin_42513339/article/details/88980795
目录
1.排序相关概念
1.1排序的稳定性
这个可以举例说明，就是如果排序前，a1,a2,a3（其中a1 = 20，a2 = 20，a3 = 15） , 排序完成后输出为 a3，a2，a1，这里a1和a2的顺序本来是正确的，但是经过一次排序算法，使得正确的顺序发生了变化，那么这个算法就是不稳定的。
1.2内排序和外排序
内排序：在整个排序过程中，待排序的所有记录全部放置于内存中。
外排序：由于记录个数太多，不能同时放置在内存中，整个排序过程需要内外存多次交换数据才能进行。
这里主要讲内排序。
2.冒泡排序（Bubble Sort）
时间复杂度：O(N^2)
一种交换排序，基本思想：两两比较相邻记录的关键字，如果反序则交换，直到没有反序记录为止。
思路易理解，代码也不难。如下：（交换函数和main函数之后省略）
#include <iostream>
using namespace std;
void mySwap(int * a,int *b)//无参交换
{
if(a == b)
return;//防止a，b指向同一个地址；否则结果会错误。
*a ^= *b;
*b ^= *a;
*a ^= *b;
}
void BubbleSort(int *arr,int N)
{
for(int i = 0;i<N-1;i++)
{
for(int j = 0;j<N-1-i;j++)
{
if(arr[j]>arr[j+1])
{
arr[j] ^= arr[j+1];
arr[j+1] ^= arr[j];
arr[j] ^= arr[j+1];
}
}
}
}
int main()
{
int arr[] = {2,4,6,8,10,1,3,5,7,9};
int N = sizeof(arr)/sizeof(arr[0]);
BubbleSort(arr,N);
for(int i = 0;i<N;i++)
{
cout<<arr[i]<<" ";
}
return 0;
}
冒泡改进版
时间复杂度：O(N^2)
实际上，如果我们在对整个序列进行排序的时候，已经有序的时候，就不需要在进行排序了，而判断有序的标准就是 是否有过交换，若无交换元素，则肯定是有序的。所以直接加个判定标志位就可以。代码如下：
void BubbleSort2(int *arr,int N)
{
bool flag;
for(int i = 0;i<N-1;i++)
{
flag = true;
for(int j = 0;j<N-1-i;j++)
{
if(arr[j]>arr[j+1])
{
flag = false;
mySwap(&arr[j],&arr[j+1])
}
}
if(flag)
break;
}
}
3.简单选择排序
时间复杂度：依然为O(N^2)，但选择排序还是优于冒泡，因为换的次数，一次外重循环只换一次位置。
思路：通过n-i次关键词比较，从n-i+1个记录中选出关键词最小的记录，并和第i个记录交换。
实际上通俗来讲，就是第一个数字先跟后面所有数字比，找到最小的，然后再交换第一个数字和最小数字的位置；然后在用第二个数字跟后面所有数字比，以此类推。
思路不难，代码也较简单，如下：（这里我存下最小的位置，最后才交换，否则要一直换）
void SelectSort(int * arr,int N)
{
for(int i = 0;i<N-1;i++)
{
int min = i;
for(int j = i + 1;j<N;j++)
{
if(arr[min]>arr[j])
{
min = j;
}
}
if(min != i)
{
mySwap(&arr[j],&arr[j+1]);
}
}
}
4.直接插入排序
时间复杂度：依然为O(N^2)，但选择排序还是优于冒泡和选择。（这里优于是依据比较次数和移动次数，详情可以搜索插入的计算方法）
直接插入排序（Straight Insertion Sort）思路：将一个记录插入到已经排序好序的有序表中，从而得到一个新的、记录数增1的有序表。
理解：相当于打扑克，拿牌的时候，拿到一张就会插入到合适的位置，这样拿完牌，手上的牌就是有序的。换成数组的话，下图表示的比较清晰
理解难度不大，代码实现简单，代码里需要注意的一点就是，插入后，插入的位置后面的数都要往后移动一位，可以暂时保存插入数，然后移动后再放入。代码如下：
void InsertSort(int *arr,int N)
{
int m,j;
for(int i = 1; i<N;i++)
{
m = arr[i];
for(j = i; j > 0&& m<arr[j-1] ;j--)
{
arr[j] = arr[j-1];
}
arr[j] = m;
}
}
5.希尔排序
时间复杂度：约等于O(N^1.3)，由科学研究证明，但是不稳定。
本质是插入排序的改进版，进行分组排序。
举例：若数组有10个数。
1.先10/2=5，arr[10-1]和arr[5-1]进行插入排序，arr[9-1]和arr[4-1]进行插入排序，以此类推。（分成五个数组插入排序）
2.排完后，然后 5/2 = 2， arr[10-1]、arr[8-1]、arr[6-1]、arr[4-1]、arr[2-1]进行插入排序，对arr[9-1]、arr[7-1]、arr[5-1]、arr[3-1]、arr[1-1]进行插入排序。（分成两个数组插入排序）
3.最后2/2=1，再次进行整体的插入排序。最后得出有序数列。
PS：思路实际上不难，就是下标可能写代码稍微麻烦点。代码如下：
void ShellSort(int * arr,int N)
{
int dis = N/2, m,j;
while(dis>=1)
{
for(int i = dis;i<N; i++)
{
m =arr[i];
for(j = i;j-dis>=0 && arr[j-dis] > m;j = j- dis)
{
arr[j] = arr[j-dis];
}
arr[j] = m;
}
dis /= 2;
}
}
6.堆排序
时间复杂度：O(N*logN)，性能好于冒泡选择和插入；但不稳定，不适合与初始排序序列个数较少的情况。
堆排序是对选择排序的一种改进，首先需要介绍下堆这种数据结构。
堆的概念：堆是具有如下性质的完全二叉树（具有完全二叉树的性质）：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
大顶堆、小顶堆如下图：
对于堆排序的步骤，举例：
- 需要先输入完全二叉树，这一步，一般给定的数组的话，就可以直接生成一个完全二叉树了。假设输入arr = {20,40,60,10,30,50};
那么生成的完全二叉树就是如下：（这里的顺序标号就是数组的顺序） - 对于这个完全二叉树进行堆调整，变成大顶堆（小顶堆也是可以的）。堆调整的顺序是从下往上，从左往右。可以从h-1的高度的结点开始调整，这里的调整顺序为，2-1-0，调整完如下图（这里只有0号位小于2号位而不符合，这里我们也可以看出来，虽然只对于0号位堆调整，但是还是需要遍历检查到根部，都满足才可以）；
这里有个规律就是如果输入n个节点，直接从 n/2 号位开始调整，n/2实际上就是最后一个节点的父节点，调整值0号位。
PS：这里的父节点是可以利用顺序位置找到的，如含有元素1的位置是3号位，它的父节点就是(3-1)/2 =2；右节点的父节点就是(4-2)/2=2；所以通用公式就是若该节点是 i 号位，那么它的左子树为 2i+1 号位，它的右子树就是 2i+2 号位。
- 最后进行排序，首先，将大顶堆顶点（即堆中最大值）与最后一个位置进行交换，然后砍断最大值和堆的关系，那么剩下的数已经不满足堆的性质了，所以需要再次根节点进行堆调整（这里只需要一次从根节点出发的堆调整），然后再把顶点与最后一个位置进行交换，。。以此类推。
动画解释的话，可以参考，https://www.cs.usfca.edu/~galles/visualization/HeapSort.html
代码如下：
void HeapAdjust(int * tree,int N, int i)//堆调整 (数组，元素个数，堆调整的位置)
{
if( i >= N)
return;
int c1 = 2*i+1;//两个子字节
int c2 = 2*i+2;
int max = i;//假设i为最大值
if(c1<N && tree[c1]>tree[max])
{
max = c1;
}
if(c2<N && tree[c2]>tree[max])
{
max = c2;
}
if(max != i)
{
mySwap(&tree[max],&tree[i]);
HeapAdjust(tree, N, max);//在换位后，需要调整剩余子节点的位置。
}
}
void BuildHeap(int *tree,int N)//从最后一个节点的父节点到0，进行堆调整
{
int lastNode = N-1;
for(int i = (lastNode-1)/2;i>=0;i--)
HeapAdjust(tree,N,i);
}
void HeadSort(int *tree,int N)
{
BuildHeap(tree,N);
for(int i = N-1;i>=0;i--)
{
mySwap(&tree[0],&tree[i]);
HeapAdjust(tree,i,0);
}
}
7.归并排序
时间复杂度：O(N*logN)，比较占内存，效率高且稳定。
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
就是拆分，然后再进行排序，合并再排序，最后生成有序。
//(a数组包含2个有序数组)-1个数组
void mergeArr2(int * a ,int * c, int start, int mid, int end)
{
int i = start, j = mid+1, k = start;
while(i != mid+1 && j != end+1)
{
if(a[i] < a[j])
c[k++] = a[i++];
else
c[k++] = a[j++];
}
if(i == mid +1)
while(j != end+1 )
c[k++] = a[j++];
else
while(i != mid +1)
c[k++] = a[i++];
while(start<=end)
{
a[start] = c[start];
start++;
}
}
//归并排序
void mergeSort(int*arr, int *tmp,int start, int end)
{
if(start<end)
{
int mid = (start +end)/2;
mergeSort(arr,tmp,start,mid);
mergeSort(arr,tmp,mid+1,end);
mergeArr2(arr,tmp,start,mid,end);
}
}
8.快速排序
时间复杂度：O(N*logN)，极快，移动数据少；但不稳定，而且有递归。
冒泡法的进化版。
思路：在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在左边，大于此数的放在右边，再对数组两边递归调用快速排序，重复这个过程。
void QuickSort(int * arr,int left,int right)
{
if(left < right)
{
int pivot = arr[left],l = left,h = right;
while(l<h)
{
while(l<h && pivot <=arr[h])
h--;
arr[l] = arr[h];
while(l<h && pivot >=arr[l])
l++;
arr[h]= arr[l];
}
arr[h] = pivot;
QuickSort(arr,left,h-1);
QuickSort(arr,h+1,right);
}
}
相关博客（包括动态演示）：https://blog.csdn.net/yushiyi6453/article/details/76407640#commentBox