分类目录归档:算法

RSA算法优化【轉】

【原文鏈接】

https://blog.csdn.net/wdxzkp/article/details/9294269

【內容】

RSA算法优化

  1. 大数乘法
  2. 模乗优化
  3. 剩余定理(孙子定理)
  4. RSA加解密
  5. python的RSA计算优化

 

[python] view plain copy

  1. #-*- coding: utf-8 -*-
  2. ”’
  3. /*********************************************************************************
  4.   *Copyright(C),2000-2013,KK Studio
  5.   *FileName:    rsa
  6.   *Author:      KingKong
  7.   *Version:     1.0
  8.   *Date:        20130709
  9.   *Description: //用于主要说明此程序文件完成的主要功能
  10.                 //与其他模块或函数的接口、输出值、取值范围、
  11.                 //含义及参数间的控制、顺序、独立及依赖关系
  12.   *Others:      //其他内容说明
  13.   *Function List:      //主要函数列表,每条记录应包含函数名及功能简要说明
  14.      1.RSA
  15.      2.RSA CRT
  16.      3.RSA MulMod    
  17.   *History:            //修改历史记录列表,每条修改记录应包含修改日期、修改者及修改内容简介
  18.      1.20130702:
  19. **********************************************************************************/
  20. ”’
  21. # sudo apt-get install python-setuptools
  22. # sudo easy_install rsa-3.1.1-py2.7.egg
  23. # import binascii
  24. #print repr(binascii.unhexlify(‘0123456789abcdef’)) 
  25. EASYKEY = True
  26. def CRT_SRC(c, n, p, q, d=None, exp1=None, exp2=None):
  27.     ”’
  28.     剩余定理的基础实现
  29.     c是密文
  30.     exp1 = d % (p-1)
  31.     exp2 = d % (q-1)
  32.     (1)计算d1←d(mod(p-1))与d2←d(mod(q-1));
  33.     (2)计算C1←c(modp)与C2←c(modq); 
  34.     (3)计算M1←C1^d1 (modp)与M2←C2^d2(modq);
  35.     (4)计算B1←q-1(modp)与B2←p-1(modq);
  36.     (5)计算m←(M1*B1*q+M2*B2*p)(modN)
  37.     ”’
  38.     c1 = c % p
  39.     c2 = c % q
  40.     if d != None:
  41.         d1 = d % (p-1)
  42.         d2 = d % (q-1)
  43.     elif exp1 != None:
  44.         d1 = exp1
  45.         d2 = exp2
  46.     else:
  47.         return 0
  48.     import rsa
  49.     y1 = rsa.common.inverse(q, p)
  50.     y2 = rsa.common.inverse(p, q)
  51.     m1 = pow(c1, d1, p)
  52.     m2 = pow(c2, d2, q)
  53.     m = (m1*q*y1 + m2*p*y2)%n
  54.     return m
  55. def CRT_MMRC(c, n, p, q, coef, d=None, exp1=None, exp2=None):
  56.     ”’
  57.     剩余定理的快速实现
  58.     c是密文
  59.     exp1 = d % (p-1)
  60.     exp2 = d % (q-1)
  61.     self.coef = rsa.common.inverse(q, p)    
  62.     (1)计算d1←d(mod(p-1))与d2←d(mod(q-1));
  63.     (2)计算C1←c(mod p)与C2←c(mod q); 
  64.     (3)计算M1←C1^d1 (modp)与M2←C2^d2(modq);
  65.     (4)计算B←p^-1(modp); 
  66.     (5)计算m←M1+[(M2-M1)*B(modq)]*p
  67.     ”’
  68.     c1 = c % p
  69.     c2 = c % q
  70.     if d != None:
  71.         d1 = d % (p-1)
  72.         d2 = d % (q-1)
  73.     elif exp1 != None:
  74.         d1 = exp1
  75.         d2 = exp2
  76.     else:
  77.         return 0
  78.     y1 = coef
  79.     m1 = pow(c1, d1, p)
  80.     m2 = pow(c2, d2, q)
  81.     m = m2 + (((m1-m2)*y1)%p)*q
  82.     return m
  83. def dec2bin(number):
  84.     ”’
  85.     转换数字为二进制字符串
  86.     :param number:
  87.     ”’
  88.     m = {‘0’:‘0000’‘1’:‘0001’‘2’:‘0010’‘3’:‘0011’,
  89.           ‘4’:‘0100’‘5’:‘0101’‘6’:‘0110’‘7’:‘0111’,
  90.           ‘8’:‘1000’‘9’:‘1001’‘a’:‘1010’‘b’:‘1011’,
  91.           ‘c’:‘1100’‘d’:‘1101’‘e’:‘1110’‘f’:‘1111’}
  92.     s = hex(number)[2:].rstrip(‘L’)
  93.     return .join(m[x] for x in s).lstrip(‘0’)
  94. #print dec2bin(10), len(dec2bin(10)) 
  95. def MulMod(m, r, e):
  96.     ”’
  97.     a^m%r
  98.     343^474%2003=1819
  99.     ”’
  100.     c = 1L
  101.     b = dec2bin(e)
  102.     length = 0;
  103.     while(length < (len(b))):
  104.         c = (c*c)%r;
  105. #         print c, b[length]
  106.         if (b[length] == “1”):
  107.             c = (c * m) % r;
  108.         length = length + 1;
  109.     return c
  110. def RSA_ENC(m, n, e):
  111.     ”’
  112.     RSA加密,处理小数据
  113.     :param m:
  114.     :param n:
  115.     :param e:
  116.     ”’
  117.     return m**e%n
  118. def RSA_DEC(c, n, d):
  119.     ”’
  120.     RSA解密,处理小数据
  121.     :param c:
  122.     :param n:
  123.     :param d:
  124.     ”’
  125.     return c**d%n
  126. def RSA_ENC_Fast(m, n, e):
  127.     ”’
  128.     RSA加密,处理大数,加速处理
  129.     :param m:
  130.     :param n:
  131.     :param e:
  132.     ”’
  133.     return pow(m, e, n)
  134. def RSA_DEC_Fast(c, n, d):
  135.     ”’
  136.     RSA解密,处理大数,加速处理
  137.     :param c:
  138.     :param n:
  139.     :param d:
  140.     ”’
  141.     return pow(c, d, n)
  142. def main():
  143.     if EASYKEY == True:
  144.         n = 3727264081
  145.         d = 3349121513
  146.         e = 65537
  147.         p = 65063
  148.         q = 57287
  149.         exp1 = 55063
  150.         exp2 = 10095
  151.         coef = 50797
  152.     else:
  153.         n = 133258714669197804455201327242498072620373933399830946281753432589524373262313529490829857553863402092345114025453326547226675345976454214588491707723768296657213731743431331618394950680996499630699923360897031860272219245284778878593279460078556127568327691304405295451439978360703575209901885763486177804307
  154.         d = 88839143112798536303467551494998715080249288933220630854502288393016248841542352993886571702575601394896742683635551031484450230650969476392327805149178849037945720743702166302175205762735121467799910708222531056914667451445033725048565810909623712841116051352011118012226070375134490825522121220289982706011
  155.         e = 3
  156.         p = 11933806723950669295207846073987787705734940703054957716278358174994444687961839258803748173125990183157845108140695431551588508864566689717312651807708143
  157.         q = 11166488426677208786957286068049106111694059354243605518996542043073672540329181171939965947432316470456431280477737669321209492974404928986620399396037149
  158.         exp1 = 7955871149300446196805230715991858470489960468703305144185572116662963125307892839202498782083993455438563405427130287701059005909711126478208434538472095
  159.         exp2 = 7444325617784805857971524045366070741129372902829070345997694695382448360219454114626643964954877646970954186985158446214139661982936619324413599597358099
  160.         coef = 9906165481638181059785426924280606820580988396251355030296387570862138753002899617836092623649635665775562393844489153345463178213574659230193241203692517
  161.     m = 9999
  162.     print ‘********RSA BEGIN********************************************’
  163.     print ‘message:’, m
  164.     c = RSA_ENC(m, n, e)
  165.     print ‘encrypt:’, c
  166.     r = RSA_DEC_Fast(c, n, d)
  167.     print ‘decrypt:’, r
  168.     print ‘********RSA END**********************************************’
  169.     print ‘********RSA FAST BEGIN***************************************’
  170.     print ‘message:’, m
  171.     c = RSA_ENC_Fast(m, n, e)
  172.     print ‘encrypt:’, c
  173.     r = RSA_DEC_Fast(c, n, d)
  174.     print ‘decrypt:’, r
  175.     print ‘********RSA FAST END*****************************************’
  176.     print ‘********RSA MulMod BEGIN*************************************’
  177.     print ‘message:’, m
  178.     c = MulMod(m, n, e)
  179.     print ‘encrypt:’, c
  180.     r = MulMod(c, n, d)
  181.     print ‘decrypt:’, r
  182.     print ‘********RSA MulMod END***************************************’
  183.     print ‘********RSA CRT BEGIN****************************************’
  184.     print ‘message:’, m
  185.     c = RSA_ENC_Fast(m, n, e)
  186.     print ‘encrypt:’, c
  187.     r = CRT_SRC(c, n, p, q, d)
  188.     print ‘decrypt:’, r
  189.     print ‘********RSA CRT END******************************************’
  190.     print ‘********RSA CRT FAST BEGIN***********************************’
  191.     print ‘message:’, m
  192.     c = RSA_ENC_Fast(m, n, e)
  193.     print ‘encrypt:’, c
  194.     r = CRT_MMRC(c, n, p, q, coef, d, exp1, exp2)
  195.     print ‘decrypt:’, r
  196.     print ‘********RSA CRT FAST END*************************************’
  197. if __name__ == ‘__main__’:
  198.     main()

 

Openssl源码方式添加国密SM2算法【轉】

【原文摘自】

http://blog.csdn.net/mrpre/article/details/51700884

【原文內容】

1:源码方式,只需要添加2部分,第一部分是 国密sm2的oid,第二部分是group。

如果不添加,则 EVP_PKEY 无法解析,ec_asn1_pkparameters2group 函数 因为找不到 oid对应的group导致解析私钥失败,或者解析x509的公钥为空。

注:如下修改 不会 让你支持生成SM2国密证书或者支持诸如ECC_SM4_SM3等国密加密套件。

该修改只是让你能够让openssl正常解密 sm2 证书。

1:添加sm2的oid

cd crypto/objects/

编辑  objects.txt ,添加: 1 2 156 10197 1 301: SM2: SM2

随便加在哪里即可,我添加在文件最后。

然后在当前目录下执行:
perl objects.pl objects.txt obj_mac.num obj_mac.h
perl obj_dat.pl obj_mac.h  obj_dat.h

2:添加 group

ec_curve.c 中添加 2 个定义:

static const struct { EC_CURVE_DATA h; unsigned char data[0+32*6]; }
_EC_X9_62_sm2 = {
{ NID_X9_62_prime_field,0,32,1 },
{  /* seed */
0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,/* p */
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFF,
0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,    /* a */
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
0xFF,0xFc,
0x28,0xE9,0xFA,0x9E,0x9D,0x9F,0x5E,0x34,0x4D,0x5A,/* b */
0x9E,0x4B,0xCF,0x65,0x09,0xA7,0xF3,0x97,0x89,0xF5,
0x15,0xAB,0x8F,0x92,0xDD,0xBC,0xBD,0x41,0x4D,0x94,
0x0E,0x93,
0x32,0xC4,0xAE,0x2C,0x1F,0x19,0x81,0x19,0x5F,0x99,    /* x */
0x04,0x46,0x6A,0x39,0xC9,0x94,0x8F,0xE3,0x0B,0xBF,
0xF2,0x66,0x0B,0xE1,0x71,0x5A,0x45,0x89,0x33,0x4C,
0x74,0xC7,
0xBC,0x37,0x36,0xA2,0xF4,0xF6,0x77,0x9C,0x59,0xBD,    /* y */
0xCE,0xE3,0x6B,0x69,0x21,0x53,0xD0,0xA9,0x87,0x7C,
0xC6,0x2A,0x47,0x40,0x02,0xDF,0x32,0xE5,0x21,0x39,
0xF0,0xA0,
0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF, /* order */
0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x72,0x03,0xDF,0x6B,
0x21,0xC6,0x05,0x2B,0x53,0xBB,0xF4,0x09,0x39,0xD5,
0x41,0x23}
};

curve_list 中添加:

{ NID_SM2, &_EC_X9_62_sm2.h, 0, “sm2 curve over a 256 bit prime field” },

然后重新make一下。

上述添加完成之后,OpenSSL即支持 SM2国密算法,能够正常解析 SM2国密证书。

 

【附】

需要將./crypto/objects/obj_mac.h移動到./include/openssl/obj_mac.h下,才能進行編譯

经典排序算法总结与实现「轉」

原文鏈接:http://xiaok.me/2015/08/27/%E7%BB%8F%E5%85%B8%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E4%B8%8E%E5%AE%9E%E7%8E%B0/

 

暑假快过完了也就大四了,马上就到了校招季了,作为一个才接触Android半年多的渣渣真的很慌张。最近打算复习一些算法和数据结构的知识,提升一下基础。这一篇是对经典排序算法的总结,共七个,可以说是手到擒来,提笔就要会的了。为了使代码易读,就用最简单的C语言实现了。

后面的排序默认从小到大排列

冒泡排序(Bubble sort)

原理

冒泡排序是一种简单的排序算法。它重复访问要排序的数列,每一次比较两个元素,如果前一个大于后一个元素,则交换数据。那么在一次全部访问过程中,最大的元素就’浮’动到数列的最后。然后重复进行方法,知道再没有数据交换,也就是数列已经排序完成。

步骤

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤,除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

实现

void BubbleSort(int arr[], int n) {
    int i, j;
    i = n;
    bool flag = true;
    while (flag) {
        flag = false;
        for (j = 1; j < i; j++) {
            if (arr[j-1] > arr[j]) {
                swap(arr[j-1], arr[j]);
                flag = true;
            }
        }
        i--;
    }
}

在上面的代码中加入了一个flag来标记是否有数据交换,如果在排序过程中没发生数据交换,则表示已经排列好了,后面就不需要在遍历了。

冒泡排序算是最简单的排序算法了,但毕竟是一种效率低下的排序算法,再数据量不大的情况下可以使用。

插入排序(Insertion sort)

原理

插入排序是一种直观的排序算法。它通过构建有序数列,对未排序的数据,在已排序的数列中从后往前扫描,找到相应的位置插入。在排序的实现上,从后向前的扫描过程中,需要反复把已排序的元素逐步向后移动,为要插入的元素留空间。

步骤

  1. 从第一个元素开始,该元素可以认为已经被排序
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
  5. 将新元素插入到该位置后
  6. 重复步骤2~5

实现

void InsertSort(int arr[], int n) {
    int i, j;
    for (i = 1;  i < n; i++) {
        if (arr[i] < arr[i-1]) {
            int temp = arr[i];
            for (j = i - 1; j >= 0 && arr[j] > temp; j--) {
                arr[j+1] = arr[j];
            }
            arr[j+1] = temp;
        }
    }
}

插入排序不适合对于数据了比较大的排序应用。但是,如果排序数据了很小,比如一千左右,那插入排序是一个不错的选择。

选择排序(Selection sort)

原理

选择排序与插入排序很像,插入排序是将一个数插入已经排好的序列,而选择排序是在未排序的序列中找到最小(大)元素,放在排序序列的起始位置。然后,再从剩下的未排序的序列中再次寻找最小(大)元素,放在已排序序列的末尾,反复重复,知道所有元素排序完成。

步骤

  1. 初始时,数组全为无序区为a[0..n-1]。令i=0
  2. 在无序区a[i…n-1]中选取一个最小的元素,将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。
  3. i++并重复第二步直到i==n-1。排序完成。

实现

void SelectSort(int arr[], int n){
    int i, j, minIndex;
    for (i = 0; i < n; i++) {
        minIndex = i;
        for (j = i+1; j < n; j++) {
            if (arr[minIndex] > arr[j]) {
                minIndex = j;
            }
        }
        if (minIndex != i) {
            Swap(arr[i],arr[minIndex]);
        }
    }
}

选择排序中,如果某个元素位于正确的最终位置,则不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移动到最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

希尔排序(Shell sort)

原理

希尔排序,也称作递减增量排序算法,是插入排序的一种更高效版本。它以一定的增量将序列分为若干个组,然后每一组进行插入排序,然后减少增量反复分组进行插入排序。直到增量为1时,就为普通的插入排序,但是此时序列已经基本排列完成,只需要进行少量的移动即可完成。

步骤

将数组列在一个表中并对列排序(用插入排序)。重复这过程,不过每次用更长的列来进行。最后整个表就只有一列了。将数组转换至表是为了更好地理解这算法,算法本身仅仅对原数组进行排序(通过增加索引的步长,例如是用i += step_size而不是i++)

例如,假设有这样一组数[ 13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10 ],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,这样他们就应该看起来是这样:

13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10

然后我们对每列进行排序:

10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

将上述四行数字,依序接在一起时我们得到:[ 10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45 ].这时10已经移至正确位置了,然后再以3为步长进行排序:

10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45

排序之后变为:

10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94

最后以1步长进行排序(此时就是简单的插入排序了)。

实现

void ShellSort(int arr[], int n) {
    int i, j, gep;
    for (gep = n/2; gep > 0; gep /= 2) {
        for (i = gep; i < n; i++) {
            int temp = arr[i];
            for (j = i - gep; j >= 0 && arr[j] > temp; j-=gep) {
                arr[j+gep] = arr[j];
            }
            arr[j+gep] = temp;
        }
    }
}

希尔排序步长的选择十分灵活,只要最终步场为1的任何步长序列都可以工作。以上的代码从n/2开始,每一次减半,最终步长为1,算法变为插入排序,就保证了数据一定会被排序。

归并排序(Merge sort)

原理

归并排序是创建在归并操作上的一种有效的排序算法,基本思想是分治法。它时将两个已经排序的序列合并成一个序列的操作。

步骤

归并操作

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  2. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  4. 重复步骤3直到某一指针到达序列尾
  5. 将另一序列剩下的所有元素直接复制到合并序列尾

归并排序

  1. 将序列每相邻两个数字进行归并操作,形成floor(n/2)个序列,排序后每个序列包含两个元素
  2. 将上述序列再次归并,形成floor(n/4)个序列,每个序列包含四个元素
  3. 重复步骤2,直到所有元素排序完毕

实现

//归并操作
void _merge_array(int arr[], int first, int mid, int last, int temp[]) {
    int i = first, j = mid + 1;
    int m = mid, n = last;
    int k = 0;
    while (i <= m && j <= n) {
        if (arr[i] < arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    
    while (i <= m) {
        temp[k++] = arr[i++];
    }
    
    while (j <= n) {
        temp[k++] = arr[j++];
    }
    
    for (i = 0; i < k; i++) {
        arr[first + i] = temp[i];
    }
}

//归并排序
void _merge_sorte(int arr[], int first, int last, int temp[]) {
    if (first < last) {
        int mid = (first + last) / 2;
        _merge_sorte(arr, first, mid, temp);
        _merge_sorte(arr, mid+1, last, temp);
        _merge_array(arr, first, mid, last, temp);
    }
}

void MergeSort(int arr[], int n) {
    int *p = (int *)malloc(sizeof(int) * n);
    if (p != nullptr) {
        _merge_sorte(arr, 0, n-1, p);
    }
    free(p);
}

归并排序是分治法的典型应用,当一个数组的左右两边都有序然后归并整个数组就有序了,利用递归逐层分治,然后合并上来就排好序了。

快速排序(Quick sort)

快速排序算是我最喜欢的一个排序了,记得第一次接触的时候惊讶排序还可以这么排…题外话了

原理

快速排序也适用分治法,已一个数作为基准,左边全为笔它小的数,右边全为比它大的数。然后左右递归重复即可。

步骤

  1. 从数列中挑出一个元素,称为”基准”(pivot)
  2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  3. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

实现

下面列两种实现一种MoreWindows大神已挖坑填数总结的,一种是算法导论上的实现。

MoreWindows:

void QuickSort(int arr[], int l, int r) { 
    if (l < r) {
        int i = l, j = r;
        int k = arr[i];
        
        while (i < j) {
            while (i<j && arr[j] > k) {
                j--;
            }
            if (i<j) {
                arr[i++] = arr[j];
            }
            
            while (i<j && arr[i] <= k) {
                i++;
            }
            if (i<j) {
                arr[j--] = arr[i];
            }
        }
        arr[i] = k;
        
        QuickSort(arr, l, i-1);
        QuickSort(arr, i+1, r);
    }
}

算法导论 :

int quick_sort(int arr[], int left, int right) {
    int index = left;
    int k = arr[index];
    
    Swap(arr[index],arr[right]);
    for (int i = left; i < right; i++) {
        if (arr[i] < k) {
            Swap(arr[index++], arr[i]);
        }
    }
    Swap(arr[index], arr[right]);
    return index;
}

void QuickSort(int arr[], int left, int right) {
    if (left < right) {
        int index = quick_sort(arr, left, right);
        QuickSort1(arr, left, index-1);
        QuickSort1(arr, index+1, right);
    }
}

快速排序递归下去的最低情形,是数列的大小0或1,也就是永远排好了序。在每一次递归中至少有一个数会摆到它最后的位置。

堆排序(Heap sort)

堆排序对于我而言算是比较难搞懂的排序了

原理

堆排序是利用堆这种数据结构所设计的一种排序算法。最大(小)堆的根节点 为整个序列的最大(小)数。堆每取出一个根节点,堆被破坏,然后堆就会调整使之符合最大(小)堆。那么依次取出堆的根节点,依次放入新的数列中,直到堆元素为0位置,那么新的数列已经排好序了。

步骤

堆节点的访问:

通常堆是通过一维数组来实现的。在起始数组为0的情形中:

  • 父节点i的左子节点在位置(2*i+1);
  • 父节点i的右子节点在位置(2*i+2);
  • 子节点i的父节点在位置floor((i-1)/2);

堆的操作:

在堆的数据结构中,堆中的最大值总是位于根节点。堆中定义以下几种操作:

  • 最大堆调整(Max_Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点
  • 创建最大堆(Build_Max_Heap):将堆所有数据重新排序
  • 堆排序(HeapSort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

原地堆排序:

  1. 创建一个堆H[0..n-1]
  2. 把堆首(最大值)和堆尾互换
  3. 把堆的尺寸缩小1,并调用MaxPrcdown(),目的是把新的数组顶端数据调整到相应位置
  4. 重复步骤2,直到堆的尺寸为1

实现

void MaxPrcdown(int arr[], int i, int n) {
    int temp = arr[i];
    int chlid = 2 * i + 1;
    while (chlid < n) {
        if (chlid + 1 < n && arr[chlid] < arr[chlid+1]) {
            chlid++;
        }
        
        if (arr[chlid] <= temp) {
            break;
        }
        
        arr[i] = arr[chlid];
        i = chlid;
        chlid = 2 * i + 1;
    }
    arr[i] = temp;
}

void HeapSort(int arr[], int n) {
    for (int i = n / 2 - 1; i>=0; i--) {
        MaxPrcdown(arr, i, n);
    }
    for (int i = n - 1; i >= 1; i--) {
        Swap(arr[0], arr[i]);
        MaxPrcdown(arr, 0, i);
    }
}

总结

 

排序算法 最差时间复杂度 平均时间复杂度 空间复杂度 稳定性
冒泡排序 O(n^2) O(n^2) O(1) 稳定
插入排序 O(n^2) O(n^2) O(1) 稳定
选择排序 O(n^2) O(n^2) O(1) 稳定
归并排序 O(nlogn) O(nlogn) O(n) 不一定
希尔排序 O O O(1) 不稳定
快速排序 O(n^2) O(nlogn) O(logn)~O(n) 不稳定
堆排序 O(n*log2n) O(n*log2n) O(1) 不稳定

 

参考