排序
- 概述
分类
内排序：数据量少，在内存中
插入
交换
选择
归并
外排序：数据量大，内外存需要交换数据
按复杂度分
简单算法：冒泡、简单选择、直接插入
改进算法：希尔、堆、归并、快速
稳定性：两个一样的数字，排序后相对位置不变，则稳定
- 冒泡排序
思想：从上到下/从下到上，与相邻元素比较
改进：设置有无交换的标志位
复杂度：最好/最坏
稳定：arr[j]严格>arr[j+1]时，才做交换
void BubbleSort(vector<int> arr)
{
int sz=arr.size();
bool flag=true;
for(int i=0;i<sz-1&&flag;i++)
{
flag=false;//没交换
for(int j=sz-2;j>=i;j--)
{
if(arr[j]>arr[j+1])
{
swap(arr[j],arr[j+1]);
flag=true;
}
}
}
}- 简单选择排序
思想：通过n-i次比较，从n-i+1中选出最小的，与位置i的交换
复杂度
void SelectSort(vector<int> arr)
{
int sz=arr.size();
int min;
for(int i=0;i<sz-2;i++)
{
min=i;
for(j=i+1;j<sz-1;j++)
{
if(arr[min]>arr[j])
min=j;
}
if(i!=min) swap(arr[i],arr[min]);
}
}- 直接插入排序
思想：扑克牌 将一个元素插入已经排好序的序列中
复杂度
稳定
void InsertSort(vector<int> arr)
{
int sz=arr.size();
for(int i=1;i<sz;i++)
{
int tmp=arr[i];//摸下一张牌
for(int j=i;j>0&&arr[j-1]>tmp;j--)
arr[j]=arr[j-1];//为新牌找位置，比它大的都向后挪
arr[j]=tmp;//新牌落座
}
}- 希尔排序
思想：定义增量序列（最后一定是1）；对每个增量序列进行排序；基本有序；跳跃；
更多增量序列
复杂度
不稳定
void ShellSort(vector<int> arr)
{
int N=arr.size();
for(int D=N/2;D>0;D/=2)//增量序列
{
for(int i=D;i<N;i++)//插入排序
{
int tmp=arr[i];
for(int j=i;j>=D&&arr[j-D]>tmp;j-=D)
arr[j]=arr[j-D];
arr[j]=tmp;
}
}
}- 堆排序（选择排序的改进）
思路：构建最大堆；堆顶与堆尾元素交换；删去堆尾后重建最大堆；重复
（利用堆的性质：完全二叉树；编号；父/子节点编号）
数组编号从0开始，堆从1开始
复杂度（最好/坏/平均一样）
不稳定
不适合待排序序列个数少的
// 递归方式构建大根堆(len是arr的长度，index是第一个非叶子节点的下标)
void adjust(vector<int> &arr, int len, int index)
{
int left = 2*index + 1; // index的左子节点
int right = 2*index + 2;// index的右子节点
int maxIdx = index;//maxIdx保存根、左、右最大的下标
if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
if(right<len && arr[right] > arr[maxIdx]) maxIdx = right;
if(maxIdx != index)
{
swap(arr[maxIdx], arr[index]);
adjust(arr, len, maxIdx);//从此次最大子节点的位置递归
}
}
// 堆排序
void HeapSort(vector<int> &arr, int size)
{
// 构建大根堆（从最后一个非叶子节点向上）
for(int i=size/2 - 1; i >= 0; i--)
{
adjust(arr, size, i);
}
// 调整大根堆
for(int i = size - 1; i >= 1; i--)
{
swap(arr[0], arr[i]); // 将当前最大的放置到数组末尾
adjust(arr, i, 0); // 去除最后位置的元素，将未完成排序的部分继续进行堆排序
}
}- 归并排序
思想：有序子列的归并
复杂度：最好/坏/平均一样
空复：常用于外排序
稳定：两两比较，无跳跃
递归：
void Merge(int a[], int b[], int left, int mid, int right)//归并到a
{
int i=left,j=mid+1;
int k=left;//存放结果数组的初始位置
while(i<=mid&&j<=right)
{
if(a[i]<=a[j]) b[k++]=a[i++];
else b[k++]=a[i++];
}
while(i<=mid)
b[k++]=a[i++];
while(j<=right)
b[k++]=a[j++];
for(i=left;i<right-left+1;i++)
a[i]=b[i];
}
void Msort(int a[], int b[], int l, int r)
{
if (l >= r) //必须有等号
return;
int m = (l + r)/2;
Msort(a, b, l, m);
Msort(a, b, m + 1, r);
Merge(a, b, l, m, r);
}
void MergeSort(int a[], int len)
{
int *b = new int[len];
//int *b;
//b=malloc(len*sizeof(int));
if(!b)
{
Error("空间不足");
}
else
{
Msort(a, b, 0, len - 1);
delete[] b;
//free(b);
}
}//非递归：
void MergePass(int a[],int b[],int len,int sz)
{
int i;
for(i=0;i<=len-2*sz;i+=2*sz)
Merge1(a,b,i,i+sz,i+2*sz-1);//将a归并到b
if(i+sz<len)//归并最后两个子列
Merge1(a,b,i,i+sz,len-1);
else//最后只剩一个子列
for(int j=i;j<len;j++)
b[j]=a[j];
}
void MergeSort(int a[], int len)
{
int sz=1;//初始化子序列长度
int *b = new int[len];
//int *b;
//b=malloc(len*sizeof(int));
if(!b)
{
Error("空间不足");
}
else
{
while(sz<len)
{
MergePass(a,b,len,sz);
sz*=2;
MergePass(b,a,len,sz);
sz*=2;
}
delete[] b;
//free(b);
}
}- 稳定：冒泡、直接插入、归并
不稳定：简单选择、希尔、堆、快速
