堆排序和快排

堆排序

 //heapSort 构建大顶堆或者小顶堆，将堆顶元素与堆尾元素交换后再调整，如此反复
public void heapSort(int[] arr)
{
    //构建大顶堆 k为最后一个非叶子节点，逐渐-1，即从下向上，从右往左
    for(int k = arr.length/2 - 1;k>=0;k--)
    {
        adjustHeap(arr,k,arr.length);
    }

    //排序 交换+调整
    int temp =0;
    for (int i = arr.length-1; i >= 0; i--) 
    {
        temp =arr [0];
        arr[0] = arr[i];
        arr[i] = temp;
        adjustHeap(arr,0,i);
    }
}

/**
     *
     * @param arr 待调整数组
     * @param i 非叶子节点在数组中的索引
     * @param length 对多少个元素进行调整
     */
public void adjustHeap(int[] arr,int i,int length)
{
    int temp = arr[i];//取出当前非叶子叶结点的值
    //k为当前节点的左子节点
    for(int k = 2*i+1;k<length;k=2*k+1)
    {
        if(k+1<length && arr[k+1]>arr[k])
        {//右子节点大于左子节点
            k++;//k指向右子节点
        }
        if(arr[k]>temp)
        {
            //如果当前节点大于父节点就交换
            arr[i] = arr[k];
            i = k;//!!!!!!精髓，因为该子节点值大小发生了改变，可能会使其子根堆发生改变，索引要调整其子根堆
        }
        else 
        {
            break;//否则直接退出，因为其后面的节点一定满足堆定义
        }
    }
    arr[i] = temp;
}

• 一个对象的下标为i，他的左右子节点分别是2i+1和2i+2
• 更换节点的时候

快排

//quickSort 每次选择一个元素并且将整个数组以这个元素分为两部分，小于该元素的放右边，大于该元素的放左边
public void quickSort(int[] arr,int l,int r)
{
    if(l<r){ //跳出递归的条件
        //partition就是划分操作，将arr划分成满足条件的两个子表
        int pivotpos = partition(arr,l,r);
        //依次对左右两个子表进行递归排序
        quickSort(arr,l,pivotpos);
        quickSort(arr,pivotpos+1,r);
    }
}

public int partition(int[] arr,int l,int r)
{
    //以当前数组的最后一个元素作为中枢pivot，进行划分
    int pivot = arr[r];
    while (l<r)
    {
        while (l<r && arr[l]<pivot) l++;
        arr[r] = arr[l];//将比中枢值大的移动到右端r处 由于r处为中枢或者该位置值已经被替换到l处，所以直接可以替换
        while (l<r && arr[r]>=pivot) r--;
        arr[l] = arr[r];//将比中枢值小的移动到左端l处 由于前面l处的值已经换到r处，所以该位置值也可以替换掉
    }
    //l==r时，重合，这个位置就是中枢的最终位置
    arr[l] = pivot;
    //返回存放中枢的最终位置
    return l;
}

• 主要的思路是每次选择一个（实际上一般是最右边的那一个）元素作为标准，将比这个元素小的元素移动到数组的左边，大的移动到右边，最后实现这个元素的左边的所有元素都比这个元素小，右边的都比这个大。然后再分别对左边和右边的数组分别排序，实现递归。

  Leetcode 295. 数据流的中位数

• 用一个最小堆记录大于中位数的数字，和一个最大堆记录小于中位数的数字
• 新加入的数字与小于中位数的数字中的最大值比较，决定插入哪个堆
• 根据总数替换中位数的值

  class MedianFinder {
  public:
      priority_queue<int, vector<int>, less<int>> queMin;
      priority_queue<int, vector<int>, greater<int>> queMax;
  
      MedianFinder() {}
  
      void addNum(int num) {
          if (queMin.empty() || num <= queMin.top()) {
              queMin.push(num);
              if (queMax.size() + 1 < queMin.size()) {
                  queMax.push(queMin.top());
                  queMin.pop();
              }
          } else {
              queMax.push(num);
              if (queMax.size() > queMin.size()) {
                  queMin.push(queMax.top());
                  queMax.pop();
              }
          }
      }
  
      double findMedian() {
          if (queMin.size() > queMax.size()) {
              return queMin.top();
          }
          return (queMin.top() + queMax.top()) / 2.0;
      }
  };