选择排序(包含堆排序)

向右看齐 2022-06-16 04:50 252阅读 0赞

# 思路 #

每一趟都从n-i+1（i=1,2,3….n-1）个记录中选择出最小的关键字，作为有序序列的第i个元素。

# 常用的选择排序 #

*  简单选择排序
 *  堆排序

# 简单选择排序 #

## 思路 （参考：[选择排序][Link 1]） ##

数组A，长度为：n，临时变量：i,初始化为1  
\- 从A\[i\]~A\[n\]这n-i+1个元素中，找出最小的关键字，并且记录其下标  
\- 如果该关键字不是A\[i\]~A\[n\]这个序列的第一个元素，则将该两个位置的元素替换  
\- 将i从1~n-1，递增循环执行上述两个步骤

## 代码实现 ##

#include<iostream>
    using namespace std;
    typedef int Datatype;    //编译期多态的一种：转换
    
    void print(Datatype * data, int i, int length) {
        int j = 0;
        cout << "第" << i + 1 << "趟排序：";
        for (j = 0; j < length; ++j) {
            cout << data[j] << " ";
        }
        cout << endl;
    }
    void EasySelectSort(Datatype * data, const int length) {
        int i = 0;
        int j = 0;
        Datatype min;
        int temp = 0;
        for (i = 0; i < length-1; ++i) {    //只需要确认前length-1个元素的顺序，则最后一个位置的元素的位置也就确定了
            temp = i;                       //记录temp
            for (j=i; j < length; ++j) {    //找出最小的那个关键字的位置。 
                if (data[j] < data[temp]) {
                    temp = j;
                }
            }
            if (temp != i) {   //判断是否需要交换两个位置上的元素
                min = data[temp];
                data[temp] = data[i];
                data[i] = min;
            }
            print(data, i, length);
        }
    }
    
    
    
    void main() {
        int data[] = { 7,4,-2,19,13,6 };
        EasySelectSort(data, sizeof(data) / sizeof(int));
        system("pause");
    }

结果：  
![image][]

## 时间复杂度分析 ##

我们通过分析可以知道，我们程序无论是什么情况，都要比较：n\*(n-1)/2次。所以程序的时间复杂度为：O(n^2)。

## 是否稳定 ##

稳定的定义就是：两个相同的数，在排完序后前后的相对顺序没有改变。对于简单选择排序，它是不稳定的，我可以简单的举个例子：\{7,7,2\}，当我们进行简单选择排序后，第一个7会和2调换位置，从出现不稳定的情况

# 堆排序 #

简单的选择排序为了得出有序的序列，对于任意序列都要比较：n\*(n-1)/2次。那么我们要优化这个算法的话，那么就要减少我们的比较的次数。所以从比较这里出发：我们为得出n个关键字中的最小的值，需要比较n-1次，而下一次要得出n-1个关键字中最小的值时，同样又要比较n-2次，如果我们可以利用之前的n-1次的比较结果，那么我们就可能在下一次寻找中，减少比较次数，从而就可以提高程序的效率了。堆就可以记录这些信息，所以我们就提出了另外一种优化的选择排序：堆排序

## 思路 ##

用一个完全二叉树来表示堆，堆有两种：最大堆和最小堆。  
\- 最大堆：所有结点都比它们的左右孩子大。调整过程出现两个孩子结点，都大于父结点，选择大的那个替换。  
\- 最小堆：所有结点都比它们的左右孩子小。调整过程出现两个孩子结点，都小于父结点，选择小的那个替换。

堆排序的大体思路是（以最小堆为例）：  
\- 首先建立初始堆  
\- 输出根结点，用最后一个结点替换根结点，删除最后一个结点，并且对堆进行调整，使其还是满足最小堆的性质。  
\- 重复，第二个过程，直到堆为空为止

## 实现过程 ##

我们从思路分析，可以知道我们需要解决两个问题：  
\- 建立初始堆  
\- 输出后，对堆的调整

## 程序实现 ##

void HeapAdjust(Datatype * data, int length, int s) {
        //最小堆
        int j = 0;
        Datatype temp = data[s];
        j = 2 * s + 1;
        for (; j <= length; j = 2 * j + 1) {
            /*
            最大堆需要修改：下面两个if语句，
            */
            //如果左子树小于右子树，则让右子树去和根结点比较
            if (j < length && data[j] > data[j + 1]) {
                ++j;
            }
            //此时已经满足最小堆了条件了，可以停止寻找了
            if (temp <= data[j]) {
                break;
            }
            //交换根结点和孩子结点的值
            data[s] = data[j];
            s = j;
        }
        //最后，确定了我们那个关键需要存放的地方
        data[s] = temp;
    }
    void HeapSort(Datatype * data, int length) {
        for (int i = (length / 2)-1; i >= 0; --i) {
          
            HeapAdjust(data, length-1, i);
        }
        int n = length - 1;
        //这里我们只需要比较前length-1个数，最后一个数的值也就确定了
        while (n >= 1) {
            Datatype temp;
            temp = data[0];
            data[0] = data[n];
            data[n] = temp;
            cout << temp << " ";
            --n;
            HeapAdjust(data, n, 0);
        }
        cout << data[n];
        cout << endl;
    }

在主函数中，调用上述的HeapSort函数，就可以进行堆排序了。

## 时间复杂度分析 ##

这里的时间主要是花费在调用heapAdjust函数中，HeapAdjust函数最多做：⌈log2n⌉次调整，总共需要调用：(n/2）+(n-1)次HeapAdjust函数，所以该时间复杂度为：O（nlog2n）

## 是否稳定 ##

堆排序是不稳定的排序算法，比如有无序的序列：\{3,27,36,27\}，所以在输出3后，最后的那个27替换到了根节点，从这里就可以看出该算法是不稳定的。

# 总结 #

堆排序的时间复杂也是为：O（nlog2n），而且是最多就是：O（nlog2n）。对于时间复杂同样是：O（nlog2n）的排序算法：快速排序和归并排序来说，它只是在最坏情况下是占优势的。具体可以参考：  
[堆和快排、归并的比较][Link 2]

[Link 1]: http://blog.csdn.net/u011784495/article/details/70985444
[image]: http://i4.buimg.com/593129/c94e7b5233e3a747.png
[Link 2]: http://blog.csdn.net/morewindows/article/details/6967409