排序算法 (插入,选择,冒泡,希尔,快速,归并,堆排序)
排序:经常在算法题中作为一个前置操作,为了之后的贪心or else做个铺垫,虽然我们经常都只是调用个sort,但是了解一些排序算法可以扩充下知识库
排序的分类:
从存储设备角度：
✓ 内排序：在排序过程中所有数据元素都在内存中；
✓ 外排序：当待排序元素所占空间大到内存存不下时，排序
必需借助外存来完成。
➢ 按对关键词的操作：
✓ 基于关键词比较的排序：基于关键词比较；
✓ 分布排序：基于元素的分布规律。
➢ 按时间复杂度：
✓ 平方阶算法：算法简单易于实现，平均时间复杂度 O(n2)；
✓ 线性对数阶算法：相对复杂，平均时间复杂度 O(nlogn)；
✓ 线性算法：不依赖关键词比较，需要已知元素的分布规律。
N^2排序
1,插入排序,
默认前面的i-1个元素已经排序好了,然后将第i个元素插入
void InsertionSort(int R[],int n){ //对R[1]...R[n]排序
for(int i=2; i<=n; i++){ //默认第1个元素已经有序
int K=R[i], j=i-1; //悬空第i个元素,遍历前i-1个元素
while(j>=1 && R[j]>K){ //从后向前找到第一个不小于他的元素
R[j+1]=R[j]; //依次将元素挪动
j--; //下标左移
}
R[j+1]=K; //因为最火一次操作一定停在一个大于等于k的位置
}
}
时间复杂度N^2(最好的时候是 n) 空间复杂度 1 并且是稳定的
在基本有序,数据量小的时候比较快
2,冒泡排序
(检索是否需要和右侧元素发生交换)
Low版实现;
void SimpleBubbleSort(int R[], int n){
for(int bound=n; bound>=2; bound--) //每一轮一定可以确定一个元素位置
for(int i=1; i<bound; i++)
if(R[i] > R[i+1])
swap(R[i],R[i+1]);
}
当然可以用一个flag来表示是否发生交换来进行一个优化
High level版本:
每一轮当中,一定会有一个最后一次发生交换的地方我们将它记作lp,那么lp之后的元素一定是有序的,我们不需要再次去在下一轮去遍历
void BubbleSort(int R[], int n){
int bound=n; //每趟冒泡关键词比较的终止位置
while(bound>0){
int t=0; //本趟冒泡元素交换的最后位置
for(int i=1; i<bound; i++)
if(R[i]>R[i+1]){ swap(R[i],R[i+1]); t=i; }
bound=t; //两种情况:1没有交换,t=0 2,t表示着最后一次交换的位置
}
}
为什么t=i 而不是i+1?
比如 : 4 3 2 1 5
第一次: 3 2 1 4 5 最后一次发生交换的位置是 3(1),那么3之后的 4,5没有发生交换,所以是有序的,但是很明显,3位置上的1不是有序的,还需要我们在下一轮的时候去交换
时间复杂度N^2(最好的时候是 n) 空间复杂度 1 并且是稳定的
3,选择排序法
”每次选择第i大的元素,直接确定好他的位置
void SelectionSort(int R[], int n){
for(int i=n; i>=1; i--){ //找到并且确定第i大的元素的位置
int max=1;
for(int j=2; j<=i; j++) //从第2个到第i个里面找最大值
if(R[j]>R[max]) max=j;
swap(R[max],R[i]); //把最大值放在第i个位置上
}
}
时间复杂度N^2(最好的时候是 n^2) 空间复杂度 1 但是是不稳定的
4,希尔排序:
有一点类似计算机组成的组相联(魔怔了)
在特定变化的组中进行插入排序
比如 :4 3 2 1 5 5个元素
第一次排序是在 4 和 1 排序; 3 和5 排序 ;2自己一组 d=5/2=2
变成: 1 3 2 4 5
第二次是d=d/2=1; 相当于直接就是插入排序了 过程略了
大概的逻辑就是利用插入排序的特点:数据少and基本有序的时候更快
1刚开始,组多,但是每组的数据量少,所以快一点
2,最后组少,但是基本都是有序的,所以也会快一点
void ShellSort(int R[], int n){ //对R[1]…R[n]递增排序
for(int d=n/2; d>0; d/=2) //d为增量值 .一开始的d是R的长度
for(int i=d+1; i<=n; i++){ //.....R[i-3d], R[i-2d], R[i-d] ß R[i]
int K=R[i],j=i-d;//(对比插入排序就是1->d )
while(j>0 && R[j]>K){//在本组从右往左找第1个£K的元素
R[j+d]=R[j];
j-=d;
}
R[j+d]=K;
}
}
时间复杂度nlogn -n^2 空间复杂度 1 但是是不稳定的
Nlogn的排序:
1,堆排序
最大堆and最小堆(堆顶元素是最小or最大的,并且树根的值大于两个子树)
结构性：完全二叉树。
堆序性：任意结点的关键词大于等于(小于等于)其孩子的关键词。
堆的顺序存储:
✓R[1]存根结点；
✓结点R[i]的左孩子（若有的话）存放在R[2i]处；
✓R[i] 的 右 孩 子（若有的话）存 放在R[2i+1]处；
✓R[i]的父结点为 R[i/2]。
堆的两个操作:
1,上浮
(当我们插入or修改一个元素的时候会用到)
void ShiftUp(int R[], int i){ //堆元素R[i]上浮, 数组R[ ]存储堆,
while(i>1 && R[i]>R[i/2]){ //i不是根R[i]比父亲大
swap(R[i], R[i/2]); //交换R[i]和父亲
i/=2; //结点i继续上浮
}
}
2,下沉
(当我们修改了一个元素o弹出栈顶元素的时候会用到(弹出栈顶时,我们会把最后一个元素放在栈顶,之后将其下沉来保证堆序性))
下沉的时候,我们优先选择大的孩子进行交换
void ShiftDown(int R[], int n, int i) { //堆元素R[i]下沉, n为堆包含的元素个数
while(i <= n/2){ //i最多下行至最后一个非叶结点
int maxchd = 2*i; // 假定最大孩子为左孩子
if(maxchd+1<=n && R[maxchd]<R[maxchd+1]) //有右孩子并且更大
maxchd++; //i的右孩子是最大孩子
if(R[i] >= R[maxchd]) return; //已经满足了堆序性,返回
swap(R[maxchd],R[i]); // R[i]的最大孩子比R[i]大
i = maxchd; // 结点i继续下沉
}
}
3,建堆
的时候本质就是将尾部插入,依次上浮(我喜欢的但是考试一般是给我一个堆)
考试做法:从最后一个非叶节点开始建堆(检查需不需要下沉)
void BuildHeap(int R[],int n){
for(int i=n/2; i>=1; i--)
ShiftDown(R,n,i); //建立以i为根的堆，即下沉i
}
n的时间复杂度///算是一个考点
4,修改
void xiugai(int R[],int i,int val){
R[i]=val;
ShiftDown(R, n, i);
ShiftUp( R, i);
}
5,尾部插入
void insert(int R[],int &n,int val){
R[++n]=val;
ShiftUp(R, n);
}
6,弹出堆顶
Void pop(int R[],int &n ){
R[1]=R[n];
n--;
ShiftDown(R, n, 1)
}
时间复杂度 nlogn 空间 1 不稳定
2,快速排序:
选取基准元素然后根据基准元素来将数组分左右(每次确定元素k的位置)
所以可以变种成寻找第k大的元素
将数组根据R[m]划分位=为左右两侧
int Partition(int R[], int m, int n){ //对子数组Rm…Rn分划
int K=R[m], L=m+1, G=n; //Rm为基准元素
while(L<=G) {
while(L<=n && R[L]<=K) L++; //从左向右找第一个>K的元素
while(R[G]>K) G--;//从右向左找第一个£K的元素
if(L<G) {swap(R[L],R[G]); L++; G--;}
}
swap(R[m],R[G]);
return G;
}
void QuickSort(int R[], int m, int n){ //对Rm…Rn递增排序
if(m < n){
int k=Partition(R, m, n); //找到本次的划分,这个时候的的第k个元素已就位
QuickSort(R, m, k-1); /排序左边
QuickSort(R, k+1, n); //排序右边
}
}
时间复杂度 nlogn,最坏是 N^2 空间复杂度 n - log n 不稳定
其他的题,我们也可以根据性质来划分
给定一个含有正数和负数的数组，编写程序对数组进行重新排列，使得所有正整数在数左侧、负数在数组右侧，要求时间复杂度为O(n)、空间复杂度O(1)。
双指针,一个从左向右找负数,一个从右向左找正数-
如果一个整数序列中一半为奇数，一半为偶数，编写一个时间复杂度O(n)、空间复杂度O(1)的算法，重新排列这些整数，使得奇数在前，偶数在后。
给定一个非负整数数组 R，其中一半整数是奇数，一半整数是偶数。编写时间复杂度O(n)、空间复杂度O(1)的算法，对数组重新排列，使得奇数放在数组的奇数位，偶数放在数组的偶数位。
优化策略
1,数据量小的时候采用插入排序
2,基准元素采用3数取中法
3,尾部递归改成循环
4,优先处理短区间降低递归深度
5,利用stack消除递归
7,当递归深度过深,直接转化为堆排序
8,当重复元素过多,尝试使用3路分划:
设置3个指针，前指针i，中指针j，后指针k；
➢初始时i=1, j=1, k=n；指针j从左往右扫描数组：
➢若R[j]为白，什么也不做继续扫描, j++；
➢若R[j]为红，交换R[j]和R[i], i++, j++；
➢若R[j]为蓝，交换R[j]和R[k], k--；
➢通过j的遍历，使红色换到数组i左边，蓝色换到数组k右边
while (j<=k){
if (R[j]==‘红’){
swap(R[j], R[i]);
j++; i++;
}
else if (R[j]==‘蓝’){
swap(R[j], R[k]);
k--;
}
else // R[j]==‘白’
j++;
}
快速排序方法是基于关键词比较的内排序算法中平均情况下时间最快的。
➢为什么平均情况下快速排序比堆排序快？
✓nlogn的常系数(1.386 vs 2）
✓倾向于访问物理上相邻的数据，缓存命中率高
3,归并排序,
自底向上的,先让左边有序,再让右边有序,最后录入结果
void MergeSort(int R[], int m, int n){
if(m < n){
int k = m+(n-m)>>1; //将待排序序列等分为两部分
MergeSort(R, m, k); //处理左边
MergeSort(R, k+1, n); //处理右边
Merge(R, m, k, n); //依次录入
}
}
void Merge(int R[],int low, int mid, int high){
//将两个相邻的有序数组(Rlow,…,Rmid)和(Rmid+1,…,Rhigh)合并成一个有序数组
int i=low, j=mid+1, k=0;
int *X=new int[high-low+1];
while(i<=mid&& j<=high)
if(R[i]<=R[j]) X[k++]=R[i++];
else X[k++]=R[j++];
while(i<=mid) X[k++]=R[i++]; //复制余留记录(补录)
while(j<=high) X[k++]=R[j++];
for(i=0; i<=high-low; i++) //将X拷贝回R
R[low+i]=X[i];
delete []X;
}
时间复杂度 nlogn 空间复杂度 n 稳定的(最快的稳定排序)
更适合链表;
node* sort(node* head) {
int n = 0;
for (auto p = head; p; p = p->next)n++; //记录长度
for (int len = 1; len < n; len += len) { //底部的长度
auto dummy = new node, cur = dummy; //记录下头节点,以免头节点被排序到后面去导致丢失数据
for (int j = 1; j <= n; j += 2 * len) { //对 2*len的区域进行排序
auto r = head, l = head; //找到第一个len部分的第一个节点
for (int i = 0; i < len && r; i++)r = r->next; //第二个len的头节点
auto nexts = r;
for (int i = 0; i < len && nexts; i++)nexts = nexts->next; //找到下一段2*len的头节点
int len1 = 0, len2 = 0;
while (len1 < len && len2 < len && l && r) {//录入
if (l->data <= r->data) {
cur->next = l;
cur = cur->next;
l = l->next;
len1++;
}
else {
cur->next = r;
cur = cur->next;
r = r->next;
len2++;
}
}
while (len1 < len && l) { //补录左边
cur->next = l;
cur = cur->next;
l = l->next;
len1++;
}
while (len2 < len && r) { //补录右边
cur->next = r;
cur = cur->next;
r = r->next;
len2++;
}
head= nexts; //进入下一段
}
cur->next = NULL; //防止最后一个节点退出的时候指向前面几个节点
head= dummy->next; //归位头节点
}
return head;
}
如果是链表操作的话,需要改为非递归形式,伪代码如下
For(底部长度 len = 1:n/2){
Int s1=1,mid=len,s2=s1+len
While(s2<=n){
从s1...mid s2...2*len将大的放入数组中
补录s1..mid
补录s2.2*len
S1=2*len+1;
S2=s1+len;
}
}
计算逆序对
逆序对个数=左侧逆序对 + 右侧逆序对 + (左右两边的逆序对)录入的时候记录
伪代码
Int nixudui(int a[],int l,int r){
左边=nixudui(a,l,(l+r)/2),右边=nixudui(a,(l+r)/2+01,r);
Res=左边+右边
While(补录){
如果左边的数更大 res++然后录入
反之 录入
}
补录
Return res;
}
总结;
