排序:经常在算法题中作为一个前置操作,为了之后的贪心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;
}
下列排序方法中，每趟排序结束都至少能确定一个元素最终位
置的方法是__134___。【考研题全国卷】
I.直接选择排序 II.希尔排序 III.快速排序 IV.堆排序 V.合并排序
下列哪个算法可能出现下列情况：在最后一趟开始之前，所有
的元素都不在其最终的位置上。
A. 堆排序 B. 冒泡排序 C. 插入排序 D. 快速排序
外排序常用归并排序
总结;
