序言：

算法系列文章会以《算法导论》 为参考，使用Java语言实现算法相关的知识，算法全篇文章主要涉及的是代码，而不是分析内容，推导过程可参考算法导论书籍或者网上寻找。

快速排序

public class QuickSortHelper {
     
    public static void quickSort(int[] a, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = partition(a, p, r);
        quickSort(a, p, q - 1);
        quickSort(a, q + 1, r);
    }
    
    public static int partition(int[] a, int p, int r) {
        int x = a[r];
        int i = p - 1;
        for (int j = p; j < r; j ++) {
            if (a[j] <= x) {
                i += 1;
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
            
        }
        int temp = a[i + 1];
        a[i + 1] = a[r];
        a[r] = temp;
        return i + 1; 
    }
    
    public static int randomPartition(int[] a, int p, int r) {
        int i = p + (int)(Math.random() * (r - p));
        int temp = a[i];
        a[i] = a[r];
        a[r] = temp;
        return partition(a, p, r);
    }
    
    public static void randomQuickSort(int[] a, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = randomPartition(a, p, r);
        randomQuickSort(a, p, q - 1);
        randomQuickSort(a, q + 1, r);
    }
    
    
    public static void main(String args[]) {
        int[] a = {3, 4, 2, 1, 6, 29, 56, 23, 43};
        int p = 0;
        int r = a.length - 1;
        System.out.println("quickSort before:" + Arrays.toString(a));
        randomQuickSort(a, p, r);
        System.out.println("quickSort after:" + Arrays.toString(a));
    }

}

计数排序

public class CountSortHelper {

    public static void countingSort(int[] a, int[] b, int k) {
        int[] c = new int[k];
        for(int i = 0; i< k; i ++) {
            c[i] = 0;
        }
        for(int j = 0; j < a.length; j ++) {
            c[a[j]] = c[a[j]] + 1;
        }
        for(int m = 1; m < k; m++) {
            c[m] = c[m] + c[m - 1];
        }
        
        for(int n = 0; n < a.length; n ++) {
            c[a[n]] = c[a[n]] - 1;
            b[c[a[n]]] = a[n];                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                        
        }
    }
      
    
    public static int[] getAToArray(int n, int k) {
        int[] a = new int[n];
        for(int i = 0; i< n; i ++) {
            a[i] = (int)(Math.random() * k);
        }
        return a;
    }
    
    public static void main(String[] args) {
        int n = 44;
        int k = 721;
        int[] a = getAToArray(n, k);
        int[] b = new int[n];
        System.out.println("countingSort before b:" +Arrays.toString(b));
        countingSort(a, b, k);
        System.out.println("countingSort after b:" +Arrays.toString(b));
    }
}
 

基数排序

/**
 * 基数排序
 */
public class BaseNumSortHelper {
    
    public  static void baseNumSort(int[] a, int k) {
        int[][] b = new int[10][a.length];
        for(int j = 0; j < k; j ++) {
            int[] count = new int[a.length];
            for(int i = 0;i < a.length; i++) {
                int num = a[i];
                int index = (num / ((int) Math.pow(10, j))) % 10;
                int c = count[index];
                b[index][c] = num;
                count[index] = count[index] + 1;
            }
            int index = 0;
            for(int m = 0; m < b.length; m++) {
                for(int n= 0; n < b[m].length; n++) {
                    if(b[m][n] != 0) {
                        a[index] = b[m][n];
                        index ++;
                        b[m][n] = 0;    
                    }
                }
            }
        }
    }
    
    public static int[] getCollections(int n, int k) {
        int[] a = new int[n];
        for (int i = 0; i< n; i++) {
            int num = (int)(Math.random() * Math.pow(10, k));
            a[i] = num;
        }
        return a;
    }
    
    
    public static void main(String[] args) {
        int n = 20;
        int k = 3;
        int[] a = getCollections(n, k);
        System.out.println("Sort before:" + Arrays.toString(a));
        baseNumSort(a, k);
        System.out.println("Sort after:" + Arrays.toString(a));
    }
}