堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
?
基本思想
1.将要排序的数组创建为一个大根堆。大根堆的堆顶元素就是这个堆中最大的元素。
2.将大根堆的堆顶元素和无序区最后一个元素交换，并将无序区最后一个位置例入有序区，然后将新的无序区调整为大根堆。
重复操作，无序区在递减，有序区在递增。
初始时，整个数组为无序区，第一次交换后无序区减一，有序区增一。
每一次交换，都是大根堆的堆顶元素插入有序区，所以有序区保持是有序的。
代码实现
?static void Main(string[] args)
? ? ? ? {
? ? ? ? ? ? point2(9);
? ? ? ? ? ? bool b = point1(9);
? ? ? ? ? ? Console.WriteLine(b);
? ? ? ? ? ? int[] p = new int[] { 4, 2, 5, 1, 7, 8, 9, 90, 999 };
? ? ? ? ? ? //堆排序
? ? ? ? ? ? point(p);
? ? ? ? ? ? foreach (var item in p)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Console.WriteLine(item);
? ? ? ? ? ? }
? ? ? ? }
public static void point(int[] p)
? ? ? ? {
? ? ? ? ? ? int num = p.Length;
? ? ? ? ? ? for (int i = num / 2; i >= 1; i--)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? //构造大顶堆
? ? ? ? ? ? ? ? print(p, i, num);
? ? ? ? ? ? }
? ? ? ? ? ? while (num > 1)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Jiao(p, 0, num - 1);
? ? ? ? ? ? ? ? num--;
? ? ? ? ? ? ? ? print(p, 1, num);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? public static void point2(int a)
? ? ? ? {
? ? ? ? ? ? if (a % 2 == 0)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Console.WriteLine(false);
? ? ? ? ? ? }
? ? ? ? ? ? else { Console.WriteLine(true); }
? ? ? ? }
? ? ? ? public static bool point1(int a)
? ? ? ? {
? ? ? ? ? ? return (a & 1) == 1;//如果尾数为1 就是奇数
? ? ? ? }
? ? ? ? public static void print(int[] p, int i, int num)
? ? ? ? {
? ? ? ? ? ? if (2 * i > num)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? ? ? if (2 * i == num)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if (p[2 * i - 1] > p[i - 1])
? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? //交换
? ? ? ? ? ? ? ? ? ? Jiao(p, 2 * i - 1, i - 1);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? return;
? ? ? ? ? ? }
? ? ? ? ? ? if (p[2 * i - 1] > p[i - 1] && p[2 * i - 1] >= p[2 * i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Jiao(p, 2 * i - 1, i - 1);
? ? ? ? ? ? ? ? print(p, 2 * i, num);
? ? ? ? ? ? }
? ? ? ? ? ? if (p[2 * i] > p[i - 1] && p[2 * i] > p[2 * i - 1])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? Jiao(p, 2 * i, i - 1);
? ? ? ? ? ? ? ? print(p, 2 * i + 1, num);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? public static void Jiao(int[] p, int a, int b)
? ? ? ? {
? ? ? ? ? ? int tmp = p[a];
? ? ? ? ? ? p[a] = p[b];
? ? ? ? ? ? p[b] = tmp;
? ? ? ? }