经典排序算法二（选择排序、堆排序）

过年的时候大家聚在一起打扑克，从两副混合扑克中挑选出完整的一副。一般我会按照一定的顺序来找。

1. ♣，从A到K。
2. ♥，从A到K。
3. ♦，从A到K。
4. ♠，从A到K。
5. 再找到大小王就算一副找全了。

这其实也可以说是选择排序了，每次挑选出某种花色最小的一个，然后第二小的。。。一直找到K。

正文

选择排序(Selection sort）

• 算法描述
  在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

初始值：  {49 27 65 97 76 12 38}　
  第一趟：12   {27 65 97 76 49 38}
  第二趟：12 27   {65 97 76 49 38}　　
  第三趟：12 27 38   {97 76 49 65}　　
  第四趟：12 27 38 49   {76 97 65}　
  第五趟：12 27 38 49 65   {97 76}　
  第六趟：12 27 38 49 65 76 97  {}

• 算法实现

void selectSort(int *a ,int num) {
    for (int i = 0; i < num - 1; i++) {
        int index = i;
        for (int j = i + 1; j < num; j++) {
            if (a[j] < a[index]){
                index = j;  // 记录位置
            }
        }
        if (index != i) { //如果最小数位置变化则交换
            int temp = a[index];
            a[index] = a[i];
            a[i] = temp;
        }
    }
}

堆排序（Heap Sort）

• 堆
  在接触“堆”这个概念之前，看到“堆”首先想到的就是“堆内存”的“堆”。。。
  根据堆-百度百科的资料，堆必须同时具备两个特性:
  1．堆总是一棵完全二叉树。
  2．堆中某个节点的值总是不大于或不小于其父节点的值。
  由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。
• 堆排序
  以如下无序数组A为例

1. 将该数组按顺序排列为完全二叉树（堆特性1）

   
   数组的二叉树表示

A[i]的左节点为A[2i+1],右节点为A[2i+2]，父节点为A[i/2]。从数组索引的角度描述了数字与数字在二叉树中的位置关系。

2. 一个数组想用堆排序，首先要把数组堆化（堆特性2）

   
   20160917105502853.gif

经典排序算法一（冒泡排序、快速排序）
经典排序算法三（插入排序、希尔排序）