精华内容
下载资源
问答
  • 简介选择排序的基本思想是:每一趟(如i趟)在后面 n-i+1 ( i = 1 , 2, ...., n-1) 个待排序元素中选取关键字最小的元素,作为有序子序列的i个元素,直到 n-1 趟做完,待排序元素只剩下一个,就不用再选了。...

        此为第二篇,选择排序算法:简单选择排序、堆排序。

    简介

    选择排序的基本思想是:每一趟(如第i趟)在后面 n-i+1 ( i = 1 , 2, ...., n-1) 个待排序元素中选取关键字最小的元素,作为有序子序列的第i个元素,直到第 n-1 趟做完,待排序元素只剩下一个,就不用再选了。

        基于选择的排序算法主要介绍简单选择排序排序

    一.简单选择排序

    简单选择排序算法的思想:假设排序表 L [1...n ],第i趟排序即从 L[i...n] 选择关键字最小的元素与L(i) 交换,每一趟排序可以确定一个元素的最终位置,这样经过n-1趟排序就可使得整个排序表有序。

    若表L={46859},我们以min来选择较小元素的小标ij结合来遍历数组。初始的时候mini都指向L首元素,j指向i+1元素,然后j开始从右向左进行遍历L,若L(j)>L(min),min=j,直至j走完整个L表;i再向右走,这样循环到i走到最后一个元素就完成了排序,过程如下图所示:

    6f557a08368f31d536f0ca9e305b9504.png

    1.例程

    /********************************* 选择排序 *********************************/#include #include #include void SelectSort(int *data, int length){    int i, j, min, temp;    for(i = 0; i     {        min = i;                               //选择一个序号        for(j = i+1; j             if(data[j]                 min = j;                          temp = data[i];                      //交换        data[i] = data[min];        data[min] = temp;    }}int main() {    int i = 0;    int data[] = {23, 64, 24, 12, 9, 16, 53, 57};    int temp[] = {0};    int length = sizeof(data) / sizeof(int);    SelectSort(data, length);    for (i = 0;i         printf("%4d", data[i]);    }    printf("\n");}

    2.性能分析

    2.1空间复杂度

    仅使用常数个辅助单元,故空间效率为O(1);

    2.2时间复杂度

    在简单选择排序过程中,元素移动的操作次数很少,不会超过 3(n-1) ,若表已有序,最好的情况是移动0次;但元素间比较的次数与序列的初始状态无关,始终是n(n-1)/2次。

    因此时间复杂度始终为:O(n2)

    2.3稳定性

    在第i趟找到最小元素后,和第i元素交换,可能会导致第i个元素与其含有相同关键字元素的相对位置发生改变。例如,表L = {2, 2, 1} 经过趟排序后 L={1, 2, 2} 最终排序序列也是L={1, 2, 2},显然,22的相对次序己发生变化。

    因此简单选择排序是一种不稳定的排序方法。

    二.堆排序

    堆排序是根据堆的数据结构设计的一种排序,而堆可分为大根堆(每个结点的值都大于其左孩子和右孩子结点的值)和小根堆(每个结点的值都小于其左孩子和右孩子结点的值),这两种堆都是一棵完全二叉树。若序列L={45, 78, 09, 32, 87, 65, 53, 17},则大小根堆如下图:

    531e0b033e4557597e795213a9ab58ee.png

    将上面的大小跟堆进行映射可得到:

    大根堆序列L(1~8)={87, 45, 78, 32, 17, 65, 53, 09}

    小根堆序列L(1~8)={09, 17, 32, 53, 65, 45, 78, 87}

    取父结点索引:i左孩子索引:2i右孩子索引:2i+1

    则以上大小根堆满足一下性质(即堆的性质):

    1<= i <= n/2

    L(i) >= L(2i) && L(i) >= L(2i+1)

    L(i) =< L(2i) && L(i) =< L(2i+1)

    堆排序的思路为:

    1.首先将存放在L[1....n]中的n个元素建成初始堆,由于堆本身的特点(以大顶堆为例),堆顶元素就是最大值。

    2.输出堆顶元素后,将堆底元素送入堆顶,此时根结点已不满足大顶堆的性质,堆被破坏,将堆顶元素向下调整使其继续保持大顶堆的性质,再输出堆顶元素

    3.如此重复,直到堆中仅剩一个元素为止。

    可见堆排序主要步骤为:1.将无序序列构造成初始堆。2.输出堆顶元素后,将剩余元素调整成新的堆。

    1.将无序序列构造成初始堆

    n个结点的完全二叉树,最后一个结点是第 n/2 个结点的孩子。

    1.1对第 n/2 个结点为根的子树筛选(对于大根堆,若根结点的关键字小于左右孩子中关键字较大者,则交换),使该子树成为堆。

    1.2之后向前依次对各结点 ( n/2 - 1 ~ 1) 为根的子树进行筛选,看该结点值是否大于其左右子结点的值,若不大于,则将右子结点中的较大值与之交换,交换后可能会破坏下一级的堆,于是继续采用上述方法构造下一级的堆,直到以该结点为根的子树构成堆为止

    1.3反复利用上述调整堆的方法建堆,直到根结点。

    步骤如下图所示:

    1ff4d4d88c0498d608a68933b24f8212.png

    (a) 初始时调整L(4)子树,09 < 32,交换,交换后满足堆的定义;

    (b) 向前调整L(3)子树,78 < 左右孩子的较大者87,交换,交换后满足堆的定义;

    (c) 向前调整L(2)子树,17 < 左右孩子的较大者45,交换后满足堆的定义;

    (d) 向前调整至根结点L(1)53 < 左右孩子的较大者87,交换,交换后破坏了L(3)子树的堆;采用上述方法对L(3)进行调整,53 < 左右孩子的较大者78 ,交换;

    (e) 至此该完全二叉树满足堆的定义。

    2.输出堆顶元素后,将剩余元素调整成新的堆

    输出堆顶元素后,堆的性质被破坏,需要向下进行筛选。步骤如下图所示:

    f132f028887ae68acb4a1d6e61a17311.png

        将 09 右孩子的较大者 78 交换,交换后破坏了L(3)子树的堆,继续对L(3)子树向下筛选;将 09 和左右孩子的较大者 65 交换,交换后得到了新堆。

    1.例程

    #include #include #include void display(int array[], int size) {    for (int i = 0; i         printf("%d ", array[i]);    }    printf("\n");}void swap(int array[], int x, int y) {    int key  = array[x];    array[x] = array[y];    array[y] = key;}// 从大到小排序// void Down(int array[], int i, int n) {//     int child = 2 * i + 1;//     int key   = array[i];//     while (child //         if (array[child] > array[child + 1] && child + 1 //             child++;//         }//         if (key > array[child]) {//             swap(array, i, child);//             i = child;//         } else {//             break;//         }//         child = child * 2 + 1;//     }// }// 从小到大排序void Down(int array[], int i, int n) { // 最后结果就是大顶堆    int parent = i;                    // 父节点下标    int child  = 2 * i + 1;            // 子节点下标    while (child         if (array[child]             child++;        }        if (array[parent]             swap(array, parent, child);     // 交换父节点和子节点            parent = child;                 // 子节点下标 赋给 父节点下标        }        child = child * 2 + 1; // 换行,比较下面的父节点和子节点    }}void BuildHeap(int array[], int size) {    for (int i = size / 2 - 1; i >= 0; i--) { // 倒数第二排开始, 创建大顶堆,必须从下往上比较        Down(array, i, size);                 // 否则有的不符合大顶堆定义    }}void HeapSort(int array[], int size) {    printf("初始化数组:");    BuildHeap(array, size); // 初始化堆    display(array, size);   // 查看初始化结果    for (int i = size - 1; i > 0; i--) {        swap(array, 0, i); // 交换顶点和第 i 个数据                           // 因为只有array[0]改变,其它都符合大顶堆的定义,所以可以从上往下重新建立        Down(array, 0, i); // 重新建立大顶堆        printf("排序的数组:");        display(array, size);    }}int main() {    int i = 0;    int data[] = {23, 64, 24, 12, 9, 16, 53, 57};    int temp[] = {0};    int length = sizeof(data) / sizeof(int);    HeapSort(data, length);    for (i = 0;i         printf("%4d", data[i]);    }    printf("\n");}

    2.性能分析

    2.1适用性

    堆排序适合关键字较多的情况(如 n>1000)。

    例如,在一亿个数中选出前 100 个最大值?首先用一个大小为100 的数组,读入前 100 个数,建立小顶堆,而后依次读入余下的数,若小于堆顶则舍弃,否则用该数取代堆顶并重新调整堆,待数据读取完毕,堆中100个数即为所求。

    2.2空间复杂度

    仅使用常数个辅助单元,故空间效率为O(1);

    2.3时间复杂度

    建堆时间为O(n),之后有 n-1 次向下调整操作,每次调整的时间复杂度为O(h)(h为堆的高度,h=log(n+1) 约为 log2n )。

    因此在最好、最坏和平均情况下,堆排序的时间复杂度为O(nlog2n)

    2.4稳定性

    进行筛选时,可能会把后面相同关键字的元素调整到前面。例如,表L = {1, 2, 2},构造初始推时可能将2交换到堆顶,此时L={2, 1, 2 } ,最终排序序列为L={1, 2, 2},显然,22的相对次序己发生变化。

    因此堆排序是一种不稳定的排序方法。

    下一篇,第三篇,插入排序算法:直接插入排序、希尔排序。

    参考:

    《王道数据结构》

    CSDN博主:有人_295 的《堆排序算法--C/C++》

    展开全文
  • 高人能不能讲述一下初始堆和排序的区别是什么呀? 首先建立完全二叉树 45 28 49 16 37 82 56 75 从n/2个节点开始选择,第一趟,16比75小,不换.到n/2-1个节点,49和82、56比,49小,也不换.到n/2-2个结点,28和16、...

    这样一组数 45 28 49 16 37 82 56 75初始堆后,利用堆排序怎么排,规律是什么?

    首先建立完全二叉树
    45
    28 49
    16 37 82 56
    75

    从n/2个节点开始选择,第一趟,16比75小,不换.到n/2-1个节点,49和82、56比,49小,也不换.到n/2-2个结点,28和16、37比,16小,变成
    45
    16 49
    28 37 82 56
    75

    45和16、49比,16最小,换

    16
    45 49
    28 37 82 56
    75

    45和28、37比,28最小

    16
    28 49
    45 37 82 56
    75

    最小初始堆建好了,到输出,首先75和16换,输出16

    75
    28 49
    45 37 82 56
    16

    将剩下的元素建成堆

    28
    37 49
    45 75 82 56
    16

    56和28换,输出28

    56
    37 49
    45 75 82 28
    16

    再建初始堆

    37
    45 49
    56 75 82 28
    16

    82和37换,输出37

    82
    45 49
    56 75 37 28
    16

    建初始堆

    45
    56 49
    82 75 37 28
    16

    75和45换,输出45

    75
    56 49
    82 45 37 28
    16

    建初始堆

    49
    56 75
    82 45 37 28
    16

    82和49换,输出49

    82
    56 75
    49 45 37 28
    16

    建初始堆

    56
    82 75
    49 45 37 28
    16

    75和56换,输出56

    75
    82 56
    49 45 37 28
    16

    建初始堆

    75
    82 56
    49 45 37 28
    16

    82和75换,输出75

    82
    75 56
    49 45 37 28
    16

    输出82

    82
    75 56
    49 45 37 28
    16
    得到有序序列82,75,56,49,45,37,28,16,是按从小到大输出的,如果要按从大到小输出,建初始堆的时候,建最大堆就可以了,规律似乎看不出来

    展开全文
  • 排序算法 堆排序

    2014-05-10 15:40:31
    第一趟排序,将顶元素 A[0] 和堆底元素 A[n-1]进行交换,然后调用AdjustDown对顶元素进行向下调整,使剩余的前n-1个元素还是。然后使顶元素与A[n-2]交换,在进行向下调整。直到最后只剩下顶元素。

    堆排序使用最大堆。堆排序:将初始序列构造成最大堆; 第一趟排序,将堆顶元素 A[0] 和堆底元素 A[n-1]进行交换,然后调用AdjustDown对堆顶元素进行向下调整,使剩余的前n-1个元素还是堆。然后使堆顶元素与A[n-2]交换,在进行向下调整。直到最后只剩下堆顶元素。


    template <class T>
    void AdjustDown(T heap[],int r,int j){
    	T temp = heap[r];
    	int child = 2 * r + 1;
    	while(child < j ){
    		child = heap[child] < heap[child+1] ? (child+1) : child;
    		if(temp < heap[child]){
    			heap[r] = heap[child];
    			heap[child] = temp;
    			r = child ;
    			child = 2 * r + 1;
    			temp = heap[r];
    		}else
    			break;
    	}
    }
    template <class T>
    void CreateHeap(T heap[],int n){
    	for(int i = n/2 - 1;i>-1;i--)
    		AdjustDown(heap,i,n-1);
    }
    template <class T>
    void swap(T &a, T &b){
    	T temp = a;
    	a = b;
    	b = temp;
    }
    template <class T>
    void HeapSort(T A[],int n){
    	CreateHeap(A,n);
    	for(int i = n-1 ;i > 0 ; i--){
    		swap(A[0],A[i]);
    		AdjustDown(A,0,i-1);
    	}
    }
    
    int main()
    {
    	int A[7] = {99,36,68,72,12,48,02};
    	HeapSort(A,7);
    	return 0;
    }


    展开全文
  • SCAU-8644堆排序 C++

    2020-06-12 16:41:47
    第一行:初始建堆后的结果 其后各行输出交换堆顶元素并调整堆的结果,数据之间用一个空格分隔 思路: 构建堆和调整堆的方法相同。所以从输出格式来看,其实是将每一次调整堆之后的结果进行输出,排序完成之后再多...

    Description

    用函数实现堆排序,并输出每趟排序的结果

    输入格式

    第一行:键盘输入待排序关键的个数n
    第二行:输入n个待排序关键字,用空格分隔数据

    输出格式

    第一行:初始建堆后的结果
    其后各行输出交换堆顶元素并调整堆的结果,数据之间用一个空格分隔

    思路:
    构建堆和调整堆的方法相同。所以从输出格式来看,其实是将每一次调整堆之后的结果进行输出,排序完成之后再多调整一次堆(最后一次什么都没有调整到,只是方便写代码用来输出结果)即可。

    调整堆的方法:
    从最后一个非子叶的节点(在数组上表示为:i=len/2)开始,将该根节点和其两个子节点三者中最大的一个放在该根节点上,然后对该根节点的两个字节点再进行一次调整堆的操作,直到根节点没有子节点为止。(这里是一个递归的操作)。每调整完一个节点后,i - -,继续调整上一个根节点。
    (这部分需要理清楚树的节点之间的关系,可以画一个图标上序号来看一下)。

    每次调整完堆之后,将堆的根节点和最后一个节点交换,然后再继续调整。

    代码如下:

    #include <iostream>
    #include <cstring>
    #include <algorithm>
    #include <math.h>
    #include <cstdio>
    #include <string>
    typedef long long ll;
    const int MAXL=10000+10;
    
    using namespace std;
    
    
    int a[MAXL]={0};
    int n;
    
    
    void printarr()
    {
        int i;
        for(i=1;i<=n;i++)
        {
            cout<<a[i]<<" ";
        }
        cout<<endl;
    }
    
    void adjust(int i,int len)
    {
        int j;
        if(a[i]<a[i*2+1]&&i*2+1<=len||a[i]<a[i*2]&&i*2<=len)//将该根节点和其两个子节点三者中最大的一个放在该根节点上//
        {
            if(a[i*2+1]>a[i*2]&&i*2+1<=len)     //如果不加i*2+1<=len这一条件,会将已经排好序的放在了最后的节点也算进来//
            {
                j=i*2+1;
            }
            else
            {
                j=i*2;
            }
            swap(a[i],a[j]);
        }
        if(i*2+1<=len)         //直到根节点没有子节点为止//
        {
            adjust(i*2+1,len); //然后对该根节点的两个字节点再进行一次调整堆的操作//
        }
        if(i*2<=len)
        {
            adjust(i*2,len);
        }
    }
    
    
    void heapsort(int len)
    {
    
        int i;
    
        for(i=len/2;i>=1;i--) //每调整完一个节点后,i - -,继续调整上一个根节点。//
        {
            adjust(i,len);
        }
        printarr();
        swap(a[1],a[len]);      //每次调整完堆之后,将堆的根节点和最后一个节点交换,然后再继续调整。//
        if(len>1)               
        {
            heapsort(len-1);
        }
    }
    
    
    
    
    
    int main()
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        heapsort(n);
    }
    
    
    展开全文
  • 1、选择排序 1.1选择排序介绍 选择式排序:是从欲排序的数据中,按指定的规则选出某元素,再依...i趟排序(i=1,2,3…n-1)开始时,当前有序区无序区分别为R[1…i-1]R(i…n)。该趟排序从当前无序区中-选出关键
  • 排序算法—选择排序

    2019-08-31 10:09:49
    【选择排序】 1.选择排序 选择排序的基本思想:每一趟从待排序记录中选出关键字最小的记录,按顺序放到已经排好序的子序列中,直到全部记录排序完毕。 选择排序算法的应用,包括直接... 1趟排序:在无序区R[1...
  • // 对L.r[low]——L.r[high] 子序列进行一趟快速排序,返回分界线位置,即枢轴 L.r[0]=L.r[low]; int pivotkey=L.r[0].key; while (low) { while (low[high].key>=pivotkey) { high--; } L.r[low]=...
  • 排序之选择排序

    热门讨论 2015-10-04 14:45:51
    排序分为5类,本篇文章主要是研究选择排序,选择...第一趟:  如上图初始状态为 3820 46 38 74 91 12 25,他们是带排序的记录,从待排序的记录中选择出最小的为12, 按顺序存放在已排好序的记录后,因为还没有排好的序
  • 选择排序有直接选择排序和堆排序。基本思想:每一趟在待排序的记录中选出关键字最小的元素,依次存放在已排好序的序列的最后。直到所有元素都好排好序为止。 1.1.直接选择排序 算法思想: 每次从待排序的无序区中...
  • 【数据结构之排序6】直接选择排序

    千次阅读 2013-10-21 17:04:53
    选择排序(Selection Sort)的基本思想是:每一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。 本节介绍第一种选择...
  • 选择排序的基本思想是:每一趟(如i趟)在后面n-i+1(i = 1, 2, …, n-1)个待排序元素中选取关键字最小的元素,作为有序子序列的i个元素,直到n-1趟做完,待排序元素只剩下1个,就不用再选了。堆排序是重点 ...
  • 选择排序的基本思想是:每一趟在n-i+1(i=1,2,…n-1)个记录中选取关键字最小的记录作为有序序列中i个记录。基于此思想的算法主要有简单选择排序、树型选择排序和堆排序。 n个记录的直接选择排序可经过n-1趟...
  • 基本原理:直接选择排序,在第 i 趟选择排序是指通过 n-i 次关键字的比较,从n-i+1 个记录中选出关键字最小的记录,并和第 i 个记录交换,直到排序完算法分析:无论序列初始状态如何,在第 i 趟排序中选出最小关键字...
  • 一趟从待排序的记录中选出关键字最小的记录,顺序放在已排好序的子文件的最后,直到全部记录排序完毕;选择在排序分为两种:直接选择排序(或称简单选择排序)和堆排序。 直接选择排序 数组分成有序区无序区,初始...
  • 典型排序算法整理

    2010-05-25 17:22:00
    典型排序 本文包括直接插入排序、冒泡排序、希尔排序堆排序和快速排序。 ,直接插入排序1、基本思想 假设待排序的记录存放在数组R[1..n]中。初始时,R[1]自成1个有序区,无序区为R[2..n]。从i=2起直至i=n为止...
  • 3、如果上述8个整数按照升序输入,即k1={ 2 , 12 , 12 , 21 , 30 , 33 , 45 , 68 },输出各种排序算法每一趟排序的结果,观察关键字次序的变化。 4、如果上述8个整数按照降序输入,即k2={ 68 , 45 , 33 , 30 , 21 ...
  • 2.27专项测试补题

    2020-02-27 15:40:54
    排序趟数与初始状态无关的有:(除了快速排序和优化的冒泡,其他都是) 算法复杂度与初始状态无关的有:堆排序、归并排序、选择排序、基数排序。 元素总比较次数与初始状态无关的有:选择排序、基数排序。 ...
  • 范例1-85 一趟快速排序的改进算法 248 ∷相关函数:QuickSort函数 1.5.10 简单选择排序 250 范例1-86 简单选择排序 250 ∷相关函数:SelectSort函数 1.5.11 箱子排序 252 范例1-87 箱子排序 252 ∷相关函数:...
  • 数据结构题

    2012-12-27 16:58:40
    请写出排序过程中得到的初始堆和前三的序列状态。 初始堆:_94,87,。。。_______ 1:{94},87,72,61,58,23,16,5 2:{94,87},72,58,61,5, 23,16, 4.在关键字序列(07,12,15,18,27,32,...
  • ThreadLocal通常用来共享数据,当你想在多个方法中使用某个变量,这个变量是当前线程的状态,其它线程不依赖这个变量,你第一时间想到的就是把变量定义在方法内部,然后再方法之间传递参数来使用,这个方法能解决...
  • //标记一趟排序中是否发生了元素交换  for (j = 0; j < i; j++)  {<!-- -->  if (list->D[j].key > list->D[j + 1].key)  {<!-- -->  Swap(list-&...
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    B. 球最大值函数max:通过单链表的一趟遍历,在单链表中确定值最大的结点; C. 统计函数number:统计单链表中具有给定值x的所有元素数量; D. *建立函数create:根据一维数组a[n]建立一个单链表,使...
  • C语言通用范例开发金典.part2.rar

    热门讨论 2012-08-31 14:18:18
    范例1-85 一趟快速排序的改进算法 248 ∷相关函数:QuickSort函数 1.5.10 简单选择排序 250 范例1-86 简单选择排序 250 ∷相关函数:SelectSort函数 1.5.11 箱子排序 252 范例1-87 箱子排序 252 ∷相关函数:...
  • C 开发金典

    2013-06-20 16:20:03
    范例1-85 一趟快速排序的改进算法 248 ∷相关函数:QuickSort函数 1.5.10 简单选择排序 250 范例1-86 简单选择排序 250 ∷相关函数:SelectSort函数 1.5.11 箱子排序 252 范例1-87 箱子排序 252 ∷相关函数:...
  • class SLinkedList{//插入删除操作分为头尾中间,对于头,前个为空,对于尾,后一个结点为空,需要分别对待. public class book{ protected int number; protected String title;...

空空如也

空空如也

1 2
收藏数 25
精华内容 10
关键字:

初始堆和第一趟排序