排序算法（四）

前言

上篇文章排序算法（三）我们介绍了7种排序算法。

可以知道到目前我们已经介绍了27种排序算法，当然，不仅仅如此，还有若干排序算法，我们今天继续来看一下。

正文

今天我们介绍4种排序算法，它们如下：

Sort Name	Time(Best)	Time(Average)	Time(Worst)	Memory	Stable
IntroSort	O(n * log n)	O(n * log n)	O(n * log n)	O(log n)	No
SmoothSort	O(n)	O(n * log n)	O(n * log n)	O(1)	No
TreeSelectionSort	O(n * log n)	O(n * log n)	O(n * log n)	O(n)	Yes
AmericanFlagSort	O(n * k/d)	O(n * k/d)	O(n * k/d)	O(1)	No

我们分别来看下。

内省排序（IntroSort）

简介及原理

内省排序（Introspective Sort）是一种比较排序算法，也是一个混合排序算法，是由David Musser在1997年设计的排序算法。

它内部使用了快速排序（QuickSort）、堆排序（HeapSort）和插入排序（InsertionSort）三种排序算法。

该排序算法的主要策略如下：

1. 数据量大时采用快速排序（QuickSort），分段递归排序；
2. 一旦分段后的数据量小于某个阈值，为避免快排的递归调用带来的额外负荷，就改用插入排序（InsertionSort）；
3. 如果递归层次过深，就会采用堆排序（HeapSort）；
4. 三点中值”获取好的数组分割。

关于“三点中值”

内省排序使用的分段递归，每一个数组段都会重复上述 1、2、3 策略部分，内省排序如何对数组进行分段的呢？这就涉及到它的“三点中值”算法了。

我们来看下它的代码：

private static int median3(int[] array, int first, int median, int end) {
    if (array[first] < array[median]) {
        if (array[median] < array[end]) {
            return median;
        } else if (array[first] < array[end]) {
            return end;
        } else {
            return first;
        }
    } else {
        if (array[first] < array[end]) {
            return first;
        } else if (array[median] < array[end]) {
            return end;
        } else {
            return median;
        }
    }
}

逻辑比较好理解：

• 如果数组首部元素比中间元素小：

  • 中间元素小于尾部元素，就取中间的index；
  • 首部元素小于尾部元素，就取尾部的index；
  • 否则取首部的index。

• 如果数组首部元素比中间元素大或者等于：

  • 首部元素小于尾部元素，就取首部的index；
  • 中间元素小于尾部元素，就取尾部的index；
  • 否则取中间的index。

我们知道快排要确立一个基准元素，对于普通快排，我们取a[low]，这儿内省排序中的快排，基准元素的index为 median3(array, begin, begin + (end - begin) / 2, end)，可以看到是寻找的begin，end和begin + (end - begin) / 2这三点的“三点中值”。

算法描述

1. 检测待排序数组长度，如果大于阈值（默认16），就会采用分段递归排序；
2. 递归最大深度为 2 * lg(array.length) ，对于每一段，都会使用快速排序，快排基准值为数组“三点中值”位置的元素值；
3. 当递归深度过大时，就会采用堆排序；
4. 随着不断分割，递归重复上述排序过程，当数组分割后的长度小于阈值时，就采用插入排序完成最后排序过程。

动图演示

代码实现

public class IntroSort {
    /**
     * 数据量的分界线，决定了使用quick sort/heap sort还是insertion sort
     */
    private static final int THRESHOLD = 16;
    /**
     * 堆排序用到的辅助函数
     * @param i
     * @return
     */
    private static int parent(int i) {
        return (i - 1) / 2;
    }
    private static int left(int i) {
        return 2 * i + 1;
    }
    private static int right(int i) {
        return (2 * i + 2);
    }
    private static void swap(int[] array, int index1, int index2) {
        int temp;
        temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
    private static void heapShiftDown(int[] heap, int i, int begin, int end) {
        int l = left(i - begin) + begin;
        int r = right(i - begin) + begin;
        int largest = i;
        //找出左右字节点与父节点中的最大者
        if (l < end && heap[l] > heap[largest]) {
            largest = l;
        }
        if (r < end && heap[r] > heap[largest]) {
            largest = r;
        }
        //若最大者不为父节点，则需交换数据，并持续向下滚动至满足最大堆特性
        if (largest != i) {
            swap(heap, largest, i);
            heapShiftDown(heap, largest, begin, end);
        }
    }
    /**
     * 自底向上的开始建堆，即从堆的倒数第二层开始
     * @param heap
     * @param begin
     * @param end
     */
    private static void buildHeap(int[] heap, int begin, int end) {
        for (int i = (begin + end) / 2; i >= begin; i--) {
            heapShiftDown(heap, i, begin, end);
        }
    }
    /**
     * 堆排序
     * @param heap
     * @param begin
     * @param end
     */
    private static void heapSort(int[] heap, int begin, int end) {
        buildHeap(heap, begin, end);
        for (int i = end; i > begin; i--) {
            swap(heap, begin, i);
            heapShiftDown(heap, begin, begin, i);
        }
    }
    /**
     * 插入排序
     * @param array
     * @param len
     */
    private static void insertionSort(int[] array, int len) {
        int i, j, temp;
        for (i = 1; i < len; i++) {
            //store the original sorted array in temp
            temp = array[i];
            //compare the new array with temp(maybe -1?)
            for (j = i; j > 0 && temp < array[j - 1]; j--) {
                //all larger elements are moved one pot to the right
                array[j] = array[j - 1];
            }
            array[j] = temp;
        }
    }
    /**
     * 三点中值计算
     * @param array
     * @param first
     * @param median
     * @param end
     * @return
     */
    private static int median3(int[] array, int first, int median, int end) {
        if (array[first] < array[median]) {
            return helpMethod(array, first, median, end);
        } else {
            return helpMethod(array, median, first, end);
        }
    }
    private static int helpMethod(int[] array, int first, int median, int end) {
        if (array[median] < array[end]) {
            return median;
        } else if (array[first] < array[end]) {
            return end;
        } else {
            return first;
        }
    }
    /**
     * 对数组分割
     * @param array
     * @param left
     * @param right
     * @param p
     * @return
     */
    private static int partition(int[] array, int left, int right, int p) {
        //选择最右侧的元素作为分割标准
        int index = left;
        swap(array, p, right);
        int pivot = array[right];
        //将所有小于标准的点移动到index的左侧
        for (int i = left; i < right; i++) {
            if (array[i] < pivot) {
                swap(array, index++, i);
            }
        }
        //将标准与index指向的元素交换，返回index，即分割位置
        swap(array, right, index);
        return index;
    }
    /**
     * 递归的对数组进行分割排序
     * @param array
     * @param begin
     * @param end
     * @param depthLimit
     */
    private static void introSortLoop(int[] array, int begin, int end, int depthLimit) {
        //子数组数据量大小，则交给后面的插入排序进行处理
        while ((end - begin + 1) > THRESHOLD) {
            //递归深度过大，则由堆排序代替
            if (depthLimit == 0) {
                heapSort(array, begin, end);
                return;
            }
            --depthLimit;
            //使用quick sort进行排序
            int cut = partition(array, begin, end,
                    median3(array, begin, begin + (end - begin) / 2, end));
            introSortLoop(array, cut, end, depthLimit);
            //对左半段进行递归的sort
            end = cut;
        }
    }
    /**
     * 计算最大容忍的递归深度
     * @param n
     * @return
     */
    private static int lg(int n) {
        int k;
        for (k = 0; n > 1; n >>= 1) {
            ++k;
        }
        return k;
    }
    /**
     * IntroSort排序
     * @param array
     * @param len
     */
    public static void introSort(int[] array, int len) {
        if (len != 1) {
            introSortLoop(array, 0, len - 1, lg(len) * 2);
            insertionSort(array, len);
        }
    }

    public static void main(String[] args) {
        int[] a = new int[100];
        Random r = new Random();
        for (int i=0;i<a.length;i++){
            a[i] = r.nextInt(10000);
        }
        System.out.println("IntroSort排序前：");
        System.out.println(Arrays.toString(a));
        introSort(a,a.length);
        System.out.println("IntroSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 该排序算法吸取了快排、插入排序、堆排的优点，是一种效率较高的排序算法；

• 内省排序算法是C++标准模板库 std::sort采用的算法；

• 该排序算法的时间复杂度：

  • 时间复杂度（最好）： O(n*log n)
  • 时间复杂度（平均）： O(n*log n)
  • 时间复杂度（最差）： O(n*log n)

• 该排序算法的空间复杂度为：O(log n)

• 该排序算法为不稳定排序算法

平滑排序（SmoothSort）

简介及原理

平滑排序（SmoothSort）是一种比较排序算法，是堆排序的一个变体，由 Edsger Dijkstra 在1981年发明并发表。

SmoothSort作为堆排序的变种，与其不同是其引入了斐波那契数列来确定堆排序中子节点的位置。

斐波那契数列（Fibonacci sequence）：又称黄金分割数列、兔子数列，函数表达式为 F[n]=F[n-1]+F[n-2] (n>=3,F[1]=1,F[2]=1)。

可以知道斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368……..

我们平滑排序中，使用的数列和其有细微不同，其函数表达式为 F[n]=F[n-1]+F[n-2]+1 (n>=3,F[1]=1,F[2]=1)。

可以得到SmoothSort使用的数列是这样的 1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973,3193, 5167, 8361, 13529, 21891, 35421, 57313……..

我们来回顾下堆排序原理，堆排序是利用了完全二叉堆（完全二叉树），来在数组里隐式构建一个完全二叉堆。

之所以完全二叉树可以用数组来表示，是因为完全二叉树有一个性质：除了最底层，每一层都是满的，每个结点对应数组中的一个元素。

如下图：

分别是最大完全二叉树堆（特点是父节点的值大于两个小节点的值） 和 最小完全二叉树堆（特点是父节点的值小于两个小节点的值）以及它们分别对应的隐式数组结构。

开始时我们需要构建一个隐式完全二叉堆（从大到小排就构建最小堆、从小到大排就构建最大堆），因为对于一个待排序数组，它目前的顺序不一定符合完全二叉堆的性质。

比如对于数组从小到大排列，堆排序先将数组改造为最大堆，然后将堆顶和堆底元素交换，之后将底部上升，重新构建最大堆，保持最大堆性质。由于堆顶元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分离出堆，重复n-1次之后，数组排列完毕。

如下图：

关于构建最大堆（或者最小堆）和堆调整的相关代码，可以参考上面内省排序代码中的buildHeap和heapShiftDown相关方法。

好，回归到SmoothSort，与堆排序类似，Smooth也是首先将数组转为隐式数组堆结构，然后通过重复提取最大剩余元素（从小到大的排序），并在剩余元素上重新构建最大堆，来生成排序数组的。

我们可以看到，我们的堆排序，隐式堆在数组中表示后，父节点一定是在子节点之前，且初始元素是该隐式堆的根节点。

而SmoothSort有所不同的是，它的父节点总是在子节点之后，就相当于将树倒了过来。

比如一个数组[4,7,8,2,3,1,5,6]，使用堆排序时，初始构建的最大堆是这样的[8,7,5,6,3,1,4,2]，这样构建好后，将8与2换位置，数组变为[2,7,5,6,3,1,4][8]，剩余元素[2,7,5,6,3,1,4]在构建最大堆；

而使用SmoothSort后，初始构建的最大堆变为[3,1,6,2,4,7,5,8]，然后分离8，数组变为[3,1,6,2,4,7,5][8]，剩余部分[3,1,6,2,4,7,5]继续构建最大堆。

可以看到这样的话最大数已经在数组正确的位置，减少了不必要的交换（8已经在最后，堆排序的话还要和底部元素2进行交换）。

我们可以看到对于SmoothSort，其隐式数组结构是确定的，与数组本身无关。

PS：相比堆排序，我们需要构造完全二叉树，即每个父节点下面有两个子节点，但是SmoothSort不用这样，它可以先确定隐式二叉树结构，比如使用完全二叉树，就如上面[3,1,6,2,4,7,5,8]这个例子，也可以不使用这种树结构，比如某个父节点下有三个子节点。

Edsger Dijkstra（该算法作者）使用了一种分割方法，就是我们上面提到的斐波那契数列（Fibonacci sequence），这样的话，形成的树的兄弟节点的子节点永远不可能有相同的节点数（除为1时）。我们可以看看堆排序，使用的完全二叉树，除最后底部外，其他的节点其子节点都只有两个子节点，是固定的。

关于为什么没有使用完全二叉树，算法作者认为使用完全二叉树将会和堆排序有相同的算法效率，而且对于大量数据，使用完全二叉树会被分割成更多子树及子树的子树。

隐式树结构的实现可以很容易地通过一次性地计算斐波那契数字列表和父和子关系表(它们完全不依赖于要排序的值)来实现。但是为了使它成为一种就地（不额外占用空间）排序算法，Edsger Dijkstra以一种巧妙的方式维护了固定数量的整数变量，这样在计算的每个点都可以访问相关信息，而不需要任何表。虽然这样做不会影响算法复杂度，但是代码量大大提高且变得晦涩难懂。

算法描述

1. 对于待排序数组，根据 斐波那契数列 构建堆结构；
2. 每次找到堆结构根节点（最大值）分离出堆结构，剩余部分重新变为合适的堆结构；
3. 依次进行，当取出堆结构最后一个元素时，排序完成。

动图演示

代码实现

public class SmoothSort {
    /**
     * 交换指定数组两个数的位置
     * @param array
     * @param index1
     * @param index2
     */
    private static void swap(int[] array,int index1,int index2) {
        int temp =  array[index1];
        array[index1] = array[index2];
        array[index2] = temp;
    }
    /**
     * 斐波那契数列
     */
    private static int[] leonardo = new int[]{
            1, 1, 3, 5, 9, 15, 25, 41, 67, 109, 177, 287, 465, 753, 1219, 1973,
            3193, 5167, 8361, 13529, 21891, 35421, 57313, 92735, 150049, 242785,
            392835, 635621, 1028457, 1664079, 2692537, 4356617, 7049155, 11405773,
            18454929, 29860703, 48315633, 78176337, 126491971, 204668309, 331160281,
            535828591, 866988873, 1402817465
    };
    /**
     * 堆调整函数
     * @param array
     * @param currentHeap
     * @param levelIndex
     * @param levels
     */
    private static void smoothSortFix(int[] array, int currentHeap, int levelIndex, int[] levels) {
        int prevHeap;
        int maxChild;
        int childHeap1;
        int childHeap2;
        int currentLevel;

        while(levelIndex > 0) {
            prevHeap = currentHeap - leonardo[levels[levelIndex]];
            if(array[currentHeap]< array[prevHeap]) {
                if(levels[levelIndex] > 1) {
                    childHeap1 = currentHeap - 1 - leonardo[levels[levelIndex] - 2];
                    childHeap2 = currentHeap - 1;
                    if(array[prevHeap]< array[childHeap1]) {
                        break;
                    }
                    if(array[prevHeap] < array[childHeap2]){
                        break;
                    }
                }
                swap(array,currentHeap,prevHeap);
                currentHeap = prevHeap;
                levelIndex -= 1;
            } else {
                break;
            }
        }
        currentLevel = levels[levelIndex];
        while(currentLevel > 1) {
            maxChild = currentHeap;
            childHeap1 = currentHeap - 1 - leonardo[currentLevel - 2];
            childHeap2 = currentHeap - 1;

            if(array[maxChild]< array[childHeap1]){
                maxChild = childHeap1;
            }
            if(array[maxChild]< array[childHeap2]) {
                maxChild = childHeap2;
            }
            if(maxChild == childHeap1) {
                swap(array,currentHeap, childHeap1);
                currentHeap = childHeap1;
                currentLevel -= 1;
            }else if(maxChild == childHeap2) {
                swap(array,currentHeap, childHeap2);
                currentHeap = childHeap2;
                currentLevel -= 2;
            } else {
                break;
            }
        }
    }
    /**
     * Smooth排序算法
     * @param array
     * @param size
     */
    public static void smoothSort(int[] array, int size) {
        int[] levels = new int[32];
        int toplevel = 0;
        int i;
        for(i = 1; i < size; i++) {
            if(toplevel > 0 && levels[toplevel - 1] - levels[toplevel] == 1) {
                toplevel -= 1;
                levels[toplevel] += 1;
            } else if(levels[toplevel] != 1) {
                toplevel += 1;
                levels[toplevel] = 1;
            } else {
                toplevel += 1;
                levels[toplevel] = 0;
            }
            smoothSortFix(array, i, toplevel, levels);
        }
        for(i = size - 2; i > 0; i--) {
            if(levels[toplevel] <= 1) {
                toplevel -= 1;
            } else {
                levels[toplevel] -= 1;
                levels[toplevel + 1] = levels[toplevel] - 1;
                toplevel += 1;

                smoothSortFix(array, i - leonardo[levels[toplevel]], toplevel - 1, levels);
                smoothSortFix(array, i, toplevel, levels);
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[10];
        Random r = new Random();
        for (int i=0;i<a.length;i++){
            a[i] = r.nextInt(10000);
        }
        System.out.println("SmoothSort排序前：");
        System.out.println(Arrays.toString(a));
        smoothSort(a,a.length);
        System.out.println("SmoothSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• SmoothSort是排序算法中理论值比较好的，但由于SmoothSort所用的树构建是基于斐波那契数列，复杂度因子较大，所以该算法的实际效率并不是特别好；

• 可以看到SmoothSort在数据基本有序的情况下可以达到O(n)的时间复杂度，比堆排序要好；

• 该排序算法时间复杂度：

  • 时间复杂度（最好）：O(n)
  • 时间复杂度（平均）：O(n * log n)
  • 时间复杂度（最差）：O(n * log n)

• 该排序算法的空间复杂度：O(1)。

• 该排序算法为不稳定排序算法。

树形选择排序（TreeSelectionSort）

简介及原理

树形选择排序（TreeSelectionSort）又称锦标赛排序（TournamentSort），是一种选择排序算法。由于其排序比较过程类似于锦标赛，因此得名锦标赛排序。

对于一个待排序数组，如下[8,6,3,2,9,5]，我们可以两两比较找到一组最小值，拿到这组最小值后在两两比较下去……最终找到最小的值，如下：

[8,6,3,2,9,5]
[6,2,5]
[2,5]
[2]

拿到最小值后，我们把最小值的位置填充为无穷大，继续上述比较逻辑。

[8,6,3,Max,9,5]
[6,3,5]
[3,5]
[3]

依次进行下去，当数组所有值都为无穷大时，我们可以得到有序数组。因为这个过程很像完全二叉树，因此也被叫做树形选择排序。

如下图：

算法描述

1. 对于待排序数组，构建一个满二叉树，节点总数 = 叶子节点数*2-1，其中叶子节点数即为数组长度。可以用数组表示这个满二叉树 int [] tree = new int[totalSize + 1];
2. 填充二叉树叶子节点，需要比较每个节点的“冠军”放入父节点；
3. 每次找到根节点（最小的元素）移走，并将最小元素的位置设置为正无穷；
4. 重复上述比较过程；

动图演示

代码实现

public class TreeSelectionSort {
    public static void treeSelectionSort(int[] array) {
        // 数组长度
        int len = array.length;
        // 对一个满二叉树，节点总数 = 叶子节点数*2-1
        int nodeSize = len * 2 - 1;
        // 这里将用数组表示二叉树的存储结构
        int[] tree = new int[nodeSize + 1];
        /* 填充叶子节点 */
        for (int i = len - 1, j = 0; i >= 0; i--, j++) {
            tree[nodeSize - j] = array[i];
        }
        /* 填充其他节点 */
        for (int i = nodeSize - len; i > 0; i--) {
            tree[i] = tree[i * 2] < tree[i * 2 + 1] ? tree[i * 2] : tree[i * 2 + 1];
        }
        /* 将每次找出的最小元素移走 */
        // 数组a的索引
        int index = 0;
        // 最小值的索引
        int minIndex = 0;
        while (index < len) {
            // 这是tree的根节点，也是最小元素
            int min = tree[1];
            // 将tree中最小的元素取到a[0]中
            array[index++] = tree[1];
            minIndex = nodeSize;
            /* 从最后的叶子节点开始，直到找到最小值的索引 */
            while (tree[minIndex] != min) {
                minIndex--;
            }
            // 将这个最小元素置为最大
            tree[minIndex] = Integer.MAX_VALUE;
            /* 如果这个节点还有父节点，那么就将它的兄弟节点升到父亲节点位置 */
            // 根结点的索引是1
            while (minIndex > 1) {
                // 这个节点是左节点
                if (minIndex % 2 == 0) {
                    tree[minIndex / 2] = tree[minIndex] < tree[minIndex + 1] ? tree[minIndex] : tree[minIndex + 1];
                    minIndex = minIndex / 2;
                } else {// 这个节点是右节点
                    tree[minIndex / 2] = tree[minIndex] < tree[minIndex - 1] ? tree[minIndex] : tree[minIndex - 1];
                    minIndex = minIndex / 2;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[3];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(10000);
        }
        System.out.println("TreeSelectionSort排序前：");
        System.out.println(Arrays.toString(a));
        treeSelectionSort(a);
        System.out.println("TreeSelectionSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 可以看到这种排序算法有辅助存储空间较多、和“最大值”进行多余比较等缺点。为了弥补该缺陷，J. willioms 在1964年提出了堆排序;
• 该排序算法的时间复杂度为：O(n * log n)；
• 该排序算法的空间复杂度为：O(n);
• 该排序算法为稳定排序算法。

美国旗帜排序（AmericanFlagSort）

简介与原理

美国旗帜排序（AmericanFlagSort）是基数排序（RadixSort）的一个变体。

和基数排序不同的是，AmericanFlagSort一般排序从数据高位切入，会用一个数组保存位数据信息，再用一个数组记录数据位置。

之所以称为美国旗帜排序，是因为排序时的算法很像美国星条旗（将数组划分成很多“条纹”）。

我们来看一下：

比如对于一个数组[8,100,7622,520,6542,7,8888,33,1234]，该排序算法会先找到它的最大值8888，并获取其位数，得到最大数为4位数，构建一个长度为10的数组，初始值为0，即[0,0,0,0,0,0,0,0,0,0];

该数组0位表示0-999的数的个数，1位表示1000-1999 的数的个数……依次类推，因此我们可以得到如下数组[5,1,0,0,0,0,1,1,1,0]，同时需要一个位置数组记录位置，默认长度10，初始值为0，即[0,0,0,0,0,0,0,0,0,0]；

如何表示数据位置呢？我们使用offset[0] = 0;offset[i] = count[i - 1] + offset[i - 1];来记录数据位置，得到如下数组[0,5,6,6,6,6,6,7,8,9];

然后结合原数组，将数据按照高位基数排序，得到如下数组[8,100,33,520,7,1234,6542,7622,8888]，继续根据第二高位进行排序，相当于重复上述过程，可以得到数组[8,33,7,100,520,1234,6542,7622,8888];

继续第三高位排序得到[8,7,33,100,520,1234,6542,7622,8888]，继续最后一位排序可以得到[7,8,33,100,520,1234,6542,7622,8888]，为最终有序数组。

算法描述

1. 对于未排序数组，找到它的基数N，比如对于十进制数，基数是10（数的位数为0-9，不可能有其他值）；对于二进制，基数是2 （只有0，1）；对于字符串，通常使用256或者128作为基数；
2. 构建两个数组，一个用于存储数据位信息，另一个用来记录数据位置；
3. 待排序数组根据上面两个数组进行高位排序，排序完成后高位上数字较小者都在前面，较大者在后面；
4. 继续对第二高位、第三高位……重复3过程，直到排序完成。

动图演示

代码实现

public class AmericanFlagSort {
    /**
     * 10位数的基数是10
     */
    private static final int NUMBER_OF_BUCKETS = 10;
    
    public static void americanFlagSort(int[] unsorted) {
        // Max number of digits
        int numberOfDigits = getMaxNumberOfDigits(unsorted);
        int max = 1;
        for (int i = 0; i < numberOfDigits - 1; i++) {
            max *= 10;
        }
        sort(unsorted, 0, unsorted.length, max);
    }
    private static void sort(int[] unsorted, int start, int length, int divisor) {
        // First pass - find counts
        int[] count = new int[NUMBER_OF_BUCKETS];
        int[] offset = new int[NUMBER_OF_BUCKETS];
        int digit = 0;
        for (int i = start; i < length; i++) {
            int d = unsorted[i];
            digit = getDigit(d, divisor);
            count[digit]++;
        }
        offset[0] = start;
        for (int i = 1; i < NUMBER_OF_BUCKETS; i++) {
            offset[i] = count[i - 1] + offset[i - 1];
        }
        // Second pass - move into position
        for (int b = 0; b < NUMBER_OF_BUCKETS; b++) {
            while (count[b] > 0) {
                int origin = offset[b];
                int from = origin;
                int num = unsorted[from];
                unsorted[from] = -1;
                do {
                    digit = getDigit(num, divisor);
                    int to = offset[digit]++;
                    count[digit]--;
                    int temp = unsorted[to];
                    unsorted[to] = num;
                    num = temp;
                    from = to;
                } while (from != origin);
            }
        }
        if (divisor > 1) {
            // Sort the buckets
            for (int i = 0; i < NUMBER_OF_BUCKETS; i++) {
                int begin = (i > 0) ? offset[i - 1] : start;
                int end = offset[i];
                if (end - begin > 1) {
                    sort(unsorted, begin, end, divisor / 10);
                }
            }
        }
    }
    /**
     * 获取最大值 位长度
     * @param unsorted
     * @return
     */
    private static int getMaxNumberOfDigits(int[] unsorted) {
        int max = Integer.MIN_VALUE;
        int temp = 0;
        for (int i : unsorted) {
            temp = (int) Math.log10(i) + 1;
            if (temp > max) {
                max = temp;
            }
        }
        return max;
    }
    /**
     * 获取该位数字
     * @param integer
     * @param divisor
     * @return
     */
    private static int getDigit(int integer, int divisor) {
        return (integer / divisor) % 10;
    }
    
    public static void main(String[] args) {
        int[] a = new int[100];
        Random r = new Random();
        for (int i = 0; i < a.length; i++) {
            a[i] = r.nextInt(10000);
        }
        System.out.println("AmericanFlagSort排序前：");
        System.out.println(Arrays.toString(a));
        americanFlagSort(a);
        System.out.println("AmericanFlagSort排序后：");
        System.out.println(Arrays.toString(a));
    }
}

其他注意事项

• 可以看到该排序和基数排序一样，只能用于正整数或者可以表示成正整数的数据排序；

• 该排序也是一种就地排序算法，除了需要新建两个基数N的数组外，排序过程都是在待排序数组内部进行的；

• 该排序效率最高的时候是处理二进制数据的时候，这时候可以使用移位操作来避免一些求幂运算；

• 因为该排序是比较随机的，每个桶里的数的分布完全取决于数据集，因此该排序对大数据集并不友好；

• 如果对于纯字符串排序，数据量较多的情况下，该排序方法理论上是优于快排的；

• 该排序方法的时间复杂度：

  • 时间复杂度（最好）：O(n*k/d)
  • 时间复杂度（平均）：O(n*k/d)
  • 时间复杂度（最差）：O(n*k/d)

• 该排序算法的空间复杂度：O(1)

• 该排序算法为不稳定排序算法

总结

今天的排序算法就介绍到这里，后面我会介绍两种比较有意思的排序，一个是双调排序，另一个是TimSort，TimSort是目前Java使用的排序，我们来详细了解一下它。对于双调排序，它是一种可以进行多路归并的并行排序算法，也是比较有特点的。

源码

本文所有源码详见我的 GitHub