插值排序+快速排序

用快排算法（QuickSort）将待排序數組劃分成長度不大于10的若幹子數組之後，改用插值排序（InsertSort）完成剩下的排序工作，這是因為當比較大小（Compare）這個操作本身就很複雜的時候，插值排序在小規模數組上的表現比快排更好，假如排序的是字元串等複雜對象，效果會更明顯。

quickSort方法裡用到了兩個方法，partition方法用來确定快排算法基準數的位置，insertSort方法就是常見的插值排序算法，代碼如下：

/**快速排序*/
static void quickSort(int[] a, int low, int up) {
        if (low >= up)
            return;
        //距離不小于10，使用遞歸快排，否則改用插入排序
        if (up - low >= 10) {
            int j = partition(a, low, up);
            quickSort(a, low, j - 1);
            quickSort(a, j + 1, up);
        } else {
            insertSort(a, low, up);
        }
    }

/**插入排序*/
static void insertSort(int[] a, int low, int up) {
        for (int i = low; i <= up; i++) {
            int v = a[i];
            int j = i;
            while (j > low && a[j - 1] > v) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = v;
        }
    }

/**用來産生快排裡的基準數*/   
private static int partition(int[] a, int low, int up) {
        Random ra = new Random();
        int r = ra.nextInt(up - low + 1) + low;
        exch(a, r, low);
        int i = low;
        int j = up + 1;
        int v = a[low];
        while (true) {
            while (v < a[--j]) if (j == low) break;
            while (a[++i] < v) if (i == up) break;
            if (i >= j) break;
            exch(a, i, j);
        }
        exch(a, low, j);
        return j;
    }