备战复试,每日三题
题目一:希尔排序
希尔排序(Shell’s Sort)是插入排序的一种又称"缩小增量排序"(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。 希尔排序是非稳定排序算法。
希尔排序–交换法(相当于分组的冒泡排序)
void shellSort(vector<int>& nums){
int n=nums.size();
//确定增量,初始增量设为数组长度的一半,每一轮变为原来的一半,增量为1时结束
for(int gap=n/2;gap>0;gap/=2){
//对应增量的下标开始
for(int i=gap;i<n;i++){
//按照增量分为若干组,每组可能有多个元素
for(j=i-gap;j>=0;j-=gap){
//对于每组中的元素排序(交换)
if(nums[j]>nums[j+gap]){
int temp=nums[j];
nums[j]=nums[j+gap];
nums[j+gap]=temp;
}
}
}
}
}
希尔排序–移位法(相当于分组的简单插入排序)
void shellSort(vector<int>& nums){
int n=nums.size();
//确定增量,初始增量设为数组长度的一半,每一轮变为原来的一半,增量为1时结束
for(int gap=n/2;gap>0;gap/=2){
//对应增量的下标开始
for(int i=gap;i<n;i++){
//按照增量分为若干组,每组可能有多个元素,对每个分组直接插入排序
int j=i;
int temp=nums[i];
if(nums[j]<nums[j-gap]){
while(j-gap>=0&&temp<nums[j-gap]){
nums[j]=nums[j-gap];
j-=gap;
}
nums[j]=temp;
}
}
}
}
题目二: 堆排序
堆排序:
若要升序排列,则先将输入的数字调整为大顶堆(任何一个节点的值大于等于它的左子节点和右子节点的完全二叉树)
基本思想:
1.首先将待排序的数组构造成一个大顶堆,此时,整个数组的最大值就是堆结构的顶端
2.将顶端的数与末尾的数交换,此时,末尾的数为最大值,剩余待排序数组个数为n-1
3.将剩余的n-1个数再构造成大顶堆,再将顶端数与n-1位置的数交换,如此反复执行,便能得到有序数组
void heapSort(vector<int>& nums){
int n=nums.size();
//在初始的树中找到最后一个非叶子节点,从它开始调整
for(int i=n/2-1;i>=0;i--){
adjust(nums,i,n);
}
// 2).将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
// 3).重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序。
for(int i=n-1;i>=0;i--){
int temp=nums[0];
nums[0]=nums[i];
nums[i]=temp;
adjust(nums,0,i);
}
}
void adjust(vector<int>& nums,int i,int len){
int temp=a[i];
//i代表当前树的根节点的下标
//2*i+1代表其左子树,2*i+2代表其右子树
for(int k=2*i+1;k<len;k=2*k+1){
//找到左右节点值最大的,并让k等于对应的下标
if(k+1<len&&nums[k]<nums[k+1]){
//说明左子结点的值小于右子结点的值
k++;
}
//将最大的孩子的值比父节点值大,则交换
if(nums[k]>temp) {//如果子结点大于父结点
nums[i]=nums[k]; //把较大的值赋给当前结点
//因为交换了节点,所以还要调整下面的子树
i=k;
}else {
break;
}
}
//当for 循环结束后,我们已经将以i 为父结点的树的最大值,放在了 最顶(局部)
nums[i]=temp;//将temp值放到调整后的位置
}
}