更新时间: 2016-11-23 17:37:19       分类: 算法


# include<iostream>

using namespace std;

int a[10] = {3,7,5,4,0,2,8,6,1,9};

void quicksort(int l,int r)
{
  int base,i,j;//i是右侧探测器,j是左侧探测器

  if(l>r)
    return;//跳出条件
  base = a[l];//选定基准数字

  i = r;j = l;
  while(i!=j)//未相遇之前
  {
    while(a[i] >= base && i > j) i--;
    while(a[j] < base && i > j) j++;

    if(i > j)
    {
      int t = a[i];
      t = a[j];
      a[j] = a[i];
    }
  }

  a[l] = a[i];//i就是基准位置
  a[i] = base;//基准数字归位

  quicksort(l,i-1);
  quicksort(i+1,r);
}

/*
*小顶堆
*/
void heapAdjust(int l,int r)
{
  if(l>=r)
    return;

  int top = a[l];//保留当前的堆顶

  for(int j=2*l+1;j<=r;j=2*j+1)//一直往下筛选找到最后需要插入的位置
  {
    if(j+1 <= r&&a[j] >= a[j+1]) j++;//选择较小的那个子节点
    if(top <= a[j])
      break;//时间优化:不必再调整了直接退出
    a[l] = a[j];
    l = j;
    /*
     从这里开始l和r就是下面要易位的两个数据的位置了
    */
  }

  //上面循环结束之后,l保存的就是最初堆顶那个元素应该插入的位置了
  a[l] = top;
}

void heapSort(int n)
{
  for(int i=n/2;i>=0;i--)
  {
    //从第一个非叶子节点开始,到根节点,不停筛选来创建一个堆
    heapAdjust(i,n);
  }
  for(int i=0;i<n;i++)
  {
    heapAdjust(i,n);
  }

}

int main()
{
  // quicksort(0,9);

  heapSort(9);

  for(int i=0;i<10;i++)
  {
    cout<<a[i]<<endl;
  }

  return 0;
}

There is a bug in HeapSort But I cant find it out


评论

还没有评论