十种常见排序算法-JAVA版

概述

数据结构与算法的可视化可以参考Data Structure Visualizations

分类

十种常见的排序算法主要可分为两大类：比较类排序和非比较类排序

• 比较类：通过对数组中的元素进行比较来实现排序，这类算法的时间复杂度下界为$\Omega(nlogn)$；
• 非比较类：利用非比较的方法获得有关输入数组中的排序信息，则可突破$\Omega(nlogn)$的复杂度下界，达到线性复杂度。

复杂度

本来是用的markdown表格，但是这个主题不支持表格中显示公式，所以只好用图片了。有点模糊，请见谅。

以下排序以数组{4, 23, 7, 34, 129, 18, 0, 116, 11, 32, 25}为示例。

比较排序

1. 选择排序

1.1 算法描述

选择排序是一种最简单的排序算法，其命名原因就是不断地选择数组中的最小（大）值。首先，找到数组中最小的元素，然后将它和数组的第一个元素交换位置（如果第一个元素最小就和自己交换）。其次，在剩下的元素中找到最小的元素，将其与数组的第二个元素交换位置，如此直到将整个数组都排好序。

1.2 代码实现

//选择排序
public static int[] SelectionSort(int[] arr)
{
    System.out.println("选择排序");
    int minIdx;
    for(int i=0;i<arr.length-1;i++)
    {
        minIdx = i;
        for(int j=i+1;j<arr.length;j++)
        {
            if(arr[j]<arr[minIdx])
            {
                minIdx = j;
            }
        }
        int temp = arr[i];
        arr[i] = arr[minIdx];
        arr[minIdx] = temp;

        System.out.printf("第%d趟结果为：%s\n", i+1, Arrays.toString(arr));
    }
    return arr;
}

1.3 排序过程

第1趟结果为：[0, 23, 7, 34, 129, 18, 4, 116, 11, 32, 25]
第2趟结果为：[0, 4, 7, 34, 129, 18, 23, 116, 11, 32, 25]
第3趟结果为：[0, 4, 7, 34, 129, 18, 23, 116, 11, 32, 25]
第4趟结果为：[0, 4, 7, 11, 129, 18, 23, 116, 34, 32, 25]
第5趟结果为：[0, 4, 7, 11, 18, 129, 23, 116, 34, 32, 25]
第6趟结果为：[0, 4, 7, 11, 18, 23, 129, 116, 34, 32, 25]
第7趟结果为：[0, 4, 7, 11, 18, 23, 25, 116, 34, 32, 129]
第8趟结果为：[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]
第9趟结果为：[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]
第10趟结果为：[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]

1.4 算法特点

选择排序的总交换次数为N。它有两个鲜明的特点：

• 运行时间和输入无头
• 数据移动是最少

2. 冒泡排序

2.1 算法描述

冒泡排序的基本思想就是比较相邻的元素，根据大小交换位置。算法过程如下：

• 比较相邻元素，若前一个比后一个大，则交换两元素；
• 比较每一对相邻元素，一趟排序过后，最后一个元素即为最大元素；
• 重复这样的过程直到排序完成

2.2 代码实现

//冒泡排序
public static int[] BubbleSort(int[] arr)
{
    System.out.println("冒泡排序");
    for(int i=0;i<arr.length-1;i++)
    {
        for(int j=0;j<arr.length-i-1;j++)
        {
            if(arr[j]>arr[j+1])
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
        }
        System.out.printf("第%d趟结果为：%s\n", i+1, Arrays.toString(arr));
    }
    return arr;
}

2.3 排序过程

第1趟结果为：[4, 7, 23, 34, 18, 0, 116, 11, 32, 25, 129]
第2趟结果为：[4, 7, 23, 18, 0, 34, 11, 32, 25, 116, 129]
第3趟结果为：[4, 7, 18, 0, 23, 11, 32, 25, 34, 116, 129]
第4趟结果为：[4, 7, 0, 18, 11, 23, 25, 32, 34, 116, 129]
第5趟结果为：[4, 0, 7, 11, 18, 23, 25, 32, 34, 116, 129]
第6趟结果为：[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]
第7趟结果为：[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]
第8趟结果为：[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]
第9趟结果为：[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]
第10趟结果为：[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]

3. 插入排序

3.1 算法描述

插入排序是一种简单的排序算法。通过类比整理扑克牌可以很好地理解插入排序的过程。插入排序把数组分为两个部分，左端为有序部分，右端为待插入部分。每次选择右端的第一个元素，插入到左端的相应位置，并将左端比该值大的元素依次右移，直到数组全部被排好序。

3.2 代码实现

//插入排序
public static int[] InsertionSort(int[] arr)
{
    System.out.println("插入排序");
    int cur, j;
    for(int i=1;i<arr.length;i++)
    {
        j = i;
        cur = arr[i];
        while(j-1>=0 && cur<arr[j-1])
        {
            arr[j] = arr[j-1];
            arr[j-1] = cur;
            j--;
        }
        System.out.printf("第%d趟结果为：%s\n", i, Arrays.toString(arr));
    }
    return arr;
}

3.3 排序过程

第1趟结果为：[4, 23, 7, 34, 129, 18, 0, 116, 11, 32, 25]
第2趟结果为：[4, 7, 23, 34, 129, 18, 0, 116, 11, 32, 25]
第3趟结果为：[4, 7, 23, 34, 129, 18, 0, 116, 11, 32, 25]
第4趟结果为：[4, 7, 23, 34, 129, 18, 0, 116, 11, 32, 25]
第5趟结果为：[4, 7, 18, 23, 34, 129, 0, 116, 11, 32, 25]
第6趟结果为：[0, 4, 7, 18, 23, 34, 129, 116, 11, 32, 25]
第7趟结果为：[0, 4, 7, 18, 23, 34, 116, 129, 11, 32, 25]
第8趟结果为：[0, 4, 7, 11, 18, 23, 34, 116, 129, 32, 25]
第9趟结果为：[0, 4, 7, 11, 18, 23, 32, 34, 116, 129, 25]
第10趟结果为：[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]

3.4 算法特点

其所需时间取决于输入元素的初始顺序，适合小规模的数组。

4. 希尔排序

4.1 算法描述

希尔排序是一种基于插入排序的快速的排序算法。插入排序对于大规模乱序数组速度很慢，这主要是因为其在插入的过程中，只交换相邻两个元素。而希尔排序则交换不相邻的元素以对数组的局部进行排序，最终用插入排序将局部有序的数组排序。希尔排序是第一个突破$O(n^2)$的排序算法。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的，这样的数组称为h有序数组。在橙书《算法》中，希尔排序的h有序数组使用序列$1/2(3^k-1)$，从$N/3$开始递减至1。如下的实现由于数组只有10个所以用1, 4, 13, 40, 121, 364, 1093, ...这样的递增序列无法较为清楚地展示希尔排序的过程，因而选择使用$N/2$的方法。

4.2 代码实现

//希尔排序
public static int[] ShellSort(int[] arr)
{
    System.out.println("希尔排序");
    int len = arr.length;
    int cnt = 1;
    int cur, j;
    for(int gap=len/2;gap>0;gap=gap/2)
    {
        //注意此处i的终止条件，i和简单插入排序一样要跑到最后的
        for(int i=gap;i<len;i++)
        {
            j = i;
            cur = arr[j];
            while(j-gap>=0 && cur<arr[j-gap])
            {
                arr[j] = arr[j-gap];
                arr[j-gap] = cur;
                j -= gap;
            }
        }
        System.out.printf("第%d趟增量为%d，结果为：%s\n", cnt, gap, Arrays.toString(arr));
        cnt++;
    }
    return arr;
}

4.3 排序过程

第1趟增量为5，结果为：[4, 0, 7, 11, 32, 18, 23, 116, 34, 129, 25]
第2趟增量为2，结果为：[4, 0, 7, 11, 23, 18, 25, 116, 32, 129, 34]
第3趟增量为1，结果为：[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]

4.4 算法特点

希尔排序的代码量很小，且不需要额外的内存空间，对于中等大小的数组其运行时间可接受。后续介绍的归并、快排和堆排序更加高效，但除了对于很大的$N$，这些高级的排序算法可能只比希尔排序快两倍，而且更复杂。所以当需要解决一个排序问题而没有api（如嵌入式系统中）时，就可用希尔排序。

5. 归并排序

5.1 算法描述

归并排序是一种建立在归并操作上的典型的基于分治法的排序算法。算法递归地将数组分成两半，分别排序，然后将结果归并起来。

• 原地归并

首先将复制所有元素复制到辅助数组中，然后再归并回原始数组。

方法在归并时进行了4个条件判断：左半边用尽（取右半边的元素）、右半边用尽（取左半边的元素）、右半边的当前元素小于左半边的当前元素（取右半边的元素）、右半边的当前元素大于等于左半边的当前元素（取左半边的元素）。
——引自橙书

//原地归并
private static void merge(int[] arr, int low, int mid, int high)
{
    int i = low, j = mid + 1;
    int len = high - low + 1;
    System.arraycopy(arr, low, mergeHelperArr, low, len);
//        for(int k=low;k<=high;k++)
//        {
//            temp[k] = ArrToMerge[k];
//        }
    for(int k=low;k<=high;k++)
    {
        //i++ 先赋值，再加1
        /*语句arr[k] = mergeHelperArr[j++];
        相当于如下两句：
        arr[k] = mergeHelperArr[j];
        j++;
         */
        if(i>mid) arr[k] = mergeHelperArr[j++];
        else if(j>high) arr[k] = mergeHelperArr[i++];
        else if(arr[i]<arr[j]) arr[k] = mergeHelperArr[i++];
        else if(arr[i]>arr[j]) arr[k] = mergeHelperArr[j++];
    }
}

5.2 代码实现

//归并排序，参考橙书p170
//Top-Down 递归
private static int[] mergeHelperArr; //辅助数组
public static int[] MergeSort(int[] arr)
{
    System.out.println("归并排序");
    mergeHelperArr = new int[arr.length];
    return mergeHelper(arr, 0, arr.length-1);
}
private static int[] mergeHelper(int[] arr, int low, int high)
{
    if(high<=low)
    {
        return arr;
    }
    //亦为二分查找的mid计算方法，此法可避免(low+high)/2的溢出问题，如low+high>Integer.MAX_VALUE时
    int mid = low + (high - low)/2;
    mergeHelper(arr, 0, mid); //左半边排序
    mergeHelper(arr, mid+1, high); //右半边排序
    merge(arr, low, mid, high); //归并代码见原地归并方法
    return arr;
}

5.3 排序过程

由于递归调用无法直接明白地输出排序过程，可视化可以参考Data Structure Visualizations中比较排序之归并。

5.4 算法特点

归并排序能够保证将任意长度为$N$的数组排序所需时间与$NlogN$成正比，主要缺点是需要额外空间与$N$成正比。

6. 快速排序

6.1 算法描述

与归并一样，快排也是分治法的一种应用。其排序的分治过程分三个步骤：

• 分解：在数组中选择一个元素作为基准（pivot），将数组分为两个子数组，一个比基准小，另一个比基准大；
• 解决：通过递归调用快速排序，对两个子数组排序；
• 合并：由于两个数组是就地排序的，所以合并不需要操作，整个数组已经排序。

6.2 代码实现

//快速排序，参考算法导论p85,86
public static int[] QuickSort(int[] arr){
    System.out.println("快速排序");
    return QSort(arr, 0, arr.length-1);
}
//快速排序递归调用
private static int[] QSort(int[] arr, int left, int right)
{
    if(left>=right) return arr;
    int v = partition(arr, left, right); //pivot = arr[j]
    QSort(arr, left, v-1);
    QSort(arr, v+1, right);
    return arr;
}
//数组划分，partition过程
private static int partition(int[] arr, int left, int right)
{
    int i = left-1, j;
    int pivot = arr[right];
    for(j=left;j<=right-1;j++)
    {
        if(arr[j]<=pivot)
        {
            i++;
            swap(arr, i, j);
        }
    }
    swap(arr, i+1, right);
    System.out.printf("pivot为%d，分割结果为：%s\n", pivot, Arrays.toString(arr));
    return i+1;
}

6.3 排序过程

pivot为25，分割结果为：[4, 7, 17, 0, 11, 25, 34, 116, 129, 31, 27]
pivot为11，分割结果为：[4, 7, 0, 11, 17, 25, 34, 116, 129, 31, 27]
pivot为0，分割结果为：[0, 7, 4, 11, 17, 25, 34, 116, 129, 31, 27]
pivot为4，分割结果为：[0, 4, 7, 11, 17, 25, 34, 116, 129, 31, 27]
pivot为27，分割结果为：[0, 4, 7, 11, 17, 25, 27, 116, 129, 31, 34]
pivot为34，分割结果为：[0, 4, 7, 11, 17, 25, 27, 31, 34, 116, 129]
pivot为129，分割结果为：[0, 4, 7, 11, 17, 25, 27, 31, 34, 116, 129]

6.4 算法特点

以上数组划分的基准选择的是数组或子数组的最后一个元素，这种方法虽然简单明确，但是并不是一种好的划分方法。因为这种划分方式在输入数组是预排序的或反序的时候，将使快速排序的时间复杂度退化到$O(N^2)$。下面介绍两种较好的pivot选择方法：

• 随机选取：
  随机选取pivot是比较安全方法，快排的平均复杂度计算一般用随机选取的划分方法。
• 三数中值分割（Median-of-Three Partitioning）：
  这方法一般选择数组左端、右端及中心位置三个元素的中值作为pivot。如示例数组{4, 27, 7, 34, 29, 17, 0, 6, 10, 31, 25}中，左端元素为4，右端元素为25，中心元素为17，三数的中值为17，于是pivot选择17。 使用三数中值法消除了预排序输入的情况，减少了快排的运行时间。如下是一种三数中值分割的实现。

//三数中值分割
//需要修改一种简单排序算法的参数，用于在left+3>right的时候使用
public static int Midian3(int[] arr, int left, int right)
{
    int mid = left + (right-left) / 2;
    if(arr[left]>arr[mid]) swap(arr, left, mid);
    if(arr[left]>arr[right]) swap(arr, left, right);
    if(arr[mid]>arr[right]) swap(arr, mid, right);
    swap(arr, mid, right-1);
    return arr[right-1];
}

7. 堆排序

7.1 算法描述

堆排序是是一种基于堆这种数据结构的排序方法。堆可以被视为一棵完全二叉树，除最后一层外，堆的每一层都是被填满的。堆具有子节点小于或大于父节点的特点，即堆的最小或最大节点为根节点。堆分为小顶堆和大顶堆。在堆排序中，升序使用大顶堆，降序使用小顶堆。
堆排序算法的过程如下：

• **建堆：**将数组构建为大顶堆；
• **交换元素：**最大元素在堆顶，即arr[0]，将arr[0]与arr[n-1]交换，得到新的数组{arr[0]...arr[n-2]<=arr[n-1]；
• **保持堆性质：**交换元素后，堆的状态可能不符合堆的性质，需要调用maxHeapify调整为新的堆
• **重复此过程：**使堆的大小从n-1降到2

7.2 代码实现

//堆排序，算法导论p74
//升序用大顶堆，降序用小顶堆
//TODO:画出堆的状态
public static int[] HeapSort(int[] arr)
{
    System.out.println("堆排序");
    buildMaxHeap(arr);
    int len = arr.length;
    for(int i=len-1;i>0;i--)
    {
        System.out.printf("%s\n", Arrays.toString(arr));
        swap(arr, 0, i);
        len--;
        maxHeapify(arr, 0, len);
    }
    return arr;
}
//建堆
private static void buildMaxHeap(int[] arr)
{
    int len = arr.length;
    for(int i=arr.length/2;i>=0;i--)
    {
        maxHeapify(arr, i, len);
    }
}
//保持堆的性质
private static void maxHeapify(int[] arr, int i, int len)
{
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int largest = i;
    if(left<len && arr[left]>arr[largest])
    {
        largest = left;
    }
    if(right<len && arr[right]>arr[largest])
    {
        largest = right;
    }
    if(largest!=i)
    {
        swap(arr, i, largest);
        maxHeapify(arr, largest, len);
    }
}

7.3 排序过程

当前堆的状态为：
129 
116 18 34 32 
7 0 4 
11 23 25 
当前数组状态为[129, 116, 18, 34, 32, 7, 0, 4, 11, 23, 25]

当前堆的状态为：
116 
34 18 25 32 
7 0 4 
11 23 
当前数组状态为[116, 34, 18, 25, 32, 7, 0, 4, 11, 23, 129]

当前堆的状态为：
34 
32 18 25 23 
7 0 4 
11 
当前数组状态为[34, 32, 18, 25, 23, 7, 0, 4, 11, 116, 129]

当前堆的状态为：
32 
25 18 11 23 
7 0 4 
当前数组状态为[32, 25, 18, 11, 23, 7, 0, 4, 34, 116, 129]

当前堆的状态为：
25 
23 18 11 4 
7 0 
当前数组状态为[25, 23, 18, 11, 4, 7, 0, 32, 34, 116, 129]

当前堆的状态为：
23 
11 18 0 4 
7 
当前数组状态为[23, 11, 18, 0, 4, 7, 25, 32, 34, 116, 129]

当前堆的状态为：
18 
11 7 0 4 
当前数组状态为[18, 11, 7, 0, 4, 23, 25, 32, 34, 116, 129]

当前堆的状态为：
11 
4 7 0 
当前数组状态为[11, 4, 7, 0, 18, 23, 25, 32, 34, 116, 129]

当前堆的状态为：
7 
4 0 
当前数组状态为[7, 4, 0, 11, 18, 23, 25, 32, 34, 116, 129]

当前堆的状态为：
4 
0 
当前数组状态为[4, 0, 7, 11, 18, 23, 25, 32, 34, 116, 129]

当前堆的状态为：
0

7.4 算法特点

堆排序是一种原地排序算法，所以其空间复杂度为$O(1)$。

非比较排序

8. 计数排序

8.1 算法描述

计数排序需要满元素中的每一个都是介于0到k之间的整数。其基本思想为对每一个元素确定小于该元素的元素个数，这样就可以直接把该元素放到最终输出数组中的位置上。如，有5个元素小于元素i，则i的最终位置为5。

8.2 代码实现

//计数排序
public static int[] CountingSort(int[] arr)
{
    System.out.println("计数排序");
    int maxVal = getMaxValue(arr);
    int[] bucket = new int[maxVal+1];
    for(int iter : arr)
    {
        bucket[iter]++;
    }
    System.out.printf("中间数组为%s\n", Arrays.toString(bucket));

    int j = 0;
    for(int i=0;i<=maxVal;i++)
    {
        while(bucket[i]>0)
        {
            arr[j] = i;
            bucket[i]--;
            j++;
        }
    }
    return arr;
}

8.3 排序过程

中间数组为[1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]

9. 桶排序

9.1 算法描述

当数组符合均匀分布时，应用桶排序可使排序过程以线性期望时间运行。桶排序的基本思想是：

• 建立n个桶，n可为数组大小，桶的跨度为$dis=(maxVal-minVal)/(n-1)$，其中最后一个桶为最大值本身；
• 遍历数组，把元素放入各个桶中；
• 对桶内元素排序
• 遍历各桶，输出元素

9.2 代码实现

//桶排序，参考程序员小灰
public static int[] BucketSort(int[] arrInt)
{
    System.out.println("桶排序");
    double[] arr = new double[arrInt.length];
    for(int i=0;i<arrInt.length;i++)
        arr[i] = arrInt[i];
    //1.计算max,min得到差
    double maxVal = arr[0], minVal = arr[0];
    for(double iter : arr)
    {
        if(iter>maxVal) maxVal = iter;
        if(iter<minVal) minVal = iter;
    }
    double dis = maxVal - minVal;

    //2.建桶
    int bucketNum = arr.length;
    ArrayList<LinkedList<Double>> bucketList =
            new ArrayList<LinkedList<Double>>(bucketNum);
    for(int i=0;i<bucketNum;i++)
    {
        bucketList.add(new LinkedList<Double>());
    }

    //3.遍历数组，放入桶中
    for(double iter : arr)
    {
        int pos = (int)((iter-minVal) * (bucketNum-1) / dis);
        bucketList.get(pos).add(iter);
        System.out.print("各个桶内元素为");
        System.out.println(bucketList);
    }
    //4.对桶内进行排序
    for(LinkedList<Double> iter : bucketList)
    {
        Collections.sort(iter);
    }
    //5.依次输出
    int[] arrReturn = new int[arr.length];
    int idx = 0;
    for(LinkedList<Double> iter : bucketList)
    {
        for(double ele : iter)
        {
            arrReturn[idx] = (int)ele;
            idx++;
        }
    }
    return arrReturn;
}

9.3 排序过程

各个桶内元素为[[4.0], [], [], [], [], [], [], [], [], [], []]
各个桶内元素为[[4.0], [23.0], [], [], [], [], [], [], [], [], []]
各个桶内元素为[[4.0, 7.0], [23.0], [], [], [], [], [], [], [], [], []]
各个桶内元素为[[4.0, 7.0], [23.0], [34.0], [], [], [], [], [], [], [], []]
各个桶内元素为[[4.0, 7.0], [23.0], [34.0], [], [], [], [], [], [], [], [129.0]]
各个桶内元素为[[4.0, 7.0], [23.0, 18.0], [34.0], [], [], [], [], [], [], [], [129.0]]
各个桶内元素为[[4.0, 7.0, 0.0], [23.0, 18.0], [34.0], [], [], [], [], [], [], [], [129.0]]
各个桶内元素为[[4.0, 7.0, 0.0], [23.0, 18.0], [34.0], [], [], [], [], [], [116.0], [], [129.0]]
各个桶内元素为[[4.0, 7.0, 0.0, 11.0], [23.0, 18.0], [34.0], [], [], [], [], [], [116.0], [], [129.0]]
各个桶内元素为[[4.0, 7.0, 0.0, 11.0], [23.0, 18.0], [34.0, 32.0], [], [], [], [], [], [116.0], [], [129.0]]
各个桶内元素为[[4.0, 7.0, 0.0, 11.0], [23.0, 18.0, 25.0], [34.0, 32.0], [], [], [], [], [], [116.0], [], [129.0]]

10.基数排序

10.1 算法描述

基数排序是一种用在老式穿卡机上的算法。这种算法先按照最低有效位数字进行排序，再对高一位的有效位数字进行排序，直到最高位。

• 取得数组中的最大值，算出其数位；
• 从对低位开始，根据每一数位进行排序；

10.2 代码实现

//基数排序
public static int[] RadixSort(int[] arr)
{
    System.out.println("基数排序");
    int radixLen = getRadixLen(getMaxValue(arr));
    int radix = 1;
    for(int i=1;i<=radixLen;i++)
    {
        countingSort(arr, radix);
        System.out.printf("当前数位为%d\n", radix);
        System.out.printf("排序结果为%s\n", Arrays.toString(arr));
        radix *= 10;
    }
    return arr;
}
//在各个数位之间用counting sort
//radix为排序的基数
private static void countingSort(int[] arr, int radix)
{
    int[] bucket = new int[10];
    int[] temp = new int[arr.length];
    for(int iter : arr)
    {
        bucket[(iter/radix)%10]++;
    }
    for(int i=1;i<10;i++)
    {
        bucket[i] += bucket[i-1];
    }
    for(int i=arr.length-1;i>=0;i--)
    {
        temp[bucket[(arr[i]/radix)%10]-1] = arr[i];
        bucket[(arr[i]/radix)%10]--;
    }
    //arraycopy的方向为 src==>dst，参数顺序为 src, 复制开始idx, dst, 复制开始idx, 复制长度
    System.arraycopy(temp, 0, arr, 0, arr.length);
}
//获得max的位数
private static int getRadixLen(int maxVal)
{
    if(maxVal==0) return 1;
    int radixLen = 0;
    while(maxVal!=0)
    {
        maxVal /= 10;
        radixLen++;
    }
    return radixLen;
}

10.3 排序过程

当前数位为1
排序结果为[0, 11, 32, 23, 4, 34, 25, 116, 7, 18, 129]
当前数位为10
排序结果为[0, 4, 7, 11, 116, 18, 23, 25, 129, 32, 34]
当前数位为100
排序结果为[0, 4, 7, 11, 18, 23, 25, 32, 34, 116, 129]

• 一些公用函数

//helper
private static void swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

private static int getMaxValue(int[] arr)
{
    int maxVal = 0;
    for(int iter : arr)
    {
        if(iter>maxVal) maxVal = iter;
    }
    return maxVal;
}
/*被static修饰的成员变量和成员方法独立于该类的任何对象。也就是说，它不依赖类特定的实例，被类的所有实例共享。
只要这个类被加载，Java虚拟机就能根据类名在运行时数据区的方法区内定找到他们。
因此，static对象可以在它的任何对象创建之前访问，无需引用任何对象  
用public修饰的static成员变量和成员方法本质是全局变量和全局方法，当声明它类的对象市，
不生成static变量的副本，而是类的所有实例共享同一个static变量  
static变量前可以有private修饰，表示这个变量可以在类的静态代码块中，或者类的其他静态成员方法中使用(当然也可以在非静态成员方法中使用)，
但是不能在其他类中通过类名来直接引用，这一点很重要。实际上你需要搞明白，private是访问权限限定，static表示不要实例化就可以使用。
static前面加上其它访问权限关键字的效果也以此类推*/

总结

排序算法是算法学习中最基本的问题，而且也是程序员面试中的高频问题。我自己目前在秋招过程中已经被到问到过3次快排了。这篇blog也算是总结一下自己之前的面试。

写的时候不知道，写完才发现可以用泛型。不过主要是为了学习算法，影响不大。之后的二叉搜索树和avl树都用了泛型。全部代码已上传到github上我的项目Dr-Cube/DataStructuresAlgorithm。