熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

排序 - 交換排序 - 快速排序 (二)

2013-11-15 15:41:05  來源: 數據結構 

  劃分算法Partition

  () 簡單的劃分方法

  ① 具體做法

  第一步(初始化)設置兩個指針i和j它們的初值分別為區間的下界和上界即i=lowi=high;選取無序區的第一個記錄

  R[i](即R[low])作為基准記錄並將它保存在變量pivot中;

  第二步令j自high起向左掃描直到找到第個關鍵字小於pivotkey的記錄R[j]將R[j])移至i所指的位置上這相當於

  R[j]和基准R[i](即pivot)進行了交換使關鍵字小於基准關鍵字pivotkey的記錄移到了基准的左邊交換後R[j]中相當於是

  pivot;然後令i指針自i+位置開始向右掃描直至找到第個關鍵字大於pivotkey的記錄R[i]將R[i]移到i所指的位置上

  相當於交換了R[i]和基准R[j]使關鍵字大於基准關鍵字的記錄移到了基准的右邊交換後R[i]中又相當於存放了pivot;接著令指

  針j自位置j開始向左掃描如此交替改變掃描方向從兩端各自往中間靠攏直至i=j時i便是基准pivot最終的位置

  pivot放在此位置上就完成了一次劃分

  ②一次劃分過程

  一次劃分過程中具體變化情況【 參見動畫演示 】

  ③劃分算法

  int Partition(SeqList Rint iint j)

  {//調用Partition(Rlowhigh)時對R[lowhigh]做劃分

  //並返回基准記錄的位置

  ReceType pivot=R[i]; //用區間的第個記錄作為基准

  while(i

  while(i=pivot.key) //pivot相當於在位置i上

  j--; //從右向左掃描,查找第1個關鍵字小於pivot.key的記錄R[j]

  if(i

  R[i++]=R[j]; //相當於交換R[i]和R[j],交換後i指針加1

  while(i

  i++; //從左向右掃描,查找第1個關鍵字大於pivot.key的記錄R[i]

  if(ipivot.key

  R[j--]=R[i]; //相當於交換R[i]和R[j],交換後j指針減1

  } //endwhile

  R[i]=pivot; //基准記錄已被最後定位

  return i;

  } //partition


From:http://tw.wingwit.com/Article/program/sjjg/201311/23788.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.