堆排序
概要
1.堆排序基本介绍
（1）堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度为O（nlogn）,它也是不稳定排序。
（2）堆是具有以下性质的完全二叉树：每个节点的值都大于等于其左右孩子结点的值，称为大顶堆，注意：没有要求节点的左孩子的值和右孩子的值的大小关系。
（3）每个系欸但的值都小于等于其左右孩子节点的值，称为小顶堆。
（4）大顶堆举例说明
我们对堆中的节点按层次进行编号，映射到数组中就是下面这样：
大顶堆特点：
- arr[i]>=arr[2 * i + 1] && arr[i] >=arr[2 * i + 2] //i 对应第几个节点，i从0开始编号
（5）小顶堆举例说明
- arr[i]<=arr[2 * i + 1] && arr[i] <=arr[2 * i + 2] //i 对应第几个节点，i从0开始编号
（6）一般升序采用大顶堆，降序采用小顶堆
2.堆排序基本思想
（1）将待排序序列构造成一个大顶堆
（2）此时，整个序列的最大值就是堆顶的根节点。
（3）将其与末尾元素进行交换，此时末尾就为最大值。
（4）然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了。
3.堆排序步骤图解
要求：有一个数组{4，6，8，5，9}，要求适用堆排序法，将数组升序排序。
- 步骤1：构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆）。
（1）假设给定无序序列结构如下
（2）此时我们从最后一个非叶子节点开始（叶节点自然不用调整，第一个非叶子节点arr.length / 2 -1 = 5 / 2 - 1 = 1,也就是下面的6节点），从左到右，从下至上进行调整。
（3）找到第二个非叶子节点4，由于[4,9,8]中9元素最大，4和9交换。
（4）这时，交换导致了子跟[4,5,6]结构混乱，继续调整[4,5,6]中的6最大，交换4和6。
此时，我们就将一个无序序列构造成了一个大顶堆。
- 步骤2：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
（1）将堆顶元素9和末尾元素4进行交换。
（2）重新调整结构，使其继续满足堆定义。
（3）再将堆顶元素8与末尾元素5进行交换，得到第二大元素8。
（4）后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序。
4.再简单总结下堆排序的基本思路
（1）将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆。
（2）将堆顶元素与末尾元素交换，将最大元素“沉”到数组末端。
（3）重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
public class HeapSort
{
public static void HeapSort0(int[] arr)
{
Console.WriteLine("堆排序！");
//分步完成
AddJustHeap(arr, 1, arr.Length);
Console.WriteLine("第一次" + arr.ToString());//4,9,8,5,6
}
/// <summary>
/// 完成将以i指向的对应的非叶子节点的树调整为一个大顶堆
/// 将一个数组（二叉树），调整为一个大顶堆
/// 举例int [] arr = {4,6,8,5,9}; =>i = 1 => addjustheap => 得到{ 4，9，8，5，6 }
/// 如果我们再次调用addjustheap 传入的是i = 0 =>{4,9,8,5,6}=>{9,6,8,5,4}
/// </summary>
/// <param name="arr">待调整数组</param>
/// <param name="i">表示非叶子节点在数组中索引</param>
/// <param name="length">表示堆多少个元素进行继续调整，length在逐渐减少</param>
public static void AddJustHeap(int[] arr, int i, int length)
{
int temp = arr[i];//先取数当前元素的值，保存在临时变量
//开始调整
//1. k = i * 2 + 1 , k 是i节点的左子节点
for (int k = i * 2 + 1; k < length; k = k * 2 +1)
{
//说明左子节点的值小于又子节点的值
if (k + 1 < length && arr[k] < arr[k+1])
{
k++; // k指向又子节点
}
//如果子节点大于父节点
if (arr[k] > temp)
{
//把较大的值赋给当前节点
arr[i] = arr[k];
//i 指向 k，继续循环比较
i = k;
}
else
{
break;
}
}
//当for循环结束后，我们已经将以i为父节点的树的最大值，放在了最顶（局部）
arr[i] = temp;//将temp的值放到调整后的位置
}
}调用
static void Main(string[] args)
{
//数组进行升序排序
int[] arr = { 4, 6, 8, 5, 9 };
HeapSort.HeapSort0(arr);
Console.Read();
}- 第一次
- 第二次
- 最后完成
第二套方案：
public static void HeapSort0(int[] arr)
{
int temp = 0;
Console.WriteLine("堆排序！");
//分步完成
//AddJustHeap(arr, 1, arr.Length);
//Console.WriteLine("第一次" + string.Join(' ',arr));//4,9,8,5,6
//AddJustHeap(arr, 0, arr.Length);
//Console.WriteLine("第二次" + string.Join(' ', arr));//9,6,8,5,4
for (int i = arr.Length / 2 - 1; i >= 0; i--)
{
AddJustHeap(arr, i, arr.Length);
}
//Console.WriteLine("第三次" + string.Join(' ', arr));
for (int j = arr.Length - 1; j > 0; j--)
{
temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
AddJustHeap(arr, 0, j);
}
Console.WriteLine("数组=" + string.Join(' ', arr));
} static void Main(string[] args)
{
//数组进行升序排序
int[] arr = { 4, 6, 8, 5, 9,-1,90,89,56,-999 };
HeapSort.HeapSort0(arr);
Console.Read();
}
堆排序的速度非常快，800万数据在3秒左右。O（nlogn）