排序算法的应用
标签: 数据结构
学习人数: 6518

八大内部排序如下:

  插入排序:直接插入排序、希尔排序

  选择排序:简单选择排序、堆排序

  交换排序:冒泡排序、快速排序

  归并排序

  基数排序

 

不同条件下,排序方法的选择

  (1)若n较小(如n≤50),可采用直接插入或直接选择排序。

  当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。

  (2)若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;

  (3)若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或归并排序。

 

  快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;

  堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。

  若要求排序稳定,则可选用归并排序。但本章介绍的从单个记录起进行两两归并的  排序算法并不值得提倡...

登录查看完整内容


课后作业

课后习题

 

【2019年真题】选择一个排序算法时,除算法的时空效率外,下列因素中,还需要考虑的是

I.数据的规模     Ⅱ.数据的存储方式 Ⅲ.算法的稳定性    V.数据的初始状态

A. 仅Ⅲ          B. 仅I、Ⅱ C. 仅Ⅱ、Ⅲ、IV    D. I、Ⅱ、Ⅲ、Ⅳ

参考答案:D

 

【2016年真题】对10TB的数据文件进行排序,应使用的方法是()

  1. 希尔排序
  2. 堆排序
  3. 快速排序
  4. 归并排序

参考答案:D

 

【2016年真题】已知由n(n>=2)个正整数构成的集合A={ak,0<=k<n},将其划分为两个不相交的子集A1和A2,元素个数分别是n1和n2,,A1和A2中元素之和分别为S1和S2。设计一个尽可能高效的划分算法,满足|n1-n2|最小且|s1-s2|最大。要求:

  1. 给出算法的基本设计思想。
  2. 根据设计思想,采用C或C++语言描述算法,关键之处给出注释。
  3. 说明你所设计算法的平均时间复杂度和空间复杂度。

参考答案:

  1. 算法的基本设计思想

由题意知,将最小的⌊n/2⌋个元素放在A1中,其余的元素放在A2中,分组结果即可满足题目要求。仿照快速排序的思想,基于枢轴将n个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理:

  1. 若i=⌊n/2⌋,则分组完成,算法结束;
  2. 若i<⌊n/2⌋,则枢轴及之前的所有元素均属于A1,继续对i之后的元素进行划分;
  3. 若i>⌊n/2⌋,则枢轴及之后的所有元素均属于A2,继续对i之前的元素进行划分;

基于该设计思想实现的算法,无需对全部元素进行排序,其平均时间复杂度是O(n),空间复杂度是O(1)。

  1. 算法实现
int setPartition(int a[], int n) {  
    int pivotkey,low=0,low0=0,high=n-1;  
    int high0=n-1,flag=1,k=n/2,i;  
    int s1=0,s2=0;  
    while (flag) {  
        pivotkey=a[low]; //选择枢轴  
        while (low < high) {//基于枢轴对数据进行划分  
            while (low < high && a[high] >= pivotkey)  
                --high;  
            if (low!=high) a[low]=a[high];  
            while (low<high && a[low]<=pivotkey)  
                ++low;  
            if (low!=high)a[high]=a[low];  
        }  
        a[low]=pivotkey;  
        if (low==k-1) //如果枢轴是第n/2小元素,划分成功  
            flag = 0;  
        else { //否则继续划分  
            if (low<k-1) {  
                low0=++low;  
                high=high0;  
            }  
            else {  
                high0=--high;  
                low=low0;  
            }  
        }  
    }  
    for (i = 0; i < k; i++) s1+=a[i];  
    for (i = k; k < n; i++) s2+=a[i];  
    return s2 - s1;  
}  

 

  1. 算法的平均时间复杂度和空间复杂度

该算法的平均时间复杂度为O(n),空间复杂度为O(1)。

 

【2013年真题】已知一个整数序列A=(a0,a1,...,an-1), 其中0<=ai<n(0<=i<n) 。若存在ap1=ap2=...=apm=x且m>n/2(0<=pk<n,1<=k<=m),则称x为A的主元素。例如A=( 0, 5,5,3,5,7,5,5 ),侧 5 为主元素;又如 A= ( 0,5,5,3,5,1,5,7 ),则 A 中没有主元素。假设 A 中的 n 个元素保存在一个一维数组中,请设计一个尽可能高效的算法,找出 A 的主元素。若存在主元素,则输出该元素;否则输出-1。要求:

(1)给出算法的基本设计思想。

(2)根据设计思想,采用 C 或 C++或 Java 语言描述算法,关键之处给出注释。

(3)说明你所设计算法的时间复杂度和空间复杂度。

参考答案:

(1)给出算法的基本设计思想:

算法的策略是从前向后扫描数组元素,标记出一个可能成为主元素的元素 Num。然 后重新计数,确认 Num 是否是主元素。

算法可分为以下两步:

① 选取候选的主元素:依次扫描所给数组中的每个整数,将第一个遇到的整数 Num 保存到 c 中,记录 Num 的出现次数为 1;若遇到的下一个整数仍等于 Num,则计数加 1, 否则计数减 1;当计数减到 0 时,将遇到的下一个整数保存到 c 中,计数重新记为 1, 开始新一轮计数,即从当前位置开始重复上述过程,直到扫描完全部数组元素。

② 判断 c 中元素是否是真正的主元素:再次扫描该数组,统计 c 中元素出现的次数,若大于 n/2,则为主元素;否则,序列中不存在主元素。

(2)算法实现:

int Majority (int A[ ], int n ) {  
    int i, c, count=1; // c 用来保存候选主元素,count 用来计数  
    c = A[0]; // 设置 A[0]为候选主元素  
    for (i=1; i<n; i++) // 查找候选主元素  
        if (A[i] = = c)  
            count++; // 对 A 中的候选主元素计数  
        else if (count > 0) // 处理不是候选主元素的情况  
            count--;  
        else // 更换候选主元素,重新计数  
        {  
            c = A[i];  
            count = 1;  
        }  
    if (count > 0)  
        for (i=count=0; i<n; i++) // 统计候选主元素的实际出现次数  
            if ( A[i] = = c )  
                count++;  
    if (count> n/2) return c; // 确认候选主元素  
    else return -1; // 不存在主元素  
}  

(3)说明算法复杂性:

参考答案中实现的程序的时间复杂度为 On),空间复杂度为 O(1)。


登录后发布评论

1 条评论
Smilezw
2021年1月30日 20:41

排序算法还是结合代码看比较方便