第七章 排序
一、插入排序
1.1 直接插入排序
空间O(1);时间最好O(n)最坏O(n^2);稳定
//a[0]相当于哨兵
void InsertSort(int a[],int n)
{
int i, j;
for(int i = 2; i <= n; i ++ ) // 依次将a[2]~a[n]插入前面已经排好序的队列
{
if(a[i] < a[i - 1]) // 如果a[i]小于它前面那个数,准备执行插入操作
{
a[0] = a[i]; // 用哨兵先备份a[i]元素
for(j = i - 1; a[0] < a[j]; j -- ) // 从后往前开始比较大小,如果比当前所比元素还小
a[j + 1] = a[j]; // 就让前面的那个元素挪到后面
a[j + 1] = a[0]; // 再把哨兵存的元素放入到当前位置
}
}
}
1.2 折半插入排序
和直接插入的区别是:将比较和插入的操作分离。
即先折半查找出元素的待插入位置,然后再统一的移动插入位置之后的所有元素
空间O(1);时间最好O(n)最坏O(n^2);稳定
//a[0]相当于哨兵
void InsertSort(int a[],int n)
{
int i, j, low, high, mid;
for (int i = 2; i <= n; i ++ ) // 依次将a[2]~a[n]插入前面已排序序列
{
a[0] = a[i]; // 先用哨兵a[0]存a[i]的值
low = 1, high = i - 1; // low和high代表边界,然后才能取中点mid
while(low <= high) // 折半查找(默认递增排序)
{
int mid = low + high >> 1; // 取中间点
if(a[mid] > a[0]) high = mid - 1; // 如果中点值 > 哨兵,查找左半表
else low = mid + 1; // 如果中点值 <= 哨兵,查找右半表
}
for(int j = i - 1; j >= low; j --)
a[j + 1] = a[j]; // 确定位置后,统一将位置后移
a[low] = a[0]; // 将空的位置放入哨兵存的值
}
}
1.3 希尔排序
思想是:先把待排序的表划分为若干个等同区间的子表(即把相隔某个“增量”的记录组成子表),
然后对各个子表分别进行直接插入排序,
当整个表的元素基本有序后,最后对全体再来一次直接插入排序
空间O(1);时间平均O(n^3/2)最坏O(n^2);不稳定
//0相当于哨兵
void ShellSort(int a[],int n)
{
for (int d = n / 2; d >= 1; d = d / 2) // 先进行分组,d即步长变化
for (int i = d + 1; i <= n; i ++ ) // 然后分别进入到各组中进行排序
if (a[i] < a[i - d]) // 需将a[i]插入到增量子表
{
a[0] = a[i]; // 暂存在a[0]
for (int j = i - d; j > 0 && a[0] < a[j]; j -= d)
a[j + d] = a[j]; // 纪录后移,查找直接插入位置
a[j + d] = a[0]; // 插入
}
}
二、交换排序(⭐该从这里整理)
2.1 冒泡排序
//0相当于哨兵
void ShellSort(int a[],int n){
for(int d=n/2;d>=1;d/=2){ //增量
for(int i=1;i<1+d;i++){ //按照增量分为d个子表
for(int j=i+d;j<=n;j+=d){ //对每个表进行排序
a[0]=a[j];
int k;
for(k=j-d;k>0&&a[0]<a[k];k-=d){ //找到插入位置
a[k+d]=a[k];
}
a[k+d]=a[0];
}
}
}
}
2.2 快速排序
int Partition(int a[],int low,int high){
int pivot = a[low];
while(low<high){
while(low<high&&a[high]>=pivot) high--;
a[low] = a[high];
while(low<high&&a[low]<=pivot) low++;
a[high] = a[low];
}
a[low] = pivot;
return low;
}
//快速排序
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);
}
}
三、选择排序
3.1 简单选择排序
//下标从1开始
void SelectSort(int a[],int n){
for(int i=1;i<=n;i++){
int tmp=i;
for(int j=i+1;j<=n;j++){
if(a[j]<a[tmp]){
tmp=j;
}
}
swap(a[tmp],a[i]);
}
}
3.2 堆排序
// ***-------大根堆排序(结果是升序)-------***
//将元素k为根的子树进行调整(大根堆)
void HeadAdjust(int a[],int k,int n){
a[0] = a[k];
for(int i=k*2;i<=n;i*=2){
if(i<n&&a[i]<a[i+1]){
i++;
}
if(a[0]>=a[i]) break;
else{
a[k]=a[i];
k=i;
}
}
a[k] = a[0];
}
//建立大根堆
void BuildMaxHeap(int a[],int n){
for(int i=n/2;i>=1;i--){
HeadAdjust(a,i,n);
}
}
//堆排序
void HeapSort(int a[],int n){
BuildMaxHeap(a,n);
for(int i=n;i>1;i--){
swap(a[i],a[1]);
HeadAdjust(a,1,i-1);
}
}
// ***-------小根堆排序(结果是降序)-------***
//将元素k为根的子树进行调整(小根堆)
void HeadAdjust(int a[],int k,int n){
a[0] = a[k];
for(int i=k*2;i<=n;i*=2){
if(i<n&&a[i]>a[i+1]){
i++;
}
if(a[0]<=a[i]) break;
else{
a[k]=a[i];
k=i;
}
}
a[k] = a[0];
}
//建立小根堆
void BuildMaxHeap(int a[],int n){
for(int i=n/2;i>=1;i--){
HeadAdjust(a,i,n);
}
}
//堆排序
void HeapSort(int a[],int n){
BuildMaxHeap(a,n);
for(int i=n;i>1;i--){
swap(a[i],a[1]);
HeadAdjust(a,1,i-1);
}
}
四、归并排序
void Merge(int a[],int low,int mid,int high){
for(int i=low;i<=high;i++){
b[i] = a[i];
}
int k=low,i=low,j=mid+1;
while(i<=mid&&j<=high){
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>>1;
MergeSort(a,low,mid);
MergeSort(a,mid+1,high);
Merge(a,low,mid,high);
}
}