久久国产成人av_抖音国产毛片_a片网站免费观看_A片无码播放手机在线观看,色五月在线观看,亚洲精品m在线观看,女人自慰的免费网址,悠悠在线观看精品视频,一级日本片免费的,亚洲精品久,国产精品成人久久久久久久

分享

堆排序算法

 啟蒙彩魂 2010-12-12
堆的定義:    
       n個(gè)關(guān)鍵字序列Kl,,K2,,…,Kn稱為堆,,當(dāng)且僅當(dāng)該序列滿足如下性質(zhì)(簡稱為堆性質(zhì)):
   (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤)

   若將此序列所存儲(chǔ)的向量R[1..n]看做是一棵完全二叉樹的存儲(chǔ)結(jié)構(gòu),,則堆實(shí)質(zhì)上是滿足如下性質(zhì)的完全二叉樹:樹中任一非葉結(jié)點(diǎn)的關(guān)鍵字均不大于(或不小于)其左右孩子(若存在)結(jié)點(diǎn)的關(guān)鍵字。

       堆的這個(gè)性質(zhì)使得可以迅速定位在一個(gè)序列之中的最小(大)的元素.

       堆排序算法的過程如下:1)得到當(dāng)前序列的最小(大)的元素 2)把這個(gè)元素和最后一個(gè)元素進(jìn)行交換,這樣當(dāng)前的最小(大)的元素就放在了序列的最后,而原先的最后一個(gè)元素放到了序列的最前面 3)的交換可能會(huì)破壞堆序列的性質(zhì)(注意此時(shí)的序列是除去已經(jīng)放在最后面的元素),因此需要對(duì)序列進(jìn)行調(diào)整,使之滿足于上面堆的性質(zhì).重復(fù)上面的過程,直到序列調(diào)整完畢為止.
  1. // array是待調(diào)整的堆數(shù)組,i是待調(diào)整的數(shù)組元素的位置,length是數(shù)組的長度
  2. void HeapAdjust(int array[], int i, int nLength)
  3. {
  4.   int nChild, nTemp;

  5.   for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
  6.   {
  7.       // 子結(jié)點(diǎn)的位置是 父結(jié)點(diǎn)位置 * 2 + 1
  8.       nChild = 2 * i + 1;

  9.       // 得到子結(jié)點(diǎn)中較大的結(jié)點(diǎn)
  10.       if (nChild != nLength - 1 && array[nChild + 1] > array[nChild])
  11.           ++nChild;

  12.       // 如果較大的子結(jié)點(diǎn)大于父結(jié)點(diǎn)那么把較大的子結(jié)點(diǎn)往上移動(dòng),替換它的父結(jié)點(diǎn)
  13.       if (nTemp < array[nChild])
  14.       {
  15.           array[i] = array[nChild];
  16.       }
  17.       else    // 否則退出循環(huán)
  18.       {
  19.           break;
  20.       }
  21.   }

  22.   // 最后把需要調(diào)整的元素值放到合適的位置
  23.   array[i] = nTemp;
  24. }

  25. // 堆排序算法
  26. void HeapSort(int array[], int length)
  27. {
  28.   // 調(diào)整序列的前半部分元素,調(diào)整完之后第一個(gè)元素是序列的最大的元素
  29.   for (int i = length / 2 - 1; i >= 0; --i)
  30.   {
  31.       HeapAdjust(array, i, length);
  32.   }

  33.   // 從最后一個(gè)元素開始對(duì)序列進(jìn)行調(diào)整,不斷的縮小調(diào)整的范圍直到第一個(gè)元素
  34.   for (int i = length - 1; i > 0; --i)
  35.   {
  36.       // 把第一個(gè)元素和當(dāng)前的最后一個(gè)元素交換,
  37.       // 保證當(dāng)前的最后一個(gè)位置的元素都是在現(xiàn)在的這個(gè)序列之中最大的
  38.       Swap(&array[0], &array[i]);

  39.       // 不斷縮小調(diào)整heap的范圍,每一次調(diào)整完畢保證第一個(gè)元素是當(dāng)前序列的最大值
  40.       HeapAdjust(array, 0, i);
  41.   }
  42. }
復(fù)制代碼
一個(gè)測試及輸出的結(jié)果,在每次HeapAdjust之后顯示出來當(dāng)前數(shù)組的情況
before Heap sort:
71 18 151 138 160 63 174 169 79 78
// 開始調(diào)整前半段數(shù)組元素
71 18 151 138 160 63 174 169 79 78
71 18 151 169 160 63 174 138 79 78
71 18 174 169 160 63 151 138 79 78
71 169 174 138 160 63 151 18 79 78
174 169 151 138 160 63 71 18 79 78
// 開始進(jìn)行全局的調(diào)整
169 160 151 138 78 63 71 18 79 174
160 138 151 79 78 63 71 18 169 174
151 138 71 79 78 63 18 160 169 174
138 79 71 18 78 63 151 160 169 174
79 78 71 18 63 138 151 160 169 174
78 63 71 18 79 138 151 160 169 174
71 63 18 78 79 138 151 160 169 174
63 18 71 78 79 138 151 160 169 174
18 63 71 78 79 138 151 160 169 174
//*****************************************
/*
  Name:       堆排序算法
  Author:       zhuqing
  Des cription:       堆排序算法的過程演示 
  Date: 18-08-03 09:50
  Copyright:
*/
#include<stdio.h>
#define N 6
int k,j;
/* 建堆函數(shù) */
void build(int *a,int i,int n){
    int tmp;
    k=i;
    j=2*k+1;
    while(j<=n){
        if(j<n && a[j]<a[j+1])
            j++;
        if(a[k]>=a[j])break;
        tmp=a[k];
        a[k]=a[j];
        a[j]=tmp;       
        k=j;
        j=2*j+1;
    }
}
/* 打印數(shù)組函數(shù) */
void prnt(int *a,int n){
    int i;
    printf("\n");
    for(i=0;i<n;i++){
        printf("%3d",a[i]);
    }
    printf("\n");
}
/* 打印堆函數(shù) */
void prnthp(int *a,int b1,int b2){
    int size;
    int h=0,sum=0,item=1;
    int i,j,cnt,start,tmp;
    size=b2-b1+1;
    while(sum<=size){
        sum+=item;
        h++;
        item*=2;
    }
    item=1;
    cnt=0;
    start=b1;
    tmp=1;
    printf("\n--------------------------------------------\n");   
    printf("  堆:\n");
    while(1){
        for(i=0;i<h;i++){
                for(j=0;j<h-i;j++)
                                printf("    ");
                 for(j=0;j<i+1;j++)printf(" ");
                for(j=0;j<tmp;j++){
                                if(cnt>size-1)goto end;
                                printf("%4d",a[cnt++]);
                }
                printf("\n");
                tmp*=2;
        }      
     }
     end:
          printf("\n");        
          return;                 
}
/* 打印已排序數(shù)組函數(shù) */
void prntar(int *a,int b2,int len){
  int i;
  printf("  已排序:\n");
  for(i=0;i<b2;i++){
    printf("   ");
  }         
  for(i=b2;i<=len;i++){
    printf("%3d",a[i]);
  }         
  printf("\n");
}
main(){
    /* int a[]={-1,2,5,1,0,-3,-2,8,6}; */
    int a[50];
    int i;
    int tmp;
    int sum;
    int num;
    int len;
    printf("              堆排序\n");
    printf("\n============================================\n");   
    printf("\n  請(qǐng)輸入待排序數(shù)組個(gè)數(shù),以回車結(jié)束:\n");
    scanf("%3d",&len);   
    printf("\n  請(qǐng)輸入待排序數(shù)組,以回車結(jié)束:\n");
    for(i=0;i<len;i++)
        scanf("%3d",&a[i]);       
    tmp=1;sum=0;
    while(sum+tmp<=len){
        sum+=tmp;   
        tmp*=2;
    }
    printf("\n============================================\n");   
    printf("\n  初始數(shù)組:            \n");   
    prnt(a,len);   
    /* 建初始堆 */
    for(i=sum-1;i>=0;i--)
        build(a,i,len-1);      
    prnthp(a,0,len-1);     
    /* 改建堆 */
    for(i=0;i<len-1;i++){
        tmp=a[0];
        a[0]=a[len-1-i];
        a[len-1-i]=tmp;
        build(a,0,len-2-i);
        prnthp(a,0,len-2-i);
        prntar(a,len-1-i,len-1);       
    }
    printf("\n--------------------------------------------\n");
    printf("\n  排序結(jié)果:\n");       
    prnt(a,len);
    printf("\n============================================\n\n");   
    getch();
}
//*****************************************************************
 

堆排序簡介:

堆排序在最壞的情況下,,其時(shí)間復(fù)雜度也能達(dá)到O(nlogn),。相對(duì)于快速排序來說,這是它最大的優(yōu)點(diǎn),,此外,,堆排序僅需要一個(gè)記錄大小供交換用的輔助存儲(chǔ)空間。

堆排序的數(shù)據(jù)結(jié)構(gòu)是二叉堆,,二叉堆的特點(diǎn)有兩個(gè),,一個(gè)是它是一棵完全二叉樹,另一個(gè)是它的根結(jié)點(diǎn)小于孩子結(jié)點(diǎn),,所以我們很容易找到它的最小結(jié)點(diǎn)----根結(jié)點(diǎn),;當(dāng)然如果你想找到最大結(jié)點(diǎn)的話,那就要掃描所有的葉子結(jié)點(diǎn),,這是很費(fèi)時(shí)間的,,如果你想找的是最大結(jié)點(diǎn)的話,你最好把它弄成一個(gè)大頂堆,,即一棵根結(jié)點(diǎn)大于孩子結(jié)點(diǎn)的完全二叉樹,。

二叉堆通常用數(shù)組來實(shí)現(xiàn),它舍棄下標(biāo)0,,從下標(biāo)1開始置數(shù),,則很容易滿足,對(duì)于數(shù)組中任意位置i上的元素,,其左兒子的位置在2i上,,右兒子的位置在2i+1上,雙親的位置則在i/2上,。

 堆排序的算法之一是把數(shù)組構(gòu)建成二叉堆----這只要增添一個(gè)長度為n+1的輔助空間,然后把原數(shù)組的元素依次插入到二叉堆即可,。然后刪除二叉堆的根,,把它作為排序后的數(shù)組的第一個(gè)元素,然后使二叉堆的長度減1,并通過上移使得新得到的序列仍為二叉堆,再提取新二叉堆的第一個(gè)元素到新數(shù)組,。依此類推,,直到提取最后一個(gè)元素,新得到的數(shù)組就是排序后的數(shù)組,。

堆排序在最壞的情況下,,其時(shí)間復(fù)雜度也能達(dá)到O(nlogn)。相對(duì)于快速排序來說,,這是它最大的優(yōu)點(diǎn),,此外,堆排序僅需要一個(gè)記錄大小供交換用的輔助存儲(chǔ)空間,。

堆排序的數(shù)據(jù)結(jié)構(gòu)是二叉堆,,二叉堆的特點(diǎn)有兩個(gè),一個(gè)是它是一棵完全二叉樹,,另一個(gè)是它的根結(jié)點(diǎn)小于孩子結(jié)點(diǎn),,所以我們很容易找到它的最小結(jié)點(diǎn)----根結(jié)點(diǎn);當(dāng)然如果你想找到最大結(jié)點(diǎn)的話,,那就要掃描所有的葉子結(jié)點(diǎn),,這是很費(fèi)時(shí)間的,如果你想找的是最大結(jié)點(diǎn)的話,,你最好把它弄成一個(gè)大頂堆,,即一棵根結(jié)點(diǎn)大于孩子結(jié)點(diǎn)的完全二叉樹。

二叉堆通常用數(shù)組來實(shí)現(xiàn),,它舍棄下標(biāo)0,,從下標(biāo)1開始置數(shù),則很容易滿足,,對(duì)于數(shù)組中任意位置i上的元素,,其左兒子的位置在2i上,右兒子的位置在2i+1上,,雙親的位置則在i/2上,。

堆排序的算法之一是把數(shù)組構(gòu)建成二叉堆----這只要增添一個(gè)長度為n+1的輔助空間,然后把原數(shù)組的元素依次插入到二叉堆即可,。然后刪除二叉堆的根,把它作為排序后的數(shù)組的第一個(gè)元素,然后使二叉堆的長度減1,,并通過上移使得新得到的序列仍為二叉堆,,再提取新二叉堆的第一個(gè)元素到新數(shù)組。依此類推,,直到提取最后一個(gè)元素,,新得到的數(shù)組就是排序后的數(shù)組。

根據(jù)要求實(shí)現(xiàn)程序如下:

#include <stdio.h>

void push_heap(int *array, int pos, int value)

{

    int i;

    for(i=pos; i/2>0 && array[i/2]>value; i/=2) {

        array[i] = array[i/2];

    }

    array[i] = value;

}

void make_heap(int *data, int *array, int len)

{

    for(int i=0; i<len; ++i) {

        push_heap(array, i+1, data[i]);

    }

}

int pop_heap(int *array, int last)

{

    int value = array[1];

    array[1] = array[last];

    int i=1;

    while(2*i < last) {

        int min = array[2*i] < array[2*i+1] ? array[2*i] : array[2*i+1];

        int pos = array[2*i] < array[2*i+1] ? (2*i) : (2*i+1);

        if(array[i] > min) {

            int tmp = array[i];

            array[i] = min;

            array[pos] = tmp;

            i = pos;

        }

    }

    return value;

}

void sort_heap(int *data, int *array, int len)

{

    for(int i=0; i<len; ++i) {

        data[i] = pop_heap(array, len-i);

    }

}

int main()

{

    int data[] = {12, 34, 23, 3, 1, 45, 87, 99};

    int array[10];

    make_heap(data, array, 8);

    for(int i=1; i<=8; ++i) {

        printf("%d ", array[i]);

    }

    printf("\n");

    sort_heap(data, array, 8);

    for(int i=0; i<8; ++i) {

        printf("%d ", data[i]);

    }

    printf("\n");

    return 0;

}

 

堆排序的空間復(fù)雜度要求O(1),上面程序使用了輔助數(shù)組,,所以其空間復(fù)雜度為O(n),,不符合要求,所以又寫了一個(gè),如下:

#include <stdio.h>

int swap(int *a, int *b)

{

        int tmp = *a;

        *a = *b;

        *b = tmp;

}

void adjust(int *array, int i, int n)

{

        int min, pos;

        while(1) {

                if((2*i+2) < n) {

                        min = array[2*i+1] < array[2*i+2] ? array[2*i+1] : array[2*i+2];

                        pos = array[2*i+1] < array[2*i+2] ? (2*i+1) : (2*i+2);

                        if(array[i] < min) { break; }

                        swap(&array[i], &array[pos]);

                        i = pos;

                } else if((2*i+2) == n) {

                        min = array[2*i+1];

                        pos = 2*i+1;

                        if(array[i] < min) { break; }

                        swap(&array[i], &array[pos]);

                        i = pos;

                } else {

                        break;

                }

        }

}

void heap_sort(int *array, int n)

{

//構(gòu)建最小堆

        for(int j=(n-1)/2; j>=0; --j) {

                adjust(array, j, n);

        }

//降序排列

        for(int i=n; i>1; --i) {

                swap(&array[0], &array[i-1]);

                adjust(array, 0, --n);

        }

}

int main()

{

        int data[] = {12, 34, 23, 3, 1, 45, 87, 99};

        heap_sort(data, 8);

        for(int i=0; i<8; ++i) {

                printf("%d ", data[i]);

        }

        printf("\n");

        return 0;

}

    本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間,,所有內(nèi)容均由用戶發(fā)布,,不代表本站觀點(diǎn)。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式,、誘導(dǎo)購買等信息,,謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容,,請(qǐng)點(diǎn)擊一鍵舉報(bào),。
    轉(zhuǎn)藏 分享 獻(xiàn)花(0

    0條評(píng)論

    發(fā)表

    請(qǐng)遵守用戶 評(píng)論公約

    類似文章 更多