精华内容
下载资源
问答
  • 对n个记录的文件进行堆排序
    2022-02-26 09:42:21

    堆排序
     


    堆的定义
        小根堆:ai<=a2i、ai<=a(2i+1)
        大根堆:ai>=a2i、ai>=a(2i+1)
        
        从堆的定义可以看出,堆实质是满足如下性质的完全二叉树;二叉树中任一非叶子结点均小于(大于)它的孩子结点
        
    堆排序    
        若在输出堆顶的最小值(最大值)后,使得剩余n-1个元素的序列重又建成一个堆,则得到n个元素的次小值(次大值)......如此反复,便能得到一个有序序列,这个过程称之为堆排序。
        
    实现堆排序需解决两个问题:
        1.如何由一个无序序列建成一个堆?
        2.如何在输出堆顶元素后,调整剩余元素为一个新的堆?
        
    如何在输出堆顶元素后,调整剩余元素为一个新的堆?
    小根堆:
        1.输出堆顶元素之后,以堆中最后一个元素替代之;
        2.然后将根结点值与左、右子树的根结点值进行比较,并与其中小者进行交换;
        3.重复上述操作,直至叶子结点,将得到新的堆,称这个从堆顶至叶子的调整过程为“筛选”
        
    筛选过程的算法描述为:
     

    int rc,j;
    void HeapAdujust(int R[], int s, int m) {
    /*
    * 已知R[s..m]中记录的关键字除R[s]之外均满足堆的定义,本函数
    * 调整R[s]的关键字,使R[s]成为一个大根堆
    */    
        rc = R[s];
        for (j = 2 * s; j <= m; j *= 2) {//沿key较大的孩子结点向下筛选
            if (j < m && R[j] < R[j + 1])//j为key较大的记录的下表
                ++j;
            if (rc >= R[j])
                break;
            R[s] = R[j];
            s = j;//rc应插入在位置s上
        }
        R[s] = rc;//插入
    }//HeapAdjust

    筛选过程的算法解读:
        1.s是根节点下标,m是数组最大下标,j被赋值为s的左孩子下标
        2.第一个if对两个子节点进行比较,选最大的子节点,在第二个if中与根结点的值比较
        3.如果根结点的值更大则直接退出,保持不变
        4.否则将大的子节点的值赋值给根结点的位置,然后将子节点的下标赋值给s
        5.进行循环继续比较,循环结束后将之前存的根结点的值赋值在叶子结点上
        
    堆的调整:
        对一个无序序列反复“筛选”就可以得到一个堆;即:从一个个无序序列建堆的过程就是一个反复“筛选”的过程。
        
    堆的建立:

    显然:
        单结点的二叉树是堆;
        在完全二叉树中所有以叶子结点    (序号i>n/2)为根的子树是堆。
    即:    
        对应由n个元素组成的无序序列,“筛选”只需从第n/2个元素开始。
        
    堆的建立: 
        由于堆实质上是一个线性表,那么我们可以顺序存储一个堆
        下面以一个实例介绍建一个小根堆的过程。
        
    将初始无序的R[1]到R[n]建成一个小根堆,可用一下语句实现:

        for(i=n/2;i>=1;i--)
            HeapAdjust(R,i,n);


        
    堆排序
    由以上分析知:
        若对一个无序序列建堆,然后输出根;重复该过程就可以由一个无序序列输出有序序列。
        实质上,堆排序就是利用完全二叉树中父结点与孩子结点之间的内在关系来排序的。
        
    堆排序的算法如下:

    void HeapSort(int R[]) {//对R[1]到R[n]进行堆排序
        int i,n;
        for (i = n / 2; i >= 1; i--)
            HeapAdujust(R, i, n);//建初始堆
        for (i = n; i > 1; i--) {//进行n-1趟排序
            swap(R[1], R[i]);//根与最后一个元素交换
            HeapAdujust(R, 1, i - 1);//对R[1]到R[i-1]重新建堆
        }
    }//HeapSort

    算法性能分析


    初始堆化所需时间不超过O(n)
    排序阶段(不含初始堆化)
        一次重新堆化所需时间不超过O(logn)
        n-1次循环所需时间不超过O(nlogn)
            Tw(n)=O(n)+O(nlogn)=O(nlogn)
        
        堆排序的时间主要耗费在建初始堆和调整建新堆时进行的反复筛选上。堆排序在最坏情况下,其时间复杂度也为O(nlog2n),这是堆排序的最大优点。无论待在排序列中的记录是正序还是逆序排列,都不会使堆排序处于“最好”或“最坏”的状态。
        另外,堆排序仅需一个记录大小供交换用的辅助存储空间。
        然而堆排序是一种不稳定的排序方法,它不适用于待排序记录个数n较少的情况,但对于n较大的文件还是很有效的。

    更多相关内容
  • 排序算法——堆排序

    千次阅读 2019-07-22 14:48:18
    在介绍堆排序之前我们首先应该弄清楚堆排序可以解决什么问题,答案是显而易见的:排序。说得通俗点儿就是一组无序的数字进行调整,使其按照从大到小或者从小大到的顺序有序排列。既然知道了堆排序的作用了,那么有...

    在介绍堆排序之前我们首先应该弄清楚堆排序可以解决什么问题,答案是显而易见的:排序。说得通俗点儿就是对一组无序的数字进行调整,使其按照从大到小或者从小大到的顺序有序排列。既然知道了堆排序的作用了,那么有的同学就会有疑问了,为什么“排序”前面加了“堆”呢?究竟什么是堆呢?这一节我们就详细了解什么是堆?如何利用堆进行排序?

    定义

    堆排序定义

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    堆排序的特点

    堆排序的特点是:在排序过程中,将R[l…n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构),在当前无序区中选择关键字最大(或最小)的记录

    堆的定义

    堆是一棵顺序存储的完全二叉树。所谓完全二叉树即叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树。

    其中每个结点的关键字都不大于其孩子结点的关键字,这样的堆称为小根堆。

    其中每个结点的关键字都不小于其孩子结点的关键字,这样的堆称为大根堆。

    举例来说,对于n个元素的序列{R0, R1, … , Rn}当且仅当满足下列关系之一时,称之为堆:

    • Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
    • Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)

    其中i=1,2,…,n/2向下取整;

    image
    image

    如下图所示,序列R{3, 8,15,31,25}
    是一个典型的小根堆。

    image

    堆中有两个父结点,元素3和元素8。

    元素3在数组中以R[0]表示,它的左孩子结点是R[1],右孩子结点是R[2]。

    元素8在数组中以R[1]表示,它的左孩子结点是R[3],右孩子结点是R[4],它的父结点是R[0]。可以看出,它们满足以下规律:设当前元素在数组中以R[i]表示,那么,

    1. 它的左孩子结点是:R[2*i+1];
    2. 它的右孩子结点是:R[2*i+2];
    3. 它的父结点是:R[(i-1)/2];
    4. R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。

    堆可以被看成是一棵树,结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目;定义堆的高度为树根的高度。我们将看到,堆结构上的一些基本操作的运行时间至多是与树的高度成正比,为O(lgn)。

    堆排序基本思想

    堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。

    1. 用大根堆排序的基本思想
    • 先将初始文件R[1…n]建成一个大根堆,此堆为初始的无序区
    • 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1…n-1]和有序区R[n],且满足R[1…n-1].keys≤R[n].key
    • 由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1…n-1]调整为堆。然后再次将R[1…n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1…n-2]和有序区R[n-1…n],且仍满足关系R[1…n-2].keys≤R[n-1…n].keys,同样要将R[1…n-2]调整为堆。
    • ……直到无序区只有一个元素为止。
    1. 大根堆排序算法的基本操作:
    • 建堆,建堆是不断调整堆的过程,从len/2处开始调整,一直到第一个节点,此处len是堆中元素的个数。建堆的过程是线性的过程,从len/2到0处一直调用调整堆的过程,相当于o(h1)+o(h2)…+o(hlen/2) 其中h表示节点的深度,len/2表示节点的个数,这是一个求和的过程,结果是线性的O(n)。
    • 调整堆:调整堆在构建堆的过程中会用到,而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i),选出三者最大(或者最小)者,如果最大(小)值不是节点i而是它的一个孩子节点,那边交互节点i和该节点,然后再调用调整堆过程,这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系,是lgn的操作,因为是沿着深度方向进行调整的。
    • 堆排序:堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换),将前面len-1个节点继续进行堆调整的过程,然后再将根节点取出,这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)(调用一次);调整堆的时间复杂度是lgn,调用了n-1次,所以堆排序的时间复杂度是O(nlgn)

    注意

    • 只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
    • 用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。

    代码实现

    【点击查看】

    总结

    堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。平均性能为O(N*logN)。由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。堆排序是就地排序,辅助空间为O(1).它是不稳定的排序方法。(排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前 和排序后他们的相对位置不发生变化)

    展开全文
  • 1) 排序 n 元素,元素为随机生成的长为1..32的字符串(字符串均为英文小写字母),n的取值为:2^2,2^5,2^8,2^11,2^14,2^17; 2) 算法:直接插入排序,堆排序,归并排序,快速排序; 3) 字符串大小判断标准...
    1. 实验要求
      1) 排序 n 个元素,元素为随机生成的长为1..32的字符串(字符串均为英文小写字母),n的取值为:2^2,2^5,2^8,2^11,2^14,2^17;
      2) 算法:直接插入排序,堆排序,归并排序,快速排序;
      3) 字符串大小判断标准:首先按字符串长度进行排序(短字符串在前,长字符串在后)。然后对长度相同的字符串,按字母顺序进行排序;
      4) 对结果进行性能分析。
    2. 实验环境
      1) 编译环境:Dev-C++ 5.9.2
      2) 机器内存:8G
      3) 时钟主频:2.2GHz
    3. 实验过程
      1) 实现getstrs函数(input.cpp源码在文件夹input中),随机产生2^17个均为小写字母的字符串,将字符串写入文件input_strings.txt中;
      2) 实现插入排序StraightInsertSort.cpp,其中产生不同规模下插入排序的结果result_n.txt和运行时间time.txt;
      3)实现堆排序HeapSort.cpp,其中产生不同规模下堆排序的结果result_n.txt和运行时间time.txt;
      4) 实现归并排序MergeSort.cpp,其中产生不同规模下归并排序的结果result_n.txt和运行时间time.txt;
      5) 实现快速排序QuickSort.cpp,其中产生不同规模下快速排序的结果result_n.txt和运行时间time.txt;
      6) 进行结果分析。
    4. 实验关键代码截图
      1) getstrs函数实现思路:每个字符串都是先产生一个随机长度,然后产生长度个随机字符写入input_strings.txt中,字符串间以换行间隔。
    void getstrs()
    {
        FILE *fp;
        int i,slen,j;
        char temp;
        srand((unsigned)time(NULL));
        fp = fopen("input_strings.txt", "w");
        for (i = 0; i < NUM; i++)
        {   
            slen = rand()*rand() % 32 + 1;
            for (j = 0; j < slen; j++)
            {
                temp = 'a' + rand()*rand() % 26;
                fputc(temp,fp);
            }
            fputc('\n',fp);
        }
        fclose(fp); 
    }

    2) 记录运行时间的方法(级别us):

    #include "windows.h"
    
    static LARGE_INTEGER Freq;
    static LARGE_INTEGER start;
    static LARGE_INTEGER end;
    static double dt;//用于计时
    
    void count_start()
    {
        QueryPerformanceFrequency(&Freq);
        QueryPerformanceCounter(&start);
    }
    
    double count_stop()
    {
        QueryPerformanceCounter(&end);
        dt = (end.QuadPart - start.QuadPart)/(double)(Freq.QuadPart);
        return dt;
    }
    

    3) 插入排序过程
    a) 从输入数据中读取前num (问题规模)个字符串存入strtemp[num][33]

    fp = fopen("..\\\\input\\input_strings.txt","r");
    rewind(fp);
    for(j = 0; j < num; j++)
    {//从输入数据中读取字符串
        memset(strtemp[j],0,33*sizeof(char));
        fscanf(fp,"%s",strtemp[j]);         
    }   
    fclose(fp);

    b) 实现插入排序的过程(compare为按照长度优先、字典顺序优先的字符串比较函数,swap实现交换两个字符串的功能,起始记录时间)

    count_start();//排序开始
        for(j = 1; j < num; j++)
        {//从第一个开始,依次调整j以前的所有元素的顺序
            i = j - 1;
            strcpy(key,strtemp[j]);
            while(i >= 0)
            {
                if(!(compare(key,strtemp[i])))
                {//逐步往后移直到找到正确的位置
                    swap(strtemp[i],strtemp[i+1]);
                    i--;
                }
                else
                    break;      
            }
            strcpy(strtemp[i+1],key);
        } 
        dtime[k] = count_stop();//排序结束

    compare:

    int compare(char a[33], char b[33])
    {
        int len1 = strlen(a);
        int len2 = strlen(b);
        if(len1 < len2)
        {
            return 0;
        }
        else if(len1 == len2)
        {
            if(strcmp(a,b) < 0)
            {
                return 0;
            }
            else
                return 1;
        }
    }
    

    swap:

    void swap(char a[33], char b[33])
    {
        char temp[33];
        strcpy(temp,a);
        strcpy(a,b);
        strcpy(b,temp);
    }

    c) 将排序结果进行文件result_n.txt中

    for(i = 0; i < num; i++)
    {//排序结果写进相应文件
       fputs(strtemp[i],fp1);
       fputc('\n',fp1);
    }

    4) 堆排序算法的实现:
    a) 从input_strings.txt中读取数据(方法同上)
    b) 堆排序过程:

    count_start();//排序开始
    BuildHeap(strtemp,num);
    for(i = num;i >= 2; i--)
    {
        swap(strtemp[1],strtemp[i]); 
        HeapAdjust(strtemp,1,i-1);      
    }
    dtime[k] = count_stop();//排序结束

    c) 建堆BuildHeap过程:

    void BuildHeap(char (*a)[33],int size)     
    {//建堆
        int i;
        for(i = size/2;i >= 1; i--)     
        {//从第一个非叶节点开始进行堆调整
            HeapAdjust(a,i,size);    
        }    
    } 

    d) 堆调整HeapAdjust过程(swap和compare与插入排序中的一样):

    void HeapAdjust(char (*a)[33],int i,int size)  
    {//堆调整过程
        int lchild = 2*i;      
        int rchild = 2*i + 1;    
        int max = i;            
        char temp[33];
        if(i <= size/2)          
        {
            if(lchild <= size && !(compare(a[max],a[lchild])))
            {//跟左孩子的值比较
                max = lchild;
            }    
            if(rchild <= size && !(compare(a[max],a[rchild])))
            {//跟右孩子的值比较
                max = rchild;
            }
            if(max != i)
            {//交换调整
                swap(a[i],a[max]);
                HeapAdjust(a,max,size);//递归调整     
            }
        }        
    }

    e) 将运行结果写入文件中。

    5) 归并排序算法的实现:
    a) 从input_strings.txt中读取数据(方法同上)
    b) 归并排序过程(递归执行):

    count_start();//排序开始  
    Merge(strtemp,1,num);
    dtime[k] = count_stop();//排序结束
    void Merge(char (*a)[33],int p,int r)
    {
        int q;
        if(p < r)
        {
            q = (p + r) / 2; 
            Merge(a,p,q);//左边进行递归的归并
            Merge(a,q+1,r);//右边进行递归的归并
            PreMerge(a,p,q,r);//将左右两边合成一个数组
        }
    }

    c) PreMerge过程(将p到q和q+1到r两部分合并到a中):
    i. 先将a[p..q]复制给L[1..nums1],将a[q+1..r]复制给R[1..nums2];
    ii. 由于在执行PreMerge之前已经对a[p..q]和a[q+1,r]进行了Merge操作,故此时L和R中均为已排好序的数组
    iii. 依次比较L[i]和R[j],将较小的写入a[k]中;
    iv. 将L或R中剩余的元素复制到a中。

    void PreMerge(char (*a)[33],int p,int q,int r)
    {//将两个已排好序的数组合并成一个
        int nums1 = q - p + 1, nums2 = r - q;
        int i,j,k;
        for(i = 1; i <= nums1; i++)
        {//将a的前半部分复制到L中
            memset(L[i], 0, 33*sizeof(char));
            strcpy(L[i], a[p+i-1]); 
        }
        for(j = 1; j <= nums2; j++)
        {//将a的后半部分复制到R中
            memset(R[j], 0, 33*sizeof(char));
            strcpy(R[j], a[q+j]);
        }
        for(k = p,i = 1,j = 1; k <= r; k++)
        {//逐个比较L[i]和R[j],按大小顺序复制到原数组中
            if(i <= nums1 && j <= nums2)
            {
                if(!(compare(L[i],R[j])))
                    strcpy(a[k],L[i++]);
                else
                    strcpy(a[k],R[j++]);
            }
            else if(i > nums1)//剩余元素复制到a中
                strcpy(a[k],R[j++]);
            else            
                strcpy(a[k],L[i++]);
        }
    }

    d) 运行结果写入文件

    6) 快速排序算法的实现:
    a) 从input_strings.txt中读取数据(方法同上)
    b) 快速排序过程:

    count_start();//排序开始   
    QuickSortRecur(strtemp,1,num);
    dtime[k] = count_stop();//排序结束
    void QuickSortRecur(char (*a)[33],int p, int r)
    {//递归进行排序
        int q;
        if(p < r)
        {
            q = Partition(a,p,r);//以a[r]为标记进行分区
            QuickSortRecur(a,p,q-1);//分区左边进行快排
            QuickSortRecur(a,q+1,r);//分区右边进行快排
        }
    }

    c) Partition过程(取a[r]为标记位):

    int Partition(char (*a)[33],int p,int r)
    {
        char temp[33];
        int i,j;
        strcpy(temp,a[r]);
        i = p - 1;
        for(j = p; j <= r-1; j++)
        {//将每个树与a[r]进行比较
            if(!(compare(a[j],temp)))
            {
                i++;
                swap(a[i],a[j]);
            }
        }
        swap(a[i+1],a[r]);
        return i+1;
    }
    
    

    d) 运行结果写入文件
    5. 实验结果、分析(结合相关数据图表分析)
    1) 直接插入排序结果分析(工具:Excel):
    这里写图片描述
    基本符合O(n2)的算法复杂度
    2) 堆排序结果分析(发现excel中没有nlgn的拟合,故用origin8进行)
    这里写图片描述
    基本符合O(nlgn)的算法复杂度
    3) 归并排序结果分析
    这里写图片描述
    基本符合O(nlgn)的算法复杂度
    4) 快速排序结果分析
    这里写图片描述
    基本符合O(nlgn)的算法复杂度
    6. 实验心得
    1) 对直接插入排序、堆排序、归并排序、快速排序的算法及其性能有了更深入的了解,学会了四种不同排序算法的实现,在性能分析上,后三个算法的时间性能明显优于直接插入排序,快速排序比堆排序和归并排序性能稍优一点,而归并排序需要多占用一倍的存储空间(本实验中,尚未考虑到存储空间限制的情况);
    2) 对文件读写操作更为熟练;
    3) 学会了使用excel和origin等数据分析工具进行性能的分析过程。

    实验源代码:
    http://download.csdn.net/download/m0_37829610/10025033
    转载请注明出处:
    http://blog.csdn.net/m0_37829610/article/details/78259022

    展开全文
  • 一、什么是排序算法1.1、排序定义一序列对象根据某个关键字进行排序。1.2、排序术语稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;...

    一、什么是排序算法

    1.1、排序定义

    对一序列对象根据某个关键字进行排序。

    1.2、排序术语

    稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;

    不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;

    内排序:所有排序操作都在内存中完成;

    外排序:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;

    时间复杂度: 一个算法执行所耗费的时间。

    空间复杂度:运行完一个程序所需内存的大小。

    1.3、算法总结

    b1892b9ca585b8bd58ccbf2ff431d5d7.png

    (注意:n指数据规模;k指“桶”的个数;In-place指占用常数内存,不占用额外内存;Out-place指占用额外内存

    1.4、算法分类

    148929d7afd568e3cac3900a616d74ca.png


    1.5、比较和非比较的区别

    常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。在冒泡排序之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中,问题规模通过分治法消减为logN次,所以时间复杂度平均O(nlogn)。比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,比较排序适用于一切需要排序的情况。计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr[i]之前有多少个元素,则唯一确定了arr[i]在排序后数组中的位置。非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度O(n)。非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。

    二、冒泡排序(Bubble Sort)

    冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

    2.1、算法描述

    比较相邻的元素。如果第一个比第二个大,就交换它们两个;

    对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;

    针对所有的元素重复以上的步骤,除了最后一个;

    重复步骤1~3,直到排序完成。

    2.2、动图演示

    a33a1043575fa6356cbd64179543a290.gif

    ​2.3、代码实现

    /**
    

    2.4、算法分析

    最佳情况:T(n) = O(n) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(n2)

    三、选择排序(Selection Sort)

    表现最稳定的排序算法之一,因为无论什么数据进去都是O(n2)的时间复杂度,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

    3.1、算法描述

    n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:

    初始状态:无序区为R[1..n],有序区为空;

    第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;

    n-1趟结束,数组有序化了。

    3.2、动图演示

    b444b1fd3e05792e7d2e5cf9581f825f.gif

    3.3、代码实现

    /**
    

    3.4、算法分析

    最佳情况:T(n) = O(n2) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(n2)

    四、插入排序(Insertion Sort)

    插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

    4.1、算法描述

    • 一般来说,插入排序都采用in-place在数组上实现。具体算法描述如下:
    • 从第一个元素开始,该元素可以认为已经被排序;
    • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
    • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
    • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
    • 将新元素插入到该位置后;
    • 重复步骤2~5。

    4.2、动图演示

    fa045b76e01e0242236d498c65a4ca49.gif

    ​4.3、代码实现

    /**
    

    4.4、算法分析

    最佳情况:T(n) = O(n) 最坏情况:T(n) = O(n2) 平均情况:T(n) = O(n2)

    五、希尔排序(Shell Sort)

    希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法。希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。希尔排序是把记录按下表的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

    5.1、算法描述

    我们来看下希尔排序的基本步骤,在此我们选择增量gap=length/2,缩小增量继续以gap = gap/2的方式,这种增量选择我们可以用一个序列来表示,{n/2,(n/2)/2...1},称为增量序列。希尔排序的增量序列的选择与证明是个数学难题,我们选择的这个增量序列是比较常用的,也是希尔建议的增量,称为希尔增量,但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序,具体算法描述:

    选择一个增量序列t1,t2,…,tk,其中ti>tj,tk=1;

    按增量序列个数k,对序列进行k 趟排序;

    每趟排序,根据对应的增量ti,将待排序列分割成若干长度为m 的子序列,分别对各子表进行直接插入排序。仅增量因子为1 时,整个序列作为一个表来处理,表长度即为整个序列的长度。

    5.2、过程演示

    20fad71110ed38cd9b17ae2f75a1b106.png

    5.3、代码实现

    /**
    

    5.4、算法分析

    最佳情况:T(n) = O(nlog2 n) 最坏情况:T(n) = O(nlog2 n) 平均情况:T(n) =O(nlog2n) 

    六、归并排序(Merge Sort)

    和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(n log n)的时间复杂度。代价是需要额外的内存空间。归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

    6.1、算法描述

    把长度为n的输入序列分成两个长度为n/2的子序列;

    对这两个子序列分别采用归并排序;

    将两个排序好的子序列合并成一个最终的排序序列。

    6.2、动图演示

    07bf662b5b3e485d80028b645ec76c68.gif

    ​6.3、代码实现

    /**
    

    6.4、算法分析

    最佳情况:T(n) = O(n) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)

    七、快速排序(Quick Sort)

    快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

    7.1、算法描述

    快速排序使用分治法来把一个串(list)分为两个子串(sub-lists)。具体算法描述如下:

    从数列中挑出一个元素,称为 “基准”(pivot);

    重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;

    递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

    7.2、动图演示

    5380dcd00b38dd711d80a2ccd07cc1b5.gif

    ​7.3、代码实现

    /**
    

    7.4、算法分析

    最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(nlogn) 

    八、堆排序(Heap Sort)

    堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

    8.1、算法描述

    • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆,此堆为初始的无序区;
    • 将堆顶元素R[1]与最后一个元素R[n]交换,此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n];
    • 由于交换后新的堆顶R[1]可能违反堆的性质,因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆,然后再次将R[1]与无序区最后一个元素交换,得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1,则整个排序过程完成。

    8.2、动图演示

    42c470302cdbe95c2eaa01ac199474ba.gif

    8.3、代码实现

    //声明全局变量,用于记录数组array的长度;
    

    8.4、算法分析

    最佳情况:T(n) = O(nlogn) 最差情况:T(n) = O(nlogn) 平均情况:T(n) = O(nlogn)

    九、计数排序(Counting Sort)

    计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。

    9.1、算法描述

    • 找出待排序的数组中最大和最小的元素;
    • 统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
    • 对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
    • 反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

    9.2、动图演示

    bebb159e08b4e81aaaa62769a9bc1885.gif

    9.3、代码实现

    /**
    

    9.4、算法分析

    当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。最佳情况:T(n) = O(n+k) 最差情况:T(n) = O(n+k) 平均情况:T(n) = O(n+k)

    十、桶排序(Bucket Sort)

    桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排。

    10.1、算法描述

    • 人为设置一个BucketSize,作为每个桶所能放置多少个不同数值(例如当BucketSize==5时,该桶可以存放{1,2,3,4,5}这几种数字,但是容量不限,即可以存放100个3);
    • 遍历输入数据,并且把数据一个一个放到对应的桶里去;
    • 对每个不是空的桶进行排序,可以使用其它排序方法,也可以递归使用桶排序;
    • 从不是空的桶里把排好序的数据拼接起来。
    • 注意,如果递归使用桶排序为各个桶排序,则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量,否则会陷入死循环,导致内存溢出。

    10.2、图片演示

    3e06bd227c48c370a49f94388a51e92c.png

    10.3、代码实现

    /**
    

    10.4、算法分析

    桶排序最好情况下使用线性时间O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大。 最佳情况:T(n) = O(n+k) 最差情况:T(n) = O(n+k) 平均情况:T(n) = O(n2)  

    十一、基数排序(Radix Sort)

    基数排序也是非比较的排序算法,对每一位进行排序,从最低位开始排序,复杂度为O(kn),为数组长度,k为数组中的数的最大的位数;基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。基数排序基于分别排序,分别收集,所以是稳定的。

    11.1、算法描述

    取得数组中的最大数,并取得位数;

    arr为原始数组,从最低位开始取每个位组成radix数组;

    对radix进行计数排序(利用计数排序适用于小范围数的特点);

    11.2、动图演示

    b300e44faa8792cba036e309ee8eeb6e.gif

    11.3、代码实现

    /**
    

    11.4、算法分析

    最佳情况:T(n) = O(n * k) 最差情况:T(n) = O(n * k) 平均情况:T(n) = O(n * k)。基数排序有两种方法:MSD 从高位开始进行排序 LSD 从低位开始进行排序 。基数排序 vs 计数排序 vs 桶排序。这三种排序算法都利用了桶的概念,但对桶的使用方法上有明显差异:

    • 基数排序:根据键值的每位数字来分配桶
    • 计数排序:每个桶只存储单一键值
    • 桶排序:每个桶存储一定范围的数值

    版权声明:本文为CSDN博主「一杯甜酒」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。

    原文链接:https://blog.csdn.net/u012562943/article/details/100136531

    展开全文
  • 堆排序(heap sort)思想:借助于堆这数据结构进行排序。 堆排序属于比较排序,不稳定。 声明 :堆的操作,包括插入,拔掉堆顶,上浮,下滤等等过程,自己画图辅助理解。 下面贴出百度百科堆的定义: 堆满足两...
  • 堆排序

    2017-01-13 19:26:20
    堆排序堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是
  • 一般来说,涉及到topN类的问题时,我们首先想到的是采用分治法:先随机取一数其他数与它比较,如果前一部分总数大于100(这里架设找出前100条),那就继续在前一部分进行partition寻找;如果前一部分的数小于100...
  • 选择排序的主要两种方法:直接选择排序、堆排序。本文内容主要针对堆排序。在本文最后的练习的中,以举例子说明该排序方法,配以图文,讲解详细(含408真题)。【考研复习:数据结构】查找(不含代码篇)_住在阳光的...
  • 直接插入排序就是把待排序记录按其关键码值的大小逐个插入到一已经排好序的有序序列中,直到所有的记录插入完为止,得到一新的有序序列,直接插入排序的时间复杂度为O(N^2) void InsertSort(int*a, int n) { ...
  • 希尔排序法的基本思想是:先选定一整数,把待排序文件中所有记录分成组,所有距离为的记录分在同一组内,并每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好...
  • 要求:1)至少采用三种方法实现上述问题求解(提示,可采用的方法有插入排序、希尔排序、起泡排序、快速排序、选择排序、堆排序、归并排序)。并把排序后的结果保存在不同的文件中。2)统计每一种排序方法的性能(以上机...
  • 排序算法—堆排序

    2020-04-17 08:17:15
    堆排序 堆排序也是选择排序的一种,起源于罗伯特·弗洛伊德。它的特点是,排序过程中使用了堆这种数据结构,利用堆的特性来选择最小(大)的元素。 题目描述 给出一组数据,根据由小到大顺序输出。 输入要求: 输入...
  • 通过本文你将了解:概述hash映射bitmapTrie树数据库索引倒排索引外排序simhash跳跃链表MD5MapReduce01 概述 大数据必然涉及海量数据,所谓海量数据,就是数据量太大,要么在短时间内无法计算出结果,要么因为数据太...
  • 堆排序和归并排序

    千次阅读 2017-08-15 11:05:57
    堆排序与快速排序,归并排序一样都是时间复杂度为O(n*logn)的几种常见排序方法。学习堆排序前,先讲解下什么是数据结构中的堆。 堆的定义:n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系之一时,称之为堆。...
  • C++实现堆排序算法

    千次阅读 2018-10-30 07:21:49
    ② 再将关键字最大的记录R[1](即顶)和无序区的最后一个记录R[n]交换, 由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key 。 ③ 由于交换后新的根R[1]可能违反性质,故应将当前无序...
  • 数组排序——堆排序

    2018-04-18 11:16:34
    数组排序——堆排序1、数组...(1)用大根堆排序的基本思想: A:先将初始文件R[1..n]建成一大根堆,此堆为初始的无序区。 B:再将关键字最大的记录R[1](即堆顶)和无序区的最后一 记录R[n]交换,由此得到...
  • shell排序和堆排序

    2022-08-15 18:30:29
    堆排序建堆时有两种情况,大顶堆或者小顶堆,在n个节点的堆进行排序时,只需直接将堆的第一元素和最后一元素交换位置,并从第一元素开始向下调整为n-1元素。先将整个待排序记录分割成若干子序列,分别...
  • 经典算法之四:堆排序

    千次阅读 2017-01-04 21:58:39
    堆排序 Heap Sort  堆排序是一种选择排序,其时间复杂度为O(nlogn)。 堆的定义  n个元素的序列{k1,k2,…,kn}当且仅当满足下列关系之一时,称之为堆。  情形1:ki 2i 且ki 2i+1 (最小化堆或小...
  • 5 直接选择的优化版之堆排序 自学成才的计算机科学家 Flody 堆排序的基本概念 堆排序的算法思想 堆排序是如何工作的 应用堆排序得到升序排序的例子 算法评价 6 总结 1 你会学到什么?彻底弄明白常用的排序算法的...
  • 选择排序——堆排序

    2018-03-15 16:12:01
    预备知识堆排序 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为O(nlogn),它也是不稳定排序。首先简单了解下堆结构。堆 堆是具有以下性质的完全...
  • 堆排序-以小根堆为例

    千次阅读 2020-09-29 10:57:49
    文章目录前言一、什么是堆二、堆排序过程1.创建堆2.堆排序总结前言一、pandas是什么?二、使用步骤1.引入库2.读入数据总结 前言 刷力扣题,遇到堆排序,考研完后就没接触数据结构,忘的差不多了,现在重现拾起来。 ...
  • 堆排序详解

    2018-01-30 21:05:09
    堆排序 堆排序利用堆积树所设计的排序算法,本质上是利用完全二叉树中双亲结点和孩子结点之间的内在关系做选择排序。可以利用数组的特点快速定位指定索引的... 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大
  • 希尔排序与堆排序

    千次阅读 2017-04-03 13:11:57
    希尔排序 堆排序
  • 排序算法之堆排序(Heap Sort)——C语言实现

    万次阅读 多人点赞 2018-08-21 16:44:21
    堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。 算法分析 在学习堆排序之前我们要先了解堆这种数据结构。 堆的定义如下:n个元素的序列{k1,k2,···,kn}当且...
  • 堆排序-C语言实现

    万次阅读 多人点赞 2018-06-27 00:49:03
    堆排序就是利用堆这种数据结构进行排序的算法,堆排序属于选择排序。 堆是一棵顺序存储的完全二叉树 堆排序的时间复杂度: O(nlogn),属于不稳定排序。 大根堆 小根堆 每节点的值大于等于孩子节点得堆...
  • 堆排序算法设计与分析

    千次阅读 2016-05-11 17:04:36
    堆排序(HeapSort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。堆分为大根堆和小根堆,是完全二叉树。大根堆要求父结点的值大于或等于子结点的值,小根堆相反。根据大根堆的性质,我们...
  • 堆排序之-大顶堆

    千次阅读 2018-10-14 15:14:34
    一、堆排序的概念 堆的定义: 设有n个元素的序列当且仅当满足下述关系之一时,称之为堆。 (1) 且 或者是 (2) 且  解释:如果让满足以上条件的元素序列()依次顺序排成一颗完全二叉树,则此树的特点是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 61,000
精华内容 24,400
热门标签
关键字:

对n个记录的文件进行堆排序