排序
排序：重新排列表中的元素，使表中元素满足按关键字有序的过程。
排序算法的评价指标：时间复杂度、空间复杂度、稳定性。
算法的稳定性：关键字相同的元素在使用某一排序算法之后相对位置不变，则称这个排序算法是稳定的，否则称其为不稳定的。
稳定的排序算法不一定比不稳定的排序算法要好。
排序算法的分类：
内部排序 ： 排序期间元素都在内存中——关注如何使时间、空间复杂度更低。
外部排序 ：排序期间元素无法全部同时存在内存中，必须在排序的过程中根据要求，不断地在内、外存之间移动——关注如何使时间、空间复杂度更低，如何使读/写磁盘次数更少。
各自排序算法演示过程参考：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
1. 插?排序
（稳定）1.1 直接插入排序【适用于顺序存储和链式存储的线性表】
基本操作就是：将
有序数据后的第一个元素插入到已经排好序的有序数据中从而得到一个新的、个数加一的有序数据
算法解释：（从小到大）
算法三个步骤：
先保留要插入的数字
往后移
插入元素
// 对A[]数组中共n个元素进行插入排序
void InsertSort(int A[],int n){
int i,j,temp;
for(i=1; i<n; i++)
{
//如果是A[i-1] <= A[i]，直接就是有序了，就不用下面的步骤【也是算法稳定的原因】
if(A[i]<A[i-1])
{
temp=A[i]; //保留要插入的数字
for(j=i-1; j>=0 && A[j]>temp; --j)
A[j+1]=A[j]; //所有大于temp的元素都向后挪
A[j+1]=temp;//插入元素
}
}
}
用算法再带入这个例子，进行加深理解
带哨兵：
补充：对链表L进行插入排序
void InsertSort(LinkList &L){
LNode *p=L->next, *pre;
LNode *r=p->next;
p->next=NULL;
p=r;
while(p!=NULL){
r=p->next;
pre=L;
while(pre->next!=NULL && pre->next->data<p->data)
pre=pre->next;
p->next=pre->next;
pre->next=p;
p=r;
}
}
时间、空间复杂度
最好情况： 共n-1趟处理，每?趟只需要对?关键字1次，不?移动元素
最好时间复杂度—— O(n)
最坏情况： 【感觉第1趟：对?关键字2次，移动元素1次？ 】
第1趟：对?关键字2次，移动元素3次
第2趟：对?关键字3次，移动元素4次
…
第 i 趟：对?关键字 i+1次，移动元素 i+2 次
最坏时间复杂度——O(n2)
（稳定）1.2 折半插入排序【先?折半查找找到应该插?的位置，再移动元素】
过程：
//对A[]数组中共n个元素进行折半插入排序
void InsertSort(int A[], int n)
{
int i,j,low,high,mid;
for(i=2; i<=n; i++)
{
A[0]=A[i]; //存到A[0]
//-----------------折半查找【代码一样】---------------------------
low=1; high=i-1;
while(low<=high){
mid=(low+high)/2;
if(A[mid]>A[0])
high=mid-1;
else
low=mid+1;
}
//--------------------------------------------
for(j=i-1; j>high+1; --j)//右移
A[j+1]=A[j];
A[high+1]=A[0];//插入
}
}
时间、空间复杂度
空间复杂度：O(1)
【右移】的次数变少了，但是关键字对?的次数依然是O(n2) 数量级，整体来看时间复杂度依然是O(n2)
（不稳定）1.3 希尔排序【多次直接插入排序】
是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。
算法思想
- 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
- 随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
图解：
代码实现：
//从小到大
void shellSort(int* arr, int n)
{
int gap, i, j, temp;
//小组的个数，小组的个数从n/2个，变成n/4，再变变变，越来越少，直到变成一个
for (gap = n / 2; gap >= 1; gap = gap / 2)
{
//**********************************直接插入排序（只是步长改变）**************************************************
for (i = gap; i < n; i++) //因为这个小组的元素使隔了gap个，所以排的时候也要隔gap个
{
if (arr[i] < arr[i - gap])
{
temp = arr[i];
//后移
for (j = i - gap; j >= 0 && temp < arr[j]; j -= gap)
arr[j + gap] = arr[j];
arr[j + gap] = temp;//插入进去
}
}
//************************************************************************************
}
}
时间、空间复杂度
空间复杂度：O(1)
时间复杂度：和步长的大小有关，?前?法?数学?段证明确切的时间复杂度 ，最坏时间复杂度为 O(n2)，当n在某个范围内时，可达O(n1.3)
稳定性：不稳定！
适?性：仅适?于顺序表，不适?于链表
2. 交换排序
2.1 (稳定）冒泡排序
英文:
bubble sort????(bubble 动和名词 起泡，冒泡)
从头到尾相邻的两个元素进行比较 大小顺序不满足就交换两个元素位置每一轮比较会让一个最大数字沉底或者一个最小数字上浮
这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。
实现代码：
//从小到大：
void bubble_sort(int arr[], int len)//冒泡排序int*arr
{
int temp;
for (int i = 0; i < len - 1; ++i)//循环比较次数
{
//for (int j = 0; j < len - 1; ++j)//从头到尾比较一轮
for (int j = 0; j < len - 1 - i; ++j)//相对于上面的一个优化
{
if (arr[j] > arr[j + 1])//发现两个位置不对的元素//j+1<len
{
//交换两个元素位置
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
优化代码【当初始序列有序时，外层for会执行“【1】”，从而外层for只执行了一次】：
//从小到大：
void bubble_sort(int arr[], int len)
{
int temp;
bool flag;
for (int i = 0; i < len - 1; ++i)
{
//表示本趟冒泡是否发生交换的标志
flag=false;
for (int j = 0; j < len - 1 - i; ++j)
{
if (arr[j] > arr[j + 1])//稳定的原因
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
//有发生交换
flag=true;
}
}//for
//本趟遍历后没有发生交换，说明表已经有序
if(flag==false)return;【1】
}//for
}
时间、空间复杂度
适用性：冒泡排序可以用于顺序表、链表
2.2 (不稳定)快速排序【所有内部排序算法中，平均性能最优的排序算法】
算法思想：
在待排序表L[1…n]中任取?个元素pivot作为枢轴（或基准，通常取?元素），
通过?趟排序将待排序表划分为独?的两部分L[1…k-1] 和 L[k+1…n]，
使得L[1…k-1]中的所有元素?于pivot，L[k+1…n]中的所有元素?于等于pivot，
再令pivot放在位置L(k)上，这个过程称为?次“划分”。
然后分别递归地对两个?表重复上述过程，直?每部分内只有?个元素或空为?，即所有元素放在了其最终位置上。
划分的过程：
初始状态：取首元素为pivot，定义low，high指针
首元素为49
high指针指向的数据小于49，就放在low指向的位置
low指针指向的数据大于49，就放在high指向的位置
// 用第一个元素将数组A[]划分为两个部分
int Partition(int A[], int low, int high){
//取首元素为pivot
int pivot = A[low];
while(low<high)
{
//先是high开始向左移动
while(low<high && A[high]>=pivot)
--high;
A[low] = A[high];
//随后low向右移动
while(low<high && A[low]<=pivot)
++low;
A[high] = A[low];
}
//low=high的位置，即pivot放在的位置
A[low] = pivot;
return low;
}
// 对A[]数组的low到high进行快速排序
void QuickSort(int A[], int low, int high){
if(low<high){
int pivotpos = Partition(A, low, high); //划分
QuickSort(A, low, pivotpos - 1);
QuickSort(A, pivotpos + 1, high);
}
}
时间、空间复杂度
把n个元素组织成?叉树，?叉树的层数就是递归调?的层数
n个结点的?叉树： 最??度 = ?log2n? + 1，最??度 = n
时间复杂度=O(n*递归层数)
最好时间复杂度=O(n * log2n)
最坏时间复杂度=O(n2)
平均时间复杂度=O(n * log2n)，是所有内部排序算法中平均性能最优的排序算法
空间复杂度=O(递归层数)
最好空间复杂度=O(log2n)
最坏空间复杂度=O(n)
最坏的情况
?较好的情况
不稳定的原因：
3.选择排序
选择排序：每?趟在待排序元素中，选取关键字最?（或最?）的元素加?有序?序列
3.1 （不稳定）简单选择排序
算法思路：每一趟在待排序元素中，选取关键字最小的元素与待排序元素中的第一个元素交换位置
// 交换a和b的值
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
// 对A[]数组共n个元素进行选择排序
void SelectSort(int A[], int n)
{
//一共进行n-1趟，i指向待排序序列中第一个元素
for(int i=0; i<n-1; i++)
{
int min = i;
for(int j=i+1; j<n; j++){ //在A[i...n-1]中选择最小的元素
if(A[j]<A[min])
min = j;
}
if(min!=i)
swap(A[i], A[min]);
}
}
补充：对链表进行简单选择排序
void selectSort(LinkList &L){
LNode *h=L,*p,*q,*r,*s;
L=NULL;
while(h!=NULL){
p=s=h; q=r=NULL;
while(p!=NULL){
if(p->data>s->data){
s=p; r=q;
}
q=p; p=p->next;
}
if(s==h)
h=h->next;
else
r->next=s->next;
s->next=L; L=s;
}
}
时间、空间复杂度
适用性：适用于顺序存储和链式存储的线性表。
3.2 （不稳定）堆排序
① 什么是堆、?根堆（?顶堆）、?根堆（?顶堆）？
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
即：
若满?：L(i) ≥ L(2i) 且 L(i) ≥ L(2i+1) （1 ≤ i ≤n/2）—— ?根堆（?顶堆）
若满?：L(i) ≤ L(2i) 且 L(i) ≤ L(2i+1) （1 ≤ i ≤n/2）—— ?根堆（?顶堆）
② 建??根堆：BuildMaxHeap(int A[], int len)、HeadAdjust(int A[], int k, int len)
思路：
把所有?终端结点都检查?遍，看是否满??根堆的要求，如果不满?，则进?调整
在顺序存储的完全?叉树中，?终端结点编号 i≤?n/2?，也就是检查 i=1 到 i=?n/2? 之间的所有结点
检查内容：是否满? 根 ≥ 左、右，若不满?，将当前结点与其更?的?个孩?互换
过程例子：
建??根堆（代码）：
// 对初始序列建立大根堆
void BuildMaxHeap(int A[], int len){
for(int i=len/2; i>0; i--) //从后往前调整所有非终端结点
HeadAdjust(A, i, len);
}
// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[], int k, int len){
A[0] = A[k];
for(int i=2*k; i<=len; i*=2){ //沿k较大的子结点向下调整
if(i<len && A[i]<A[i+1])
i++;
if(A[0] >= A[i])
break;
else{
A[k] = A[i]; //将A[i]调整至双亲结点上
k=i; //修改k值，以便继续向下筛选
}
}
A[k] = A[0]
}
③基于?根堆进?排序：HeapSort(int A[], int len)
选择排序：每?趟在待排序元素中，选取关键字最?（或最?）的元素加?有序?序列
堆排序：每?趟将堆顶元素加?有序?序列（即与待排序序列中的最后?个元素交换）
过程：
// 交换a和b的值
void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
// 对长为len的数组A[]进行堆排序
void HeapSort(int A[], int len){
//初始建立大根堆
BuildMaxHeap(A, len);
//n-1趟的交换和建堆过程
for(int i=len; i>1; i--)
{
swap(A[i], A[1]);
HeadAdjust(A,1,i-1);
}
}
时间、空间复杂度
建堆时间 O(n)，之后进行 n-1 次向下调整操作，每次调整时间复杂度为 O(log2n)；
故时间复杂度 = O(n) + O(n * log2n) = O(n* log2n)
空间复杂度 = O(1)
结论：堆排序是不稳定的
④ 补充：在堆中插?新元素
对于?根堆，新元素放到表尾，并与?节点对?，若新元素??节点更?，则将?者互换。
新元素就这样?路“上升”，直到?法继续上升为?
⑤ 补充：在堆中删除元素
被删除的元素?堆底元素替代，然后让该元素不断“下坠”，直到?法下坠为?
4. （稳定）归并排序
归并：把两个或多个已经有序的序列合并成?个
① 明白什么是“2路”归并？——就是“?合?”
多路归并：
② 一次“2路”归并的代码【Merge(int A[], int low, int mid, int high)】
B[ i ] = B[ j ]时，优先用B[ i ]，故算法稳定
③递归进行分治思想【MergeSort(int A[], int low, int high)】
④ 总实现代码
// 辅助数组B
int *B=(int *)malloc(n*sizeof(int));
// A[low,...,mid]，A[mid+1,...,high]各自有序，将这两个部分归并
void Merge(int A[], int low, int mid, int high){
int i,j,k;
for(k=low; k<=high; k++)
B[k]=A[k];
for(i=low, j=mid+1, k=i; i<=mid && j<= high; k++){
if(B[i]<=B[j])
A[k]=B[i++];
else
A[k]=B[j++];
}
while(i<=mid)
A[k++]=B[i++];
while(j<=high)
A[k++]=B[j++];
}
// 递归操作（使用了分治法思想）
void MergeSort(int A[], int low, int high){
if(low<high){
int mid = (low+high)/2;
MergeSort(A, low, mid);
MergeSort(A, mid+1, high);
Merge(A,low,mid,high); //归并
}
}
时间、空间复杂度
5. 基数排序
直接看课本的过程图来理解P352
再看这个例子：
算法思想：把整个关键字拆分为d位，按照各个关键字位递增的次序（比如：个、十、百），做d趟“分配”和“收集”，若当前处理关键字位可能取得r个值，则需要建立r个队列。分配：顺序扫描各个元素，根据当前处理的关键字位，将元素插入相应的队列。一趟分配耗时 O(n) 。收集：把各个队列中的结点依次出队并链接。一趟收集耗时 O( r ) 。- 基数排序擅长处理的问题：
①数据元素的关键字可以方便地拆分为d组，且d较小。
②每组关键字的取值范围不大，即r较小。
③ 数据元素个数n较大。 - 算法效率分析：
时间复杂度：一共进行d趟分配收集，一趟分配需要 O(n) ，一趟收集需要O( r ) ，时间复杂度O[d(n+r)] ，且与序列的初始状态无关.空间复杂度： O( r ) ，其中r为辅助队列数量。稳定性：稳定。
内部排序算法总结
