深入浅出选择类排序算法(简单选择排序,堆排序) -- 算法 -- IT技术博客大学习 -- 共学习共进步！

您现在的位置：首页 --> 算法 --> 深入浅出选择类排序算法(简单选择排序,堆排序)

深入浅出选择类排序算法(简单选择排序,堆排序)

浏览:3740次出处信息

一.简单选择排序：

简单选择排序的基本思想是：一次选定数组中的一个数，记下当前位置并假设它是从当前位置开始后面数中的最小数min=i，从这个数的下一个数开始扫描直到最后一个数，并记录下最小数的位置min，扫描结束后如果min不等于i，说明假设错误，则交换min与i位置上的数。(也即每次从数列中找出一个最小的数放到最前面来，再从剩下的n-1个数中选择一个最小的，不断做下去。

通俗的说：你要在你的班上选择女朋友(假定你有这个特权的话)，你开始肯定会最喜欢的，然后再选择次喜欢的，然后继续在剩下的MM中找

你比较喜欢的。这样就可以按你的要求排成一个序了，就这样理解。

简单选择排序算法的关键：

1.每一趟在n-i+1中选取最小的记录

2.通过n-i次关键字进行比较

3.总共需要n(n-1)/2次比较

4.选择排序算法的时间复杂度是“死”的，也就是O(n^2)

算法代码：

void SelectSort(int* a, int len) {
    int i,j,k;
    for (i=1; i<len; i++) {    /**< 比较n-i次 i为指向无序区的开始位置  */
        j=i;
        for (k=i-1; j<len; j++)   {    /**< "A" k记下目前最小关键字的位置，每一轮进行比较取出最小值  */
            if (a[j] < a[k])   {    /**< 如果排在前面的数字大于后面的就交换两者的key */
                k=j;
            }
        }
        if (k>=i)  {    /**< /一轮结束后，把k认为的最小值和i进行交换  */
            int m;
            m = a[k];
            a[k] = a[i-1];
            a[i-1] = m;
        }
    }
}

从上面的代码可以看出,整个序列分为有序和无序部分, 在A循环中选取最小关键字,也即是有序序列进行更新的时刻.

在这个算法中有两层循环, 外层循环执行n次, 内层循环执行n-1次平均时间复杂度为O( $n^2$ n^2).代码中使用了一个临时变量m,空间复杂度为

O(1).

二. 堆排序:

堆其实可以看成一个完全二叉树, 我们先温习下完全二叉树的定义:若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树.

完全二叉树

那么堆又是怎么回事呢, 堆分大小堆.

大顶堆的需要在满二叉树的定义下再满足, 任何一个非叶结点的值, 都不大于其左右结点的值, 也就是父亲大孩子小.

小顶堆的需要在满二叉树的定义下再满足, 任何一个非叶结点的值, 都不小于其左右结点的值, 也就是父亲小孩子大.

根据上面的性质可以得出, 根节点要么最大, 要么最小. 从排序角度来看, 如果一个无序序列调整一个堆的数据结构,那么它必定是有序的. 这个调整的过程就是堆排序的过程.

我们来取一组数据演示下堆排序的过程:

原始序列:

我们先把这组数据建立一棵完全二叉树, 如图:

因为49’, 76, 13, 27为叶子结点,所以不需要对其进行调整, 我们直接从非叶子结点97, 38, 65, 49开始.

1.先调整97, 发现97>49’, 满足大堆性质

2.调整38, 发现38<97, 38<76, 父亲都小于孩子结点的值,需要调整, 和孩子结点中最大值97交换, 38和97交换, 发现38<49’, 继续交换.交换后结果为:

3.调整65, 发现65>13, 65>27 满足大顶堆性质, 不需要交换.

4.调整49, 发现49<97, 49<65, 和较大的孩子97进行交换,交换后,发现49<76, 继续交换.结果为:

现在,已经没有需要调整的结点了, 也就是已经建立了一个大顶堆了.序列为:

因为是大顶堆, 所以根节点肯定是最大值了, 把根节点和最后一个结点进行交换, 就认为第一趟堆排序完成.然后除97这个序列再进行堆排序, 如此反复直到有序为止.

来看下代码实现:

///< 大顶堆调整
void HeapAdjust(int ziArray[], int iNonLeafIndex, int iLen)  {
     
    int iLeftChild = 2*iNonLeafIndex + 1;   
    int iRightChild = 2*iNonLeafIndex + 2;  
    int iMaxChild = iLeftChild;
    while (iLeftChild < iLen) {
        if (iRightChild < iLen) { ///< 说明有右儿子结点
            if (ziArray[iLeftChild]<ziArray[iRightChild]) {
                iMaxChild = iRightChild; ///< 算出最大儿子结点Index
            }
        }
        if (ziArray[iNonLeafIndex] < ziArray[iMaxChild]) {
            int iTemp = ziArray[iNonLeafIndex];
            ziArray[iNonLeafIndex] = ziArray[iMaxChild];
            ziArray[iMaxChild] = iTemp;
 
            iNonLeafIndex = iMaxChild;
            iLeftChild = 2*iNonLeafIndex + 1;  
            iRightChild = 2*iNonLeafIndex + 2; 
            iMaxChild = iLeftChild;
 
        } else {
            break;
        }
    }
    int i = 0;
    for(; i<iLen; i++)   {   
        printf("%d ", ziArray[i]);
    }
    printf("\n");
    return;   
}   
 
void HeapSort(int ziArray[], int iLen) {   
    int i=0;   
    ///< 建立初始堆 
    for (i=iLen/2; i>=1; i--) {   
        printf("从非叶结点%d调整:", i);
        HeapAdjust(ziArray, i-1, iLen);    ///< 从0开始 
    }
 
    printf("\n%s\n", "递归调整过程:");
    for (i=iLen-1; i>0; i--) {  
        printf("取出本次调整的根结点:%d--", ziArray[0]);
        ///<交换根结点和最后一个结点 
        int temp =ziArray[0];   
        ziArray[0] = ziArray[i];   
        ziArray[i] = temp;   
        HeapAdjust(ziArray, 0, i);   
    }   
    return;   
}   
 
int main()   
{   
    int ziArray[] ={49,38,65,97,76,13,27,49};   
 
    int iLen = sizeof(ziArray)/sizeof(int);
    printf("%s\n", "原序列:");
    int i = 0;
    for(; i<iLen; i++)   {   
        printf("%d ", ziArray[i]);
    }
    printf("\n");
    HeapSort(ziArray, 8);   
    printf("最后结果:");
    for(i=0; i<8; i++)   {   
        printf("%d ", ziArray[i]);
    }   
 
    return 0;   
}

实现结果为:

原序列:
49 38 65 97 76 13 27 49
从非叶结点4调整:49 38 65 97 76 13 27 49
从非叶结点3调整:49 38 65 97 76 13 27 49
从非叶结点2调整:49 97 65 49 76 13 27 38
从非叶结点1调整:97 76 65 49 49 13 27 38
 
递归调整过程:
取出本次调整的根结点:97--76 49 65 38 49 13 27
取出本次调整的根结点:76--65 49 27 38 49 13
取出本次调整的根结点:65--49 49 27 38 13
取出本次调整的根结点:49--49 38 27 13
取出本次调整的根结点:49--38 13 27
取出本次调整的根结点:38--27 13
取出本次调整的根结点:27--13
最后结果:13 27 38 49 49 65 76 97

堆排序的时间复杂度是和完全二叉树的高度有关的. 完全二叉树的高度为O( $log_2(n+1)$ log_2(n+1)),即结点最坏的调整堆的时间为O( $log_2n$ log_2n),另外在调整堆的过程中, 完全二叉树从最下层最右边的非终端结点开始调整, 将它与其孩子进行比较和交换, 对于每个非终端结点来说，其实最多进行两次比较和交换操作，因此整个调整堆的最坏时间复杂度为O(n).所以最坏时间复杂度为O( $nlog_2n$ nlog_2n).

堆排序空间复杂度为O(1), 因为需要一个临时变量存储中间数据.快排的时间复杂度为O( $nlog_2n$ nlog_2n),但是它的空间复杂度也为O( $nlog_2n$ nlog_2n),而堆排序是O(1), 这个是堆排序的优势.

原创文章,转载请注明出处: http://www.crazyshell.org/blog/?p=1049

建议继续学习：

QQ技术交流群：445447336，欢迎加入！
扫一扫订阅我的微信号：IT技术博客大学习

<< 前一篇：数学中的极限思想求时间复杂度

后一篇：深入浅出交换类排序算法(冒泡排序,快速排序) >>

文章信息

作者：Crazybaby 来源：狂Shell - Happy Hacking狂Shell - Happy Hacking
标签：排序
发布时间：2013-04-07 13:15:28

建议继续学习

近3天十大热文