HeapSort堆排序

/*

• @Author: sumBorn
• @Date: 2022-03-01 21:45:51
• @Description:

空间复杂度O(NlogN)
时间复杂度O(1)
不稳定排序

堆的基本思想：

• 和树的区别 https://www.jianshu.com/p/6b526aa481b1
• shiftUp()：对于最大堆来说，如果某个节点比自己父节点大，就要往上移，和父节点交换位置
• shiftDown()<堆化>：对于最大堆来说，如果某个节点比自己父节点小，就要往下移，和子节点交换位置、
• 两者都是一个递归的过程，所以时间复杂度是O(logN)

基本步骤：

1. 对序列进行原地建堆
2. 重复以下流程,直到元素个数为1

• 交换堆顶元素与堆尾元素
• 堆的元素数量减1
• 堆0位置的元素进行siftdown操作

例子：
0:{50,21,80,43,38,14}
1:{80,43,50,21,38,14}
2:{50,43,14,21,38,80}
3:{43,38,14,21,50,80}
4:{38,21,14,43,50,80}
...

*/

/**

• @description: 递归实现 看着更棒

• @param {*}

• @return {*}
  */
  public class Solution
  {
  public void HeapSort(int[] arr)
  {
  int endIndex = arr.Length - 1;
  int beginIndex = (endIndex - 1) / 2;//shiftdown第一次判断有子节点的那个父节点，所有的叶子节点都没有子节点根本不需要进行操作，只有有子节点的节点才需要进行操作，所以找到第一个有叶子节点的节点
  for (int i = beginIndex; i >= 0; i--)
  {
  this.Shiftdown(i, arr, endIndex); //需要shiftdown的索引元素，整个数组，这个元素可以down到最低的位置，也就是数组的最末尾
  }

   for (int i = endIndex; i >= 0; i--)
   {
       this.Swap(i, 0, arr);
       this.Shiftdown(0, arr, i - 1);//交换完 down可以的最低位置少了一位
   }
  

  }

  public void Shiftdown(int index, int[] arr, int limitIndex)
  {
  int leftIndex = index * 2 + 1;
  int rightIndex = leftIndex + 1;
  int maxIndex = leftIndex;//先默认左节点比右节点大

   if (leftIndex > limitIndex)
       return;
  
   if (leftIndex < limitIndex && arr[leftIndex] < arr[rightIndex])
       maxIndex = rightIndex;
  
   if (arr[maxIndex] > arr[index])
   {
       this.Swap(maxIndex, index, arr);
       this.Shiftdown(maxIndex, arr, limitIndex);
   }
  

  }

  public void Swap(int i, int j, int[] arr)
  {
  int tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
  }
  }

/**

• @description: 正常实现

• @param {*}

• @return {*}
  */
  public class Solution
  {
  public void HeapSort(int[] arr)
  {
  for (int i = arr.Length / 2 - 1; i >= 0; i--)
  {
  this.Shiftdown(i, arr, arr.Length - 1);
  }

   for (int i = arr.Length - 1; i >= 0; i--)
   {
       this.Swap(i, 0, arr);
       this.Shiftdown(0, arr, i - 1);// 从根节点向下调整，每次取出一个数值，集合长度逐渐减小
   }
  

  }

  public void Swap(int i, int j, int[] arr)
  {
  var tmp = arr[i];
  arr[i] = arr[j];
  arr[j] = tmp;
  }

  public void Shiftdown(int index, int[] arr, int limitIndex)
  {
  int node = arr[index];
  while (index <= limitIndex)
  {
  int leftIndex = 2 * index + 1;
  int rightIndex = 2 * index + 2;
  if (leftIndex > limitIndex)
  {
  //左右节点都没有
  break;
  }
  else if (rightIndex > limitIndex)
  {
  //左节点在，右节点没了
  int left = arr[leftIndex];
  if (left > node)
  {
  arr[index] = left;
  index = leftIndex;
  }
  else
  {
  break;
  }
  }
  else
  {
  //左右节点都在
  int left = arr[leftIndex];
  int right = arr[rightIndex];
  int maxIndex = left >= right ? leftIndex : rightIndex;
  int max = arr[maxIndex];
  if (max < node)
  {
  break;
  }
  else
  {
  //和较大值交换
  arr[index] = max;
  index = maxIndex;
  }
  }
  }
  arr[index] = node;
  }

  public void ShiftUp(int index, int[] arr)
  {
  int node = arr[index];
  while (index > 0)
  {
  int parentIndex = (int)((index - 1) / 2);
  int parent = arr[parentIndex];

       if (parent > node) break;
  
       arr[index] = parent;
       index = parentIndex;
   }
   arr[index] = node;
  

  }
  }