考研数据结构排序算法比较
考研排序算法比较
记录一下考研会涉及到有关排序算法理论性的知识:
(桶排序在考研中很少涉及, 个人认为计数排序已经算是桶排序的一种了, 所以没有提及, 于是众多周知十大排序算法有九种)
| 算法 | 排序趟数与原始序列是否有关 | 元素比较次数与原始序列是否有关 | 元素移动次数与原始序列是否有关 |
|---|---|---|---|
| 直接插入排序 | 否 | 是 | 是 |
| 冒泡排序 | 是 | 是 | 是 |
| 简单选择排序 | 否 | 否 | 是 |
| 希尔排序 | 否 | 是 | 是 |
| 快速排序 | 是 | 是 | 是 |
| 堆排序 | 否 | 是 | 与堆的调整有关 |
| 2路归并排序 | 否 | 否 | 否 |
| 基数排序 | 否 | 否 | 否 |
| 计数排序 | 否 | 否 | 否 |
| 算法 | 适合用链表做存储结构 | 适合用顺序表做存储结构 | 基于关键字的比较 |
|---|---|---|---|
| 直接插入排序 | 是 | 是 | 是 |
| 冒泡排序 | 是 | 是 | 是 |
| 简单选择排序 | 是 | 是 | 是 |
| 希尔排序 | 否 | 是 | 是 |
| 快速排序 | 否 | 是 | 是 |
| 堆排序 | 否 | 是 | 是 |
| 2路归并排序 | 是 | 是 | 是 |
| 基数排序 | 是 | 否 | 否 |
| 计数排序 | 是 | 是 | 否 |
以上是本人在不同学校自主命题以及408的统考题中总结出来的, 针对考察排序算法比较的选择题, 如总结有误欢迎在评论区指正
下面是考研数据结构初试最有可能要求手写的代码, 亲测可用:
1. 直接插入
void InsertSort(int a[],int n)//插入排序
{for(int i=1;i<n;i++){int temp = a[i];int j;if(a[i]<a[i-1]){for(j=i-1;j>=0&&a[j]>temp;j--)//这里是temp不是a[i]!如果改为a[i]会在后序排序中被不断覆盖!{a[j+1]=a[j];}a[j+1]=temp;}}return;
}
2. 冒泡排序
///冒泡排序:
void Swap(int *a,int *b)
{int temp = *a;*a = *b;*b = temp;return;
}void BubbleSort(int a[],int n)
{for(int i=0;i<n;i++){int flag=0;for(int j=n-1;j>i;j--){if(a[j]<a[j-1]){Swap(a+j,a+j-1);flag=1;}}if(!flag)break;}return;
}
3. 简单选择排序
///简单选择排序:
void Swap(int *a,int *b)
{int temp = *a;*a = *b;*b = temp;return;
}void EasySelectSort(int a[],int n)
{for(int i=0;i<n-1;i++){int min_index = i;for(int j=i+1;j<n;j++){if(a[min_index]>a[j])min_index = j;}if(min_index!=i)Swap(a+min_index,a+i);}
}
4. 希尔排序
///希尔排序:(4,2,1)
void ShellSort(int a[],int n)
{int d[3] = {4,2,1};for(int i=0;i<sizeof(d)/sizeof(int);i++){int j,k,l,temp;for(j=0;j<d[i];j++)//遍历每个子表{for(l=j+d[i];l<n;l+=d[i])//对每个子表执行插入排序{if(a[l]<a[l-d[i]]){temp = a[l];for(k=l-d[i];k>=0&&a[k]>temp;k-=d[i]){a[k+d[i]] = a[k];}a[k+d[i]] = temp;}}}}return;
}
5. 快速排序
///快速排序:
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 mid = Partition(a,low,high);QuickSort(a,low,mid-1);QuickSort(a,mid+1,high);}return;
}
6. 归并排序
///归并排序:
int *merge_space;
void Merge(int a[], int low, int mid ,int high)
{int i,j,k;for(int k=low;k<=high;k++){merge_space[k] = a[k];}for(i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){if(merge_space[i]<=merge_space[j])a[k] = merge_space[i++];elsea[k] = merge_space[j++];}while(i<=mid)a[k++] = merge_space[i++];while(j<=high)a[k++] =merge_space[j++];
}void MergeSort(int a[],int low,int high)
{if(low<high){int mid = (low+high)/2;MergeSort(a,low,mid);MergeSort(a,mid+1,high);Merge(a,low,mid,high);}return;
}
7. 计数排序
///计数排序:
int *result;
int *count;
void CountSort(int a[],int n,int len_cnt)//a:待排序数组 n:待排序数组长度 len_cnt:计数数组长度(桶的数量)
{for(int i=0;i<n;i++)count[a[i]]++;for(int i=1;i<len_cnt;i++)count[i] = count[i]+count[i-1];for(int i=n-1;i>=0;i--)result[--count[a[i]]] = a[i];return;
}
8. 折半插入排序
///折半插入
void BinarySort(int a[],int n)
{int i,j,temp,low,high;for(i=1;i<n;i++){temp = a[i];low=0;high = i-1;while(low<=high){//循环等待low>high, 这时mid所指就是目标元素待插入位置int mid = (low+high)/2;if(a[mid]>temp)high = mid-1;else low = mid+1;}for(j=i-1;j>=high+1;j--)//此时low与mid相等, high小于low, mid=low=元素应该插入的位置a[j+1] = a[j];a[high+1] = temp;}return;
}
以上代码在默写时可能出现的错误情况总结:
1.快速排序
为了便于说明, 我把我在手写代码时经常出错的点全部在上图标注了出来,用数字1~9标明。 上图是CodeBlock IDE的界面。
数字1 处可能的错误:代码错写为:
while(low<=high) //多加了一个等于号, 这是不对的
我们都知道, 快速排序是需要寻找枢纽(pivot)的, 而判断枢纽被找出来的方法就是low==high, 这也是第一层循环跳出的条件, 如果在第一层while循环处加了这么个等于号, 代表你默认low == high时也可以进行循环, 进入循环后, 由于内部两个while循环条件不满足, 因此low和high在循环内不会被改变。于是直接进入下一层循环, 就这样不断进入死循环。
数字2和4处可能的错误: 代码写错为:
while(low<high&&a[high]>=temp)high--;while(low<=high&&a[low]<temp)low++;
或
while(low<=high&&a[high]>=temp)high--;while(low<=high&&a[low]<temp)low++;
首先, 第一个while循环里面low<high改写为low<=high是没问题的, 因为在第一个内部while循环进入时low根本不可能等于high, 理由是有最外层while循环在"把关", low == high的情况根本进不来, 所以这里改写为low<=high对程序的运行没有任何影响, 只是没必要这么写。
关键在于第二个while循环, 里面若改为low<=high就等同于你默认low ==high时可以进入该循环, 我们先来回顾一下, 如果low ==high就相当于我们已经找到枢纽元素的最终位置了，但是该位置原来的元素有可能小于枢纽元素, 所以第二个while循环对"low==high"这个条件"放行", 结果就是执行low++, 使得low>high, 暂且不谈我们好不容易找到的枢纽位置丢失了, 后面执行的a[high] = a[low]也会使本来位置正确的元素被错误赋值到low++后的位置上, 这样即使程序不会发生死循环或内存泄露, 其结果也是错误的!
数字3和5处可能的错误:
3和5处, 必须保证至少有一处是有等于号的! 也就是说, 你可以做出以下修改:
| 修改 | 是否合法 |
|---|---|
3处:a[high]>=temp5处: a[low]<temp | 合法 |
3处:a[high]>temp5处: a[low]<=temp | 合法 |
3处:a[high]>=temp5处: a[low]<=temp | 合法 |
3处:a[high]>temp5处: a[low]<temp | 不合法! |
理由:
如果3和5都不加等号, 就会发生以下情况:
排序时遇到了a[high]的值大小与枢纽元素相同, 可是第一个内部while循环只能处理a[high]>temp的情况, 因此跳过该循环, 执行赋值语句a[low] = a[high],
现在a[low]和a[high]都与枢纽元素相等了, 进入第二个while循环时, 第二个内部while循环只能处理a[low]<temp的情况, 因此跳过该循环, 再一次毫无意义第执行一次赋值语句a[low] = a[high], 外部循环循环第二次时, 第一个内部while循环还是处理不了a[low] == a[high]的情况, 第二个内部while循环也同样, 于是进入第三次外部while循环…没错， 你已经死循环了。
数字6处:
这里写成a[low] = temp或a[high] = temp都行, 因为快速排序中找到枢纽时一定有low==high, 在整个快速排序过程中就不会出现low>high的情况。
数字7处:这里写成low<=high也没事, 只是没必要, 因为QuickSort函数是递归函数, 而递归的终止条件需要Partition函数给出, Partition函数内的while外层循环就已经直接把low ==high这个情况排除掉了, 所以不影响排序结果的正确性。
数字8和9处:
这两处不能有任何一处被错改为"mid", 否则下一次递归调用划分区间时把本来最终位置已经确定的元素划分进来参与枢纽元素的定位导致排序错误!
2. 折半插入排序
数字1和2处:
折半插入排序是直接插入排序的优化, 它是利用折半查找来定位待插入元素的位置的, 两个指针low和high在找到元素后的状态一定是low>high, 或者更确切地描述就是low = high+1, 注意, 这里要与快速排序的两个指针low和high在找到元素位置后的状态作区分:
折半查找找到元素位置后的指针状态: low = mid = 元素最终位置 > high
快速排序找到元素位置后的指针状态: low = high = 元素最终位置
所以折半插入排序元素最终要插入在low指向的位置(或者说mid所指向的位置, 都行)。
因此1和2处代码可以按如下改写, 不影响正确性:
for(j=i-1;j>=low;j--)//1处://此时low与mid相等, high小于low, mid=low=元素应该插入的位置a[j+1] = a[j];a[low] = temp;//2处
发布评论