数据结构排序系列之选择排序（三）

#include <stdio.h>




void selectSort(int R[],int n){
  // 进行n-1趟排序
  for(int i = 0;i < n-1;i++){
    int k = i;
    // 在R[i..n-1]区间选出关键字最小的元素
    for(int j = i;j < n;j++){
      if(R[k] > R[j]){
        k = j;
      }
    }
    // 将最小的元素与R[i]进行交换
    if(i != k){
      int temp = R[i];
      R[i] = R[k];
      R[k] = temp;
    }
  }
}
int main(){
  int data[] = {38,33,65,82,76,38,24,11};
  selectSort(data,8);
  for(int i = 0; i < 8;i++){
    printf("%d ",data[i]);
  }
  printf("\n");
  return 0;
}

堆排序是一个种树形选择排序

算法思想：

在排序过程中，将数组R[0..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和该子结点之间的内存关系，在当前无序区中选择关键字最大（或最小）的元素。

堆排序正是利用大根堆（或小根堆）来选择当前无序区中关键字最大（或最小）的元素来实现排序的。每一趟排序就是将当前无序区调整为一个大根堆，选择关键字最大的堆顶元素和无序区中最后一个元素进行交换。通过不断将剩余的无序区调整为一个大根堆，然后再将堆顶元素与无序区中最后一个元素进行交换来完成排序的。

那么堆排序的关键就是构造堆，构造堆的过程：

将待排序的文件的关键字存储在一个数组R[0..n-1]中(存储在R[1..n])更好理解，将R看成一棵完全二叉树的顺序存储结构，每个结点代表一个元素。那么任意结点R_i的左孩子是R\[2i+1\](如果是R[1..n]，那么左孩子就是R[2i])，右孩子是R\[2i+2\](如果是R[1..n]，那么右孩子就是R[2i+1])，R[i]的双亲结点就是R[i/2]。构造大根堆的过程：假设完全二叉树的某一个结点i的左子树和右子树已是堆，那么将R[2i+1]和R[2i+2]中的较大者与R[i]比较，如果R[i]较小，则交换，交换后，就有可能破坏下一级的堆，因此继续采取同样的方法构造下一级的堆，直至完全二叉树中以结点i为根的子树成堆为止，当无序区调整为大根堆时，堆顶元素就是无序区中关键字最大的元素，将其与无序区中最后一个元素进行交换。重复构造堆和进行交换，经过n-1趟后就可以排好序。

参考：

●完全二叉树的顺序存储结构就是从树根开始自上到下，每层从左到右地给该树中每个结点进行编号（假定从0开始），就能够得到一个反映整个二叉树结构的线性序列。

●堆：n个元素的关键字序列k₁,k₂,...,k_n称为堆，那么它必须满足以下条件：k_i≤k_2i且k_i≤k_2i+1，或k_i≥k_2i且k_i≥k_2i+1（也就是双亲结点要么都小于左右子结点，要么都大于左右子结点，前者叫小根堆（如15，27，44，76，38 ，59），后者叫大根堆（如76，38，59，27，15，44））

算法实现：

#include <stdio.h>




void check(int R[],int i,int l){
  // i当前结点，l为无序区的长度
  int j = 2*i +1; // R[i]的左孩子
  if((j+1) < l && R[j] < R[j+1]){
    j++;  
  }
  // R[i]与左右孩子结点中较大者进行比较
  if(j < l && R[i] < R[j]){
    int tmp = R[i];
    R[i] = R[j];
    R[j] = tmp;
    check(R,j,l);
  }
  
}








void heapSort(int R[],int n){
  
  // 堆排序就是不断建堆的过程
  int temp = n;
  while(temp != 0){
  // 恰好temp/2的结点的子树就是R的最后的元素
  for(int i = temp/2-1;i<temp/2 && i >= 0; i--){
      // 检查是否是堆，不是就调整，直到无序区变为大根堆
      check(R,i,temp);
  }




  temp--;
  // 堆顶元素与无序区最后一个元素交换
  int t = R[temp];
  R[temp] = R[0];
  R[0] = t;
  }
}




int main(){
  int data[] = {45,36,72,18,53,31,48,36};
  heapSort(data,8);
  for(int i =0 ; i < 8; i++){
    printf("%d ",data[i]);
  }
  printf("\n");
  return 0;
}