正文

快速排序学习笔记2006-10-24 20:34:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/wenzhuo316/19696.html

分享到:

  •  分解算法:每趟运算确保比枢轴pivot小的值都在其左边,大的都在右边。

int Partition(SqList &L, int low, int high)
 {
  L.r[0] = L.r[low];//子表中的第一个记录作为枢轴记录
  int pivot = L.r[low].key;//枢轴记录的关键字值
  while (low < high)
  {
   while (low < high && L.r[high].key>pivot)
   {
    high--;
   }
   L.r[low].key = L.r[high].key;
   while (low < high && L.r[low].key<pivot)
   {
    low++;
   }
   L.r[high].key = L.r[low].key;
  }
  L.r[low] = L.r[0];
  return low;
 }

  • 求解过程:递归调用分解函数的过程。 

void QSort(SqList &L,int low,int high)
 { // 对顺序表L中的子序列L.r[low..high]作快速排序。算法10.7
   int pivotloc;
   if(low<high)
   { // 长度大于1
     pivotloc=Partition(L,low,high); // 将L.r[low..high]一分为二
     QSort(L,low,pivotloc-1); // 对低子表递归排序,pivotloc是枢轴位置
     QSort(L,pivotloc+1,high); // 对高子表递归排序
   }
 }

阅读(3660) | 评论(0)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

暂无评论
您需要登录后才能评论,请 登录 或者 注册