7.3 堆排序

1. 选择排序

 void Selection_Sort (ElementType [A], int N) {
      for (I = 0; I< N; I++) {
      MinPosition = ScanForMin (A,i,N-1); // 从a[I] 到a[n-1] 找出最小元，并将其位置赋值给MinPosition;
      Swap(A[I]，A[MinPostion]); //将未排序的最小元 换到有序部分的最后位置。
    }
}

如何快速找到最小元问题：

使用堆排序：
算法1：

void Heap_Sort (ElementType A[],int N) {
  BuildHeap(A);       //O(N)
  for (I = 0 ; I< N; I++) {
   TmpA[i]  = DeleteMin(A)   // O(logN)
  }     
  for (I = 0 ; I<N; I++) {
  A[I] = TmpA[i]; 
  }
}

// 总的时间复杂度 是T(N) = O(N logN)