精华内容
下载资源
问答
  • 堆排序

    2016-06-22 21:21:36
    堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 (1)用大根堆排序的基本思想 ① 先将初始文件R[1..n]建成一大根堆...
    堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
    (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]调整为堆。
    ……
    直到无序区只有一个元素为止。
    (2)大根堆排序算法的基本操作:
    ①建堆,建堆是不断调整堆的过程,从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)[2] 

    注意

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

    特点

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

    平均性能

    O(N*logN)。

    其他性能

    由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。
    堆排序是就地排序,辅助空间为O(1).
    它是不稳定的排序方法。(排序的稳定性是指如果在排序的序列中,存在前后相同的两个元素的话,排序前 和排序后他们的相对位置不发生变化)
    下边是代码:
    void AdjustDown(int* a, int parent,int size)	//向下调整
    {
    	int child = parent * 2 + 1;
    	while (child < size)
    	{
    		if (child + 1 < size && a[child] > a[child + 1])
    		{
    			child++;
    		}
    		if (a[child] < a[parent])
    		{
    			swap(a[child], a[parent]);
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else
    		{
    			break;
    		}
    	}
    }
    //建小堆
    void BuildHeap(int* a,int size)
    {
    	for (int i = (size - 2) / 2; i >= 0; i--)
    	{
    		swap(a[0], a[i]);
    		AdjustDown(a, i, size);
    	}
    }
    
    void HeapSort(int* a, int size)
    {
    	BuildHeap(a, size);
    	for (int i = size - 1; i >= 0; i--)
    	{
    		swap(a[0], a[i]);
    		AdjustDown(a, 0, i);
    	}
    }
    
    void Print(int* a, int size)
    {
    	for (int i = 0; i < size; i++)
    	{
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }

    测试代码
    void Test2()
    {
    	int a[] = { 1, 0, 3, 5, 8, 2, 6, 7, 4, 9, 10 };
    	int len = sizeof(a) / sizeof(a[0]);
    	HeapSort(a, len);
    	Print(a, len);
    }
    int main()
    {
    	//Test();
    	Test2();
    	return 0;
    }


    展开全文
  • 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

    展开全文
  • 数组排序——堆排序

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

    数组排序——堆排序


    1、数组排序之堆排序:

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

    (1)用大根堆排序的基本思想:

            A:先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区。

            B:再将关键字最大的记录R[1](即堆顶)和无序区的最后一个 记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n], 且满足R[1..n-1].keys≤R[n].key

            C:由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。

            D:然后再次将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]调整为堆。

            E:直到无序区只有一个元素为止。   

    (2)大根堆排序算法的基本操作:

            A:初始化操作:将R[1..n]构造为初始堆;

            B:每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。

    2、代码演示

    package cn.itcast_01;
    
    public class ArraySort_heapSort {
    	public static void main(String[] args) {
    		// 定义一个数组
    		int[] arr = { 47, 35, 26, 26, 18, 7, 13, 19 };
    		// int[] arr = { 11, 3, 454, 231, 87, 334, 0, 1, 3422, 55, 10, 4324 };
    		// int[] arr = { 24 };
    		// int[] arr = {};
    		System.out.println("排序前:");
    		printArray(arr);
    
    		// 调用堆排序算法
    		int n = arr.length;
    		heapSort(arr, n - 1);
    
    		System.out.println("排序后:");
    		printArray(arr);
    	}
    
    	// 堆排序heapSort()+sift()
    	// 调整算法sift()
    	public static void sift(int r[], int k, int m) {
    		// 你要调整的结点是k
    		int i = k;
    		// 堆中最后一个结点的编号是m,j是i的左孩子结点
    		int j = 2 * i + 1;
    		int temp = 0;
    		while (j <= m) {
    			if (j < m && r[j] < r[j + 1])
    				j++;
    			if (r[i] > r[j])
    				break;
    			else {
    				temp = r[i];
    				r[i] = r[j];
    				r[j] = temp;
    				i = j;
    				j = 2 * i + 1;
    			}
    		}
    	}
    
    	// 堆排序heapSort()
    	// n是数组下标的最大值:7
    	public static void heapSort(int r[], int n) {
    		int temp = 0;
    		// 建立大顶堆
    		for (int i = n / 2; i >= 0; i--) {
    			sift(r, i, n);
    		}
    
    		// 逐步取出堆顶,再调整堆
    		for (int i = 0; i < n; i++) {
    			temp = r[0];
    			r[0] = r[n - i];
    			r[n - i] = temp;
    			sift(r, 0, n - i - 1);
    		}
    
    	}
    
    	// 数组遍历
    	public static void printArray(int[] arr) {
    		System.out.print("[");
    		for (int i = 0; i < arr.length; i++) {
    			if (i == arr.length - 1) {
    				System.out.print(arr[i]);
    			} else {
    				System.out.print(arr[i] + ", ");
    			}
    		}
    		System.out.println("]");
    	}
    }
    




    展开全文
  • 先了解堆排序概念:堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 (1)用大根堆排序的基本思想 ① 先将初始文件R[1.....

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

    (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]调整为堆。

    ……

    直到无序区只有一个元素为止。

    (2)大根堆排序算法的基本操作:

    ① 初始化操作:将R[1..n]构造为初始堆;

    ② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。

    时间复杂度O(N*logN)

    #include <iostream>
    #include <string>
    #include <vector>
    #include <stdio.h>
    #include <sys/types.h>
    #include <sys/wait.h>
    #include <unistd.h>
    
    using namespace std;
    
    //创建大根堆,即父节点大于两个子节点
    void MaxHeapCreate(int array[],int n,int length) {
    int temp;
    int maxChild;
    for(temp = array[n]; 2*n+1 < length ; n = maxChild) {
    maxChild = 2*n+1;
    if(maxChild<length-1 && array[maxChild+1]>array[maxChild] )
    maxChild++;
    if( temp < array[maxChild] ) {
    array[n] = array[maxChild];
    array[maxChild] = temp;
    } else {
    break;
    }
    }
    }
    
    void HeapSort(int array[],int length) {
    int temp;
    int i;
    //由底下第一个非叶子节点开始逐个往上创建大根堆,使每个节点满足大根堆
    //精髓部分,这步保证堆顶为最大
    for( i = length/2 -1 ; i >= 0; i--) {
    MaxHeapCreate(array,i,length);
    }
    for( i = length-1; i > 0 ; i-- ) {
    temp = array[0];
    array[0] = array[i];
    array[i] = temp;
    MaxHeapCreate(array,0,i);
    }
    
    }
    
    void findFirstN(int array[],int length,int result[],int n) {
    int temp;
    int i,j;
    for( i = length/2-1 ; i>=0 ; i-- ) {
    MaxHeapCreate(array,i,length);
    }
    for( i = length-1,j=0; j<n && i > 0 ; i--) {
    result[j++] = array[0];
    temp = array[0];
    array[0] = array[i];
    array[i] = temp;
    MaxHeapCreate(array,0,i);
    }
    }
    
    template<typename T>
    int BinSearch(T array[],int length,T key) {
    int low = 0;
    int high = length - 1;
    int mid=0;
    if(array[low] == key)
    return low;
    if(array[high] == key)
    return high;
    while(low<=high) {
    mid = low + ((high-low)/2);
    if( array[mid] == key ) {
    return mid;
    } else if( array[mid] > key ) {
    high = mid - 1;
    } else
    low = mid + 1;
    }
    if(low>high)
    return -1;
    }
    
    int main()
    {
     
    printf("-=-=-=-=-=堆排序=-=-=-=-=-=-=-=-=-=-=\n");
    int array[]={12,15,8,33,96,76,38,22,9,23};
    int a_length = sizeof(array)/sizeof(int);
    HeapSort(array,a_length);
    
    while(a_length--)
    printf("array[%d]=%d\n",a_length,array[a_length]);
    printf("-=-=-=-=-=利用堆排序查找前n个最大元素=-=-=-=-=-=-=-=-=-=-=\n");
    int array2[]={12,15,8,33,96,76,38,22,9,23};
    int a2_length = sizeof(array2)/sizeof(int);
    int nn=3;
    int result[3];
    findFirstN(array2,a2_length,result,3);
    for(a2_length=0;a2_length<nn;a2_length++)
    printf("result[%d]=%d\n",a2_length,result[a2_length]);
    printf("-=-=-=-=-=二分查找=-=-=-=-=-=-=-=-=-=-=\n");
    printf("38的位置为:%d\n",BinSearch(array2,sizeof(array2)/sizeof(int),38));
    
    return 0;
    }


    展开全文
  • 堆排序详解

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

    2016-03-11 02:20:48
    堆排序今天实习电面腾讯算法,发现自己的知识结构的掌握有很...这篇文章中的堆排序,不是很好理解(我这样之前没认真学过的而言),我试图以更简单的方式解释堆排序。 - 1.什么是堆? - 2.堆的特点是什么? - 3.堆
  • 排序算法——堆排序

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

    2014-08-30 22:51:52
    堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。 (1)用大根堆排序的基本思想 ① 先将初始文件R[1..n]建成一大根堆...
  • 堆排序图片详解

    千次阅读 2016-10-09 15:23:27
    堆排序实例 首先,建立初始的堆结构如图: ...然后,交换堆顶的元素和最后一元素,此时最后一位置作为有序区... 堆排序方法对记录数较少的文件并不值得提倡,但对n较大的文件还是很有效的。因为其运行时

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 53,075
精华内容 21,230
关键字:

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