QuickSort.java
上传用户:quxuerui
上传日期:2018-01-08
资源大小:41811k
文件大小:3k
源码类别:

网格计算

开发平台:

Java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one
  3.  * or more contributor license agreements.  See the NOTICE file
  4.  * distributed with this work for additional information
  5.  * regarding copyright ownership.  The ASF licenses this file
  6.  * to you under the Apache License, Version 2.0 (the
  7.  * "License"); you may not use this file except in compliance
  8.  * with the License.  You may obtain a copy of the License at
  9.  *
  10.  *     http://www.apache.org/licenses/LICENSE-2.0
  11.  *
  12.  * Unless required by applicable law or agreed to in writing, software
  13.  * distributed under the License is distributed on an "AS IS" BASIS,
  14.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15.  * See the License for the specific language governing permissions and
  16.  * limitations under the License.
  17.  */
  18. package org.apache.hadoop.util;
  19. /**
  20.  * An implementation of the core algorithm of QuickSort.
  21.  */
  22. public final class QuickSort implements IndexedSorter {
  23.   private static final IndexedSorter alt = new HeapSort();
  24.   public QuickSort() { }
  25.   private static void fix(IndexedSortable s, int p, int r) {
  26.     if (s.compare(p, r) > 0) {
  27.       s.swap(p, r);
  28.     }
  29.   }
  30.   /**
  31.    * Deepest recursion before giving up and doing a heapsort.
  32.    * Returns 2 * ceil(log(n)).
  33.    */
  34.   protected static int getMaxDepth(int x) {
  35.     if (x <= 0)
  36.       throw new IllegalArgumentException("Undefined for " + x);
  37.     return (32 - Integer.numberOfLeadingZeros(x - 1)) << 2;
  38.   }
  39.   /**
  40.    * Sort the given range of items using quick sort.
  41.    * {@inheritDoc} If the recursion depth falls below {@link #getMaxDepth},
  42.    * then switch to {@link HeapSort}.
  43.    */
  44.   public void sort(IndexedSortable s, int p, int r) {
  45.     sort(s, p, r, null);
  46.   }
  47.   /**
  48.    * {@inheritDoc}
  49.    */
  50.   public void sort(final IndexedSortable s, int p, int r,
  51.       final Progressable rep) {
  52.     sortInternal(s, p, r, rep, getMaxDepth(r - p));
  53.   }
  54.   private static void sortInternal(final IndexedSortable s, int p, int r,
  55.       final Progressable rep, int depth) {
  56.     if (null != rep) {
  57.       rep.progress();
  58.     }
  59.     while (true) {
  60.     if (r-p < 13) {
  61.       for (int i = p; i < r; ++i) {
  62.         for (int j = i; j > p && s.compare(j-1, j) > 0; --j) {
  63.           s.swap(j, j-1);
  64.         }
  65.       }
  66.       return;
  67.     }
  68.     if (--depth < 0) {
  69.       // give up
  70.       alt.sort(s, p, r, rep);
  71.       return;
  72.     }
  73.     // select, move pivot into first position
  74.     fix(s, (p+r) >>> 1, p);
  75.     fix(s, (p+r) >>> 1, r - 1);
  76.     fix(s, p, r-1);
  77.     // Divide
  78.     int i = p;
  79.     int j = r;
  80.     int ll = p;
  81.     int rr = r;
  82.     int cr;
  83.     while(true) {
  84.       while (++i < j) {
  85.         if ((cr = s.compare(i, p)) > 0) break;
  86.         if (0 == cr && ++ll != i) {
  87.           s.swap(ll, i);
  88.         }
  89.       }
  90.       while (--j > i) {
  91.         if ((cr = s.compare(p, j)) > 0) break;
  92.         if (0 == cr && --rr != j) {
  93.           s.swap(rr, j);
  94.         }
  95.       }
  96.       if (i < j) s.swap(i, j);
  97.       else break;
  98.     }
  99.     j = i;
  100.     // swap pivot- and all eq values- into position
  101.     while (ll >= p) {
  102.       s.swap(ll--, --i);
  103.     }
  104.     while (rr < r) {
  105.       s.swap(rr++, j++);
  106.     }
  107.     // Conquer
  108.     // Recurse on smaller interval first to keep stack shallow
  109.     assert i != j;
  110.     if (i - p < r - j) {
  111.       sortInternal(s, p, i, rep, depth);
  112.       p = j;
  113.     } else {
  114.       sortInternal(s, j, r, rep, depth);
  115.       r = i;
  116.     }
  117.     }
  118.   }
  119. }