考研数据结构之排序小结
排序的问题比较杂,想通过这篇博客理顺一下,基础的概念这里不累述。
总体的知识框架如下:
1、关于适用场景:
①直接插入排序适用于排序表和数据量不大的排序表;
②取一大堆数据中K个最大(小)的元素,优先选用堆排序;
③大规模排序,希尔排序均能达到较好的效果;
④快速排序的平均性能达到O(nlog2n),在实际中应用较多;
⑤文件初始状态已按照关键字基本有序,直接插入或冒泡,可以达到O(n);
⑥当n较大时,优先选用快速排序、堆排序、归并排序;
若要求稳定,则选归并排序;
平均时间最短的为快速排序;
辅助空间少的为堆排序;
2、关于稳定性
快速排序,希尔排序,简单选择排序,堆排序不稳定;
3、关于时间复杂度
①最佳情况能达到O(n)的有直接插入排序和冒泡排序
②排序算法的关键字比较次数与原始序列无关的——简单选择排序、折半插入排序;
排序算法的排序趟数与原始序列无关的——交换类排序;
排序算法的shij时间复杂度列无关的——简单选择排序O(n2)、堆排序O(nlog2n),二路归并O(nlog2n);
③平均时间复杂度为O(nlog2n)的有:快速排序、堆排序、归并排序;
4、关于空间复杂度:
快速排序O(log2n);归并O(n);基数排序O(rd)
5、需要记忆的排序代码:
重点:快速排序
void quicksort(Elemtype a[],int low,int high){
int i=low,j=high;
int temp=a[low];
if(i<j){
while(i<j&&a[j]>=temp)
--j;
a[i]=a[j];
while(i<j&&a[i]<=temp)
++i;
a[j]=a[i];
}
a[i]=temp;
quicksort(a,low,i-1);
quicksort(a,i+1,high);
}
应用:
①在数组a[1....n]中找到第K小的元素:
int kth_elem(Elemtype a[],int low,int high,int k){
int temp=a[low];
int i=low,j=high;
if(i<j){
while(i<j&&a[j]>=temp)
--j;
a[i]=a[j];
while(i<j&&a[i]<=temp)
++i;
a[j]=a[i];
}
a[i]=temp;
if(i==k)
return temp;
else if(i>k)
return kth_elem(a,low,i-1,k);
else
return kth_elem(a,i+1,high,k);
}