Skynet

          ---------- ---------- 我的新 blog : liukaiyi.cublog.cn ---------- ----------

            BlogJava :: 首頁 :: 聯(lián)系 :: 聚合  :: 管理
            112 Posts :: 1 Stories :: 49 Comments :: 0 Trackbacks

          # 快排 和 分治 很像 都是分而治之 ,但他們卻是 相反的 方式排序 :
          分治 是想拆分完成后,合并以有序的小段進(jìn)行 排序 ,而快排是直接由原始的“拆分”來排序


          #encoding=utf-8
          #
          從 大 到 小
          def partition(A,p,r):
              tmp
          =A[p]
              
          while True :
                  
          while p+1<and A[p] > tmp : p+=1
                  
          while r-1>and A[r] <= tmp : r-=1    
              
          if A[p]<=A[r]: A[p],A[r]=A[r],A[p]
              
          if r-1<=p : return p


          def quickSort(A,p,r):
              
          if p<r:
                  q
          =partition(A,p,r)
                  quickSort(A,p,q)
                  quickSort(A,q
          +1,r)

          A
          =[9,61,7,14,-1,7,667,3,6,8]
          print A
          quickSort(A,0,len(A)
          -1)
          print A
          # 結(jié)果
          [667, 61, 14, 9, 8, 7, 7, 6, 3, -1]



          圖解:
          一次迭代過程描述 (從小到大):
          1. 以 A[0] 為切分點(diǎn) 用臨時(shí)變量 記錄 這里是 切分點(diǎn) = [5]
          2. 分別起 2枚指針 [切分起左,右]
          3. 分別向中間 靠攏 , 當(dāng)左指針指向值大于 切分點(diǎn) 停止 左 , 右指針指向值 小于 切分點(diǎn) 停止 右 。
          4. 判斷 是否是  停止點(diǎn) 上 左值 小于 右值 是:交換兩指針值 !

          第一次迭代后 : 
            以初始分隔 [5]  就已經(jīng)切分好了 小于 5 的左 ,大于等于5 的右




          整理 www.aygfsteel.com/Good-Game
          posted on 2009-12-03 17:11 劉凱毅 閱讀(1686) 評(píng)論(0)  編輯  收藏 所屬分類: python算法/函數(shù)
          主站蜘蛛池模板: 花莲县| 北碚区| 沾益县| 江华| 马鞍山市| 类乌齐县| 宁波市| 甘德县| 吕梁市| 乌兰察布市| 广元市| 星座| 苏尼特左旗| 孝义市| 尚义县| 宁强县| 小金县| 利津县| 突泉县| 息烽县| 安国市| 阿拉善左旗| 精河县| 延寿县| 色达县| 泰安市| 图木舒克市| 淮南市| 越西县| 陕西省| 麻阳| 泰和县| 西华县| 大冶市| 海口市| 大英县| 汕尾市| 靖安县| 辽宁省| 永登县| 揭东县|