希尔排序
直接插入排序的改进——希尔排序( O ( n log 2 ( n ) ) O(n\log_2(n)) O(nlog2(n)),不稳定,就地)
核心:分组预处理+组内直接插入排序
流程:将待排序元素序列分割成若干个子序列,在子序列内分别进行直接插入排序,待序列基本有序(接近正序)时,再对全体记录进行直接插入排序,能够大大提升直接插入排序效率。希尔排序不存在有序区和无序区。
分组方法:并非逐段分组,而是将相距某个增量的元素组成一个子序列。对于长度为 n n n的数组,增量序列为 n 2 1 , n 2 2 , n 2 3 , … , 1 \frac{n}{2^1},\frac{n}{2^2},\frac{n}{2^3},\ldots,1 21n,22n,23n,…,1,且增量序列互质(最经典的分组方法)。
void sort(){for(int gap=MAX/2;gap>0;gap/=2){//逐步缩小gap,初始间隔为MAX/2,依次折半for(int j=gap;j<MAX;j++){//从gap开始,对每组序列内进行直接插入排序int temp=a[j],i;for(i=j-gap;i>=0;i-=gap){//此处与直接插入排序稍有不同:j为i-gap而非i-1,迭代时为j-=gap而非j--if(temp<a[i]) a[i+gap]=a[i];//将大者后移else break;//找到插入点}a[i+gap]=temp;}}
}
归并排序
归并排序是对分治法的运用。 O ( n log 2 ( n ) ) O(n\log_2(n)) O(nlog2(n)),稳定,非就地
快速排序
冒泡排序的改进——快速排序( O ( n log 2 ( n ) ) O(n\log_2(n)) O(nlog2(n)),不稳定,就地)
核心:哨兵变量的选取
流程:在每次划分中,选一个枢轴(哨兵变量/主元/基准值,通常选第一个元素作为枢轴,但在最坏情况下会劣化为冒泡排序),将待排序序列划分成两部分,左侧记录均 ≤ \le ≤轴值,右侧记录均 ≥ \ge ≥轴值(左小右大),哨兵变量位于序列中间(枢轴归位),本次划分完毕。然后分别对这两部分重复上述过程,直到每部分内只有一个元素或为空为止,整个序列有序。
- 左右指针法
- 实现方法1
extern int a[MAX];
int part(int l,int r){int i=l,j=r;//i为轴值指针while(i<j){while(a[i]<=a[j]&&i<j) j--;//从右侧开始找比轴值小的元素 注:先从轴值的对侧开始扫描if(i<j) swap(a[i],a[j]),i++;//小者置前,此处变为j为轴值指针while(a[j]>=a[i]&&i<j) i++;//从左侧开始找比轴值大的元素if(i<j) swap(a[i],a[j]),j--;//大者置后,此处变为i为轴值指针}return i;//返回轴值最终所在位置
}
void sort(int l,int r){int i;if(l<r){i=part(l,r);sort(l,i-1);sort(i+1,r);}
}
//调用:sort(0,MAX-1);
- 实现方法2
extern int a[MAX];
int part(int l,int r){//l:轴值指针int i=l,j=r;while(i<j){while(a[l]<=a[j]&&i<j) j--;//从右侧找到首个比轴值小的元素while(a[l]>=a[i]&&i<j) i++;//从左侧找到首个比轴值大的元素swap(a[i],a[j]);//确保左小右大}swap(a[l],a[i]);//先从右侧扫小的,因此a[i]一定是比轴值小的元素return i;
}
void sort(int l,int r){int i;if(l<r){i=part(l,r);sort(l,i-1);sort(i+1,r);}
}
//调用:sort(0,MAX-1);
- 挖坑法
extern int a[MAX];
int part(int l,int r){int i=l,j=r,key=a[i];while(i<j){while(a[j]>=key&&i<j) j--;if(i<j) a[i]=a[j],i++;while(a[i]<=key&&i<j) i++;if(i<j) a[j]=a[i],j--;}a[i]=key;return i;
}
void sort(int l,int r){int i;if(l<r){i=part(l,r);sort(l,i-1);sort(i+1,r);}
}
//调用:sort(0,MAX-1);
- 前后指针法
堆排序
简单选择排序的改进——堆排序( O ( n log 2 ( n ) ) O(n\log_2(n)) O(nlog2(n)),不稳定,就地)
计数排序
O ( n + k ) O(n+k) O(n+k),稳定,非就地
桶排序
O ( n + k ) O(n+k) O(n+k),稳定,非就地
基数排序
( O ( n × k ) O(n\times k) O(n×k),稳定,非就地)