排序的稳定性

因为待排序的记录序列中可能存在两个或两个以上的关键字相等的记录， 排序结果可能会存在不唯一的情况。所以就有稳定与不稳定的定义。

假设ki=kj( 1 =< i <= n,1 =< j <= n, i != j)，且在排序前的序列中ri领先于rj。如果排序后ri仍领先于rj，则称所用的排序方法是稳定的；反之，若可能使得排序后的序列中rj领先于ri，则称所用的排序方法是不稳定的。 

只要有一组关键字发生类似情况，就可认为此排序方法是不稳定的。

内排序和外排序

根据在排序过程中待排序记录是否全部放在内存中，排序分为内排序和外排序。

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。

外排序是由于排序的记录个数太多，不能同时放置在内存中，整个排序过程需要在内外存之间多次交换数据才能进行。

对内排序来说，排序算法的性能主要有3个影响因素：

• 时间性能 

  排序算法的时间开销是衡量其好坏的最重要的标志。 

  在内排序中，主要进行两种操作：比较和移动。 

  高效率的内排序算法应该具有尽可能少的关键字比较次数和尽可能少的记录移动次数。

• 辅助空间 

  评估算法的另一个主要标准是执行算法所需要的辅助存储空间。 

  辅助存储空间是除了存放待排序所占用的存储空间外，执行算法所需要的其他存储空间。

• 算法的复杂性 

  指算法本身的复杂性，过于复杂的算法也会影响排序的性能。

接下来就讲各种排序算法。

1. 冒泡排序Bubble Sort

1. 冒泡排序是一种交换排序，它的基本思想是： 

   两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

2. 算法复杂度分析： 

   使用优化后的冒泡排序，最好的情况下，仅需要n - 1次比较，时间复杂度为O(n)；最坏情况下，需要n(n - 1)/2次比较和交换； 

   所以平均时间复杂度为O(n2)。

3. 代码实现：

class BubbleSort {

    // 最简单交换排序，非冒泡排序,比较的不是相邻关键字，但便于理解

    // 比较次数n(n + 1)/2，交换次数会很多，仔细分析下，会把小的数字放到最后去，而冒泡则不会，原因就是比较的是相邻关键字

    static void simpleSwapSort(int[] array) {

        if (array == null || array.length == 0 || array.length == 1) return;

        for (int i = 0, size = array.length; i < size; ++i) {

            //for (int j = 0; j < size; j++) { //这种效率更低 n^2

            for (int j = i + 1; j < size; ++j) {

                if (array[j] < array[i]) {

                    CommonUtil.swap(array, i, j);

                }

            }

        }

    }

    // 正宗的冒泡排序，从最底下开始冒泡，两两比较,每次都将小的往上冒一点

    static void bubbleSort(int[] array) {

        if (array == null || array.length == 0 || array.length == 1) return;

        for (int i = 1, size = array.length; i < size; ++i) {

            for (int j = size - 1; j >= i; --j) {

                if (array[j] < array[j - 1]) {

                    CommonUtil.swap(array, j, j - 1);

                }

            }

            //CommonUtil.printArray(array);

        }

    }

    // 冒泡排序优化，如果经过一轮发现已经是有序的，就不再进行排序

    static void bubbleSortBetter(int[] array) {

        if (array == null || array.length == 0 || array.length == 1) return;

        boolean flag = true;

        for (int i = 1, size = array.length; i < size && flag; ++i) {

            flag = false;

            for (int j = size - 1; j >= i; --j) {//经过一轮循环，发现两两已经是有序的了，就置为false

                if (array[j] < array[j - 1]) {

                    CommonUtil.swap(array, j, j - 1);

                    flag = true;

                }

            }

            //CommonUtil.printArray(array);

        }

    }

}

2. 简单选择排序Simple Selection Sort

1. 选择排序的基本思想： 

   每一次遍历时选取关键字最小的记录作为有序序列的第i个记录。

2. 算法复杂度分析 

   简单选择排序最大的特点就是交换移动数据次数少，但它的比较次数是和数组本身是否有序是无关的，即无论最好最差的情况，都要进行n(n-1)/2次比较；在最好的情况下，不需要进行交换，在最坏的情况下，进行n-1次交换。 

   所以平均时间复杂度为O(n2)。

3. 代码实现：

class SimpleSelectionSort {

    static void simpleSelectionSort(int[] array) {

        if (array == null || array.length == 0 || array.length == 1) return;

        for (int i = 0, size = array.length; i < size; ++i) {

            int minIndex = i;

            for (int j = i + 1; j < size; ++j) {

                if (array[j] < array[minIndex]) {

                    minIndex = j;

                }

            }

            if (minIndex != i) {

                CommonUtil.swap(array, i, minIndex);

            }

        }

    }

}

3. 直接插入排序Straight Insertion Sort

1. 直接插入排序的基本操作： 

   将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录递增1的有序表。 

   插入排序是进行值移动，而是不值交换。所以在量较小的情况下插入排序性能要优于冒泡和简单选择排序。

2. 算法复杂度分析： 

   在最好的情况下，只需进行比较n - 1次，无需进行移动； 

   在最坏的情况下，比较(n + 2)(n - 1)/2次，交换(n + 4)(n - 1)/2次。 

   所以平均时间复杂度O(n2)

3. 实现如下：

class StraightInsertionSort {

    static void straightInsertionSort(int[] array) {

        if (array == null || array.length == 0 || array.length == 1) return;

        // 默认array[0]是有序的，将剩下的插入到该有序数组中

        for (int i = 1, j, temp, size = array.length; i < size; ++i) {

           // if (array[i] < array[i - 1]) { //如果小于，将array[i]插入该有序数组中，可以不用判断

                //寻找合适的j

                j = i - 1;

                temp = array[i];//需要一个辅助空间，赋值操作也是移动操作

                // 边移动边查找，可以使用二分查找法

                while (j >= 0 && array[j] > temp) { //持续移动，直到找到合适的位置

                    array[j + 1] = array[j];//向后移

                    --j;

                }

                array[j + 1] = temp;//移动

            }

        //}

    }

    //for循环

    static void straightInsertionSort2(int[] array) {

        if (array == null || array.length == 0 || array.length == 1) return;

        for (int i = 1, j, temp, size = array.length; i < size; ++i) {

            temp = array[i];

            for (j = i - 1; j >= 0 && array[j] > temp; --j) {

                array[j + 1] = array[j];//移动而非交换

            }

            array[j + 1] = temp;

        }

    }

}

4. 二分插入排序Binary Insert Sort

二分（折半）插入排序是一种在直接插入排序算法上进行小改动的排序算法。其与直接排序算法最大的区别在于查找插入位置时使用的是二分查找的方式，在速度上有一定提升。

1. 算法复杂度分析： 

   插入每个记录需要O(log i)比较，最多移动i+1次，最少2次。最佳情况O(n log n)，最差和平均情况O(n^2)。 

   总排序码比较次数比直接插入排序的最差情况好得多，但比最好情况要差，所元素初始序列已经按排序码接近有序时，直接插入排序比二分插入排序比较次数少

2. 代码实现：

class BinaryInsertionSort {

    static void binaryInsertionSort(int[] array) {

        if (array == null || array.length == 0 || array.length == 1) return;

        int temp, left, right, middle;

        for (int i = 1, size = array.length; i < size; i++) {

            temp = array[i];

            left = 0;

            right = i - 1;

            //寻找合适的位置

            while (left <= right) {

                middle = (left + right) / 2;

                if (array[middle] > temp) {

                    right = middle - 1;

                } else {

                    left = middle + 1;

                }

            }

            for (int j = i - 1; j >= left; j--) {

                array[j + 1] = array[j];

            }

            array[left] = temp;

        }

    }

}

5. 希尔排序Shell Sort

1. 希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。 

   希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已排好的了（此时插入排序较快）。

2. 更好的理解方式 

   将数组列在一个表中并对行排序（用插入排序）。重复这过程，不过每次用更小的列来进行。最后整个表就只有一列了。 

   将数组转换至表是为了更好地理解这算法，算法本身仅仅对原数组进行排序（通过增加索引的步长，例如是用i += step_size而不是i++）。 

   比如第一次放在5列中对每行使用快速排序排序，第二次放在3列中，最后放在1列中。类比于步长从5到3再到1。

3. 算法复杂度分析 

   希尔排序的算法复杂度和增量序列有关，只要最终步长为1任何步长序列都可以工作。可以参加希尔排序。

4. 代码实现

class ShellSort {

    static void shellSort(int[] array) {

        if (array == null || array.length == 0 || array.length == 1) return;

        //计算步长

        int gap = 1, size = array.length;

        while (gap < size / 3) {

            gap = gap * 3 + 1; // O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ...

        }

        while (gap > 0) {

            for (int i = gap, j, temp; i < size; ++i) {

                temp = array[i];

                for (j = i - gap; j >= 0 && array[j] > temp; j -= gap) {

                    array[j + gap] = array[j];

                }

                array[j + gap] = temp;

            }

            gap /= 3;

        }

    }

}

6. 堆排序Heap Sort

1. 堆 

   堆是具有下列性质的完全二叉树： 

   每个节点的值都大于或等于其左右孩子节点的值，成为大顶堆； 

   每个节点的值都小于或等于其左右孩子节点的值，成为小顶堆；

2. 完全二叉树性质 

   按完全二叉树的性质，该树可以被顺序存储在数组中，按不同的角标进行表示。 

   即： 

   Parent(i) = (i-1)/2，i 的父节点下标 

   Left(i) = 2i + 1，i 的左子节点下标 

   Right(i) = 2(i + 1)，i 的右子节点下标

3. 基本思想 

   将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆定的根节点，将它移走(与堆数组末尾元素交换)，再将剩余n-1个序列重新构造成一个堆，这样就会得到第二大值，以此类推，就能得到一个有序序列了。

4. 算法复杂度分析 

   在构建堆时，对每个非叶子节点来说，最多进行2次比较和互换操作，复杂度为O(n)； 

   在进行排序时，第i次取堆顶记录重新建堆需要用O(log i )时间，并需要取n-1次，所以重建堆的时间为O(nlogn)。 

   所以堆排序的时间复杂度为O(nlogn)。

5. 实现步骤：

   最大堆调整（Max_Heapify）：从堆的倒数第一个非叶子节点作调整，使得子节点永远小于父节点。没有必要从叶子节点开始，叶子节点可以看作是已符合堆特点的节点。

   创建最大堆（Build_Max_Heap）：将堆所有数据重新排序

   堆排序（HeapSort）：移除位在第一个数据的根节点，并做最大堆调整。

6. 代码如下：

class HeapSort {

    static void heapSort(int[] array) {

        if (array == null || array.length == 0 || array.length == 1) return;

        int i, size = array.length;

        /*

            1. 从末端子节点开始作调整，使得子节点永远小于父节点。

            2. 构造大顶堆

        */

        // i = (lastLeftIndex - 1) / 2 = (size -2) /2即堆的末端子节点，

        // 从末子节点往上开始调整堆，使得子节点永远小于父节点。

        for (i = (size - 2) >> 1; i >= 0; --i) {

            //maxHeapify(array, i, size);

            maxHeapify3(array, i, size);

        }

        /*

            3. 交换堆顶元素和末尾元素，重新调整剩下元素为大顶堆

         */

        for (i = size - 1; i > 0; --i) {

            CommonUtil.swap(array, 0, i);//将堆顶元素和末尾元素交换

            //maxHeapify(array, 0, i);//将剩下的元素调整为大顶堆

            maxHeapify3(array, 0, i);//将剩下的元素调整为大顶堆

        }

    }

    /**

     * 调整索引为 index 处的数据，使其符合堆的特性。

     * 使array[index...len]成为大顶堆

     *

     * 使用递归

     *

     * @param index 需要堆化处理的数据的索引

     * @param len 未排序的堆（数组）的长度,注意处理下标

     */

    private static void maxHeapify(int[] array, int index, int len) {

        int li = (index << 1) + 1; // 左子节点索引

        int ri = li + 1;           // 右子节点索引

        int cMax = li;             // 子节点值最大索引，默认左子节点。

        if (li > len - 1) { // 左子节点索引超出计算范围(数组长度)，直接返回。

            // 这种情况是指已经进入到叶子节点了，非叶子节点必定是有左孩子的。

            return;

        }

        //选择最大的节点的下标

        if (ri < len && array[ri] > array[li]) { // 右子节点在数组内 && 并先判断左右子节点，哪个较大。

            cMax = ri; //两个子节点哪个大

        }

        if (array[cMax] > array[index]) { //子节点大于跟节点，不大顶堆的定义，调换

            CommonUtil.swap(array, cMax, index);      // 如果父节点被子节点调换，

            maxHeapify(array, cMax, len);  // cMax已被换为最大子节点的下标，需要继续判断换下后的父节点是否符合堆的特性。这样就可以不断调整

        }

    }

    /**

     * 调整索引为 index 处的数据，使其符合堆的特性。

     * 使array[index...len]成为大顶堆

     *

     * 使用循环，好理解的写法

     *

     * @param index 需要堆化处理的数据的索引。

     * 构造大顶堆时，挨个传入进来的就是末尾非叶子节点的index，开始调整此index到length间的数组，使其成为大顶堆

     * 进行堆排序时，传入进来的始终是0，len传入的却是length- 1 - i，调整从0到length- 1 - i间的数组，使成为大顶堆

     * <br />

     * @param len 未排序的堆（数组）的长度，始终传的是要排序数组的length。

     */

    private static void maxHeapify3(int[] array, int index, int len) {

        int li, ri, iMax;

        while (true) {

            li = (index << 1) + 1;

            ri = li + 1;

            iMax = index;

            if (li < len && array[li] > array[iMax]) {

                iMax = li;

            }

            if (ri < len && array[ri] > array[iMax]) {

                iMax = ri;

            }

            if (iMax == index) {

                // 说明当前小树就是堆，不用重排

                break;

            } else {

                CommonUtil.swap(array, iMax, index);

                index = iMax;

            }

        }

    }

}

7. 归并排序Merge Sort

1. 概念 

   归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的典型应用。 

   它指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。

2. 算法思路

   把 n 个记录看成 n 个长度为 l 的有序子表

   进行两两归并使记录关键字有序，得到 n/2 个长度为 2 的有序子表

   重复第 2 步直到所有记录归并成一个长度为 n 的有序表为止。

3. 算法复杂度分析： 

   在最后一步，需要依次遍历两个已排序的好的数组，此时的时间复杂度为O(n)。 

   同时又进行着二路归并，形成一颗完全二叉树，此时整个排序需要进行log2n次。 

   所以归并排序的时间复杂度为O(nlogn)。这是它的最好、最坏、平均的时间性能。

4. 代码实现：

class MergeSort {

    /*

     递归实现

    */

    static void mergeSort(int[] array) {

        int length = array.length;

        int[] result = new int[length];//新声明一个同样长度数组，用于存储排序后的数组，可使用插入排序替换

        merge_sort_recursive(array, result, 0, length - 1);//传入最后一个元素下标会好理解很多

    }

    private static void merge_sort_recursive(int[] arr, int[] result, int start, int end) {

        if (start >= end) return;

        int mid = start + ((end - start) >> 1);

        // 递归不断拆分

        merge_sort_recursive(arr, result, start, mid);

        merge_sort_recursive(arr, result, mid + 1, end);

        // 从最小的两个有序数组合并

        merge(arr, result, start, mid, end);

    }

    /**

     * 合并两个有序数组

     *

     * 将arr[start...mid]和arr[mid + 1...end]合并为有序的result，并重新赋值给arr

     */

    private static void merge(int[] arr, int[] result, int start, int mid, int end) {

        int i = start, j = mid + 1, k = start; //i是前半部分下标、j是后半部分下标、k是result下标

        while (i <= mid && j <= end) {

            result[k++] = arr[i] < arr[j] ? arr[i++] : arr[j++];

        }

        while (i <= mid) result[k++] = arr[i++];

        while (j <= end) result[k++] = arr[j++];

        for (k = start; k <= end; ++k) {

            arr[k] = result[k];

        }

    }

    /*

      迭代实现

    */

    static void mergeSortWhile(int[] arr) {

        int len = arr.length;

        int[] result = new int[len];

        int block, start;

        // 原版代码的迭代次数少了一次，没有考虑到奇数列数组的情况

        for (block = 1; block < len * 2; block *= 2) { // block从1开始，1、2、4...这样进行拆分进行归并

            for (start = 0; start < len; start += 2 * block) {

                // block = 1时，start = 0、2、4、6、8、10、12...

                // block = 2时，start = 0、4、8、12、16...

                // block = 4时，start = 0、8、16...

                int mid = (start + block) < len ? (start + block) : len;

                int end = (start + 2 * block) < len ? (start + 2 * block) : len;

                merge(arr, result, start, --mid, --end);//merge函数计算的是下标，所以需要减去一位

            }

        }

    }

}

8. 快速排序Quick Sort

1. 基本思想 

   通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分小，则可分别对这两部分记录继续进行排序，直到整个序列有序。

2. 复杂度分析 

   最好情况：partition每次划分的都很均匀，如果排序n个关键字，其递归树的深度就为floor(log2n)+ 1次，此时的复杂度为O(nlogn)。 

   如果是最坏情况，每次partition都只操作一个数字，该递归树即为一颗斜树，比较次数为n(n - 1)/2，时间复杂度为O(n2)。 

   平均复杂度为O(nlogn)。

3. 实现代码

class QuickSortWhile {

    private static final int MAX_LIMIT = 4;

    static void quickSort(int[] arr) {

        if (array == null || array.length == 0 || array.length == 1) return;

        quick_sort_recursive(arr, 0, arr.length - 1);

    }

    private static void quick_sort_recursive(int[] arr, int start, int end) {

        if (end - start <= MAX_LIMIT) {

            // 到达一定程度的小数组时使用插入排序

            insertSort(arr, start, end);

            return;

        }

        while (start < end) { //尾递归优化

            int pivot = partition(arr, start, end);

            quick_sort_recursive(arr, start, pivot - 1);

            start = pivot + 1;

        }

    }

    /*

       分区操作：将arr[end]作为中轴，比它小的放在前面，比它大的放在后面

    */

    private static int partition(int[] arr, int start, int end) {

        int pivotKey = arr[end];

        int left = start, right = end - 1;

        while (left < right) {

            while (arr[left] <= pivotKey && left < right) left++;

            while (arr[right] >= pivotKey && left < right) right--;

            if (left < right) {

                CommonUtil.swap(arr, left, right);

            }

        }

        if (arr[left] >= pivotKey) {

            CommonUtil.swap(arr, left, end);

        } else {

            left++;

        }

        return left;

    }

    //插入排序

    private static void insertSort(int[] arr, int start, int end) {

        for (int i = start + 1, j, temp; i <= end; ++i) {

            temp = arr[i];

            j = i - 1;

            while (j >= start && arr[j] > temp) {

                arr[j + 1] = arr[j];

                j--;

            }

            arr[j + 1] = temp;

        }

    }

}

9. 桶排序Bucket Sort

1. 基本思想 

   工作的原理是将数组分到有限数量的桶里。每个桶再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。

2. 步骤

   设置一个定量的数组当作空桶子。

   寻访序列，并且把项目一个一个放到对应的桶子去。

   对每个不是空的桶子进行排序。

   从不是空的桶子里把项目再放回原来的序列中。

3. 算法复杂度 

   对于N个待排数据，M个桶，平均每个桶[N/M]个数据的桶排序平均时间复杂度为： 

   O(N)+O(M*(N/M)log(N/M))=O(N+N(logN-logM))=O(N+N*logN-N*logM) 

   可以看出，最好情况即当N=M时，每个桶只有一个数据时，能够达到O(N)。

4. 代码实现

class BucketSort {

    /**

     * 使用数组结构来完成桶排序

     *

     * @param step 表示一个桶内放几个数字

     */

    static void bucketSort(int[] array, int step) {

        if (array == null || array.length == 0 || array.length == 1) return;

        int max = array[0], min = array[0], length = array.length;

        for (int i = 1; i < length; ++i) {

            max = array[i] > max ? array[i] : max;

            min = array[i] < min ? array[i] : min;

        }

        // 计算桶个数

        int num = (int) Math.ceil((max - min + 1) / (step + 0F));

        if (num < 1) num++;

        // 建桶,使用二维数组来存储，Integer可以避免数字为0而无法区分的情况

        List<List<Integer>> list = new LinkedList<List<Integer>>();

        for (int i = 0; i < num; ++i) {

            list.add(new LinkedList<Integer>());

        }

        // 将数据放入对应桶内

        for (int i = 0; i < length; i++) {

            int index = (array[i] - min) / step;

            list.get(index)

                    .add(array[i]);

        }

        // 对每个桶内部排序（可以递归桶排序）

        for (int i = 0; i < num; i++) {

            list.set(i, sort(list.get(i)));

        }

        // 将排序后的桶放回数组

        int k = 0;

        for (int i = 0, size = list.size(); i < size; ++i) {

            List<Integer> temp = list.get(i);

            for (int j = 0; j < temp.size(); j++) {

                array[k] = temp.get(j);

                k++;

            }

        }

    }

    private static List<Integer> sort(List<Integer> list) {

        //使用插入排序

        if (list == null) return null;

        for (int i = 1, j, temp, size = list.size(); i < size; ++i) {

            j = i - 1;

            temp = list.get(i);

            while (j >= 0 && list.get(j) > temp) {

                list.set(j + 1, list.get(j));

                --j;

            }

            list.set(j + 1, temp);

        }

        System.out.println(list.toString());

        return list;

    }

}

10. 计数排序Count Sort

1. 基本思想 

   计数排序是一种稳定的线性时间排序算法。 

   计数排序使用一个额外的数组C，其中C数组的第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。 

2. 步骤：

   找出待排序的数组中最大和最小的元素

   统计数组中每个值为i的元素出现的次数，存入数组 C 的第 i 项

   对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）

   反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

3. 算法复杂度分析 

   当输入的元素是n个0到k之间的整数时，它的运行时间是Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。 

   由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。

4. 实现代码

class CountSort {

    static int[] countSort(int[] a) {

        int b[] = new int[a.length];

        int max = a[0], min = a[0];

        for (int i : a) {

            max = i > max ? i : max;

            min = i < min ? i : min;

        }

        //这里k的大小是要排序的数组中，元素大小的极值差+1

        int k = max - min + 1;

        int c[] = new int[k];

        /*

            a[i]的出现次数放在数组c的第a[i] - min个中

            即：min + i 出现了 c[i]次

         */

        for (int i = 0; i < a.length; ++i) {

            c[a[i] - min] += 1;

        }

        /*

            统计出小于等于a[i]的个数有几个

         */

        for (int i = 1; i < c.length; ++i) {

            c[i] = c[i] + c[i - 1];

        }

        /*

            例如有10个年龄不同的人，统计出有8个人的年龄比A小，那A的年龄就排在第9位，用这个方法可以得到其他每个人的位置，也就排好了序。

         */

        for (int i = a.length - 1; i >= 0; --i) {

            // --c[a[i] - min],小于等于它的有这么多个，就排在这个位置上，数组下标要减1

            // 此处c数组在不断变化，取走一个，小于等于它的便少了一个

            int index = --c[a[i] - min];

            b[index] = a[i];//按存取的方式取出c的元素

        }

        return b;

    }

}

11. 基数排序Radix Sort

1. 基本概念 

   基数排序（英语：Radix sort）是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。 

   由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

2. 实现步骤 

   将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

3. 算法复杂度分析 

   基数排序的时间复杂度是O(kn)，其中n是排序元素个数，k是数字位数。k决定了进行多少轮处理，而n是每轮处理的操作数目。

4. 实现代码

class RadixSort {

    static void radixSort(int[] arr) {

        if (array == null || array.length == 0 || array.length == 1) return;

        /*

            1. 计算最大位数

         */

        int maxBit = maxBit(arr);

        System.out.println(maxBit);

        /*

            2. 获取每一位，使用计数排序进行排序

         */

        int j, k, radix = 1, length = arr.length;

        int[] count = new int[10]; // 0 ~ 9

        int[] temp = new int[length];

        for (int i = 1; i <= maxBit; ++i) {

            for (j = 0; j < 10; ++j) {

                count[j] = 0; //初始化

            }

            //统计位数为i的个数

            for (j = 0; j < length; ++j) {

                k = (arr[j] / radix) % 10;

                ++count[k];

            }

            // 位数小于等于i的个数

            for (j = 1; j < 10; ++j) {

                count[j] = count[j] + count[j - 1];

            }

            //开始排序

            for (j = length - 1; j >= 0; j--) {//将所有桶中记录依次收集到tmp中

                k = (arr[j] / radix) % 10;

                temp[count[k] - 1] = arr[j];

                count[k]--;

            }

            for (j = 0; j < length; ++j) {

                arr[j] = temp[j];

            }

            radix *= 10;

        }

    }

    private static int maxBit(int[] arr