排序算法代码实现

归并排序

    /*
     * 归并排序(从上往下)
     * 
     * 参数说明： a -- 待排序的数组 start -- 数组的起始地址 endi -- 数组的结束地址
     */
    public void Sort(int[] a, int start, int end) {
        if (a == null || start >= end)
            return;

        int mid = (end + start) / 2;
        Sort(a, start, mid); // 递归排序a[start...mid]
        Sort(a, mid + 1, end); // 递归排序a[mid+1...end]

        // a[start...mid] 和 a[mid...end]是两个有序空间，
        // 将它们排序成一个有序空间a[start...end]
        merge(a, start, mid, end);
    }
    /*
     * 将一个数组中的两个相邻有序区间合并成一个
     * 
     * 参数说明： a -- 包含两个有序区间的数组 start -- 第1个有序区间的起始地址。 mid --
     * 第1个有序区间的结束地址。也是第2个有序区间的起始地址。 end -- 第2个有序区间的结束地址。
     */
    public void merge(int[] a, int start, int mid, int end) {
        int[] tmp = new int[end - start + 1]; // tmp是汇总2个有序区的临时区域
        int i = start; // 第1个有序区的索引
        int j = mid + 1; // 第2个有序区的索引
        int k = 0; // 临时区域的索引
        // 类似于合并两个有序链表，当两个有序链表都有数据时，比较这两个链表的数据，并将小的数据放到新开辟出的空间中
        while (i <= mid && j <= end) {
            if (a[i] <= a[j])
                tmp[k++] = a[i++];
            else
                tmp[k++] = a[j++];
        }
        // 防止两个数组一个排完了，另一个还没有排完，将剩下的那个数组的值接在后面。
        while (i <= mid)
            tmp[k++] = a[i++];

        while (j <= end)
            tmp[k++] = a[j++];

        // 将排序后的元素，全部都整合到数组a中。
        for (i = 0; i < k; i++)
            a[start + i] = tmp[i];

        tmp = null;
    }

快速排序

    /*
     * 快速排序
     * 
     * 参数说明： a -- 待排序的数组 l -- 数组的左边界(例如，从起始位置开始排序，则l=0) r --
     * 数组的右边界(例如，排序截至到数组末尾，则r=a.length-1)
     */
    public static void quickSort(int[] a, int l, int r) {
        if (l < r) {
            int i, j, x;

            i = l;
            j = r;
            x = a[i];
            while (i < j) {
                while (i < j && a[j] > x) {
                    j--; // 从右向左找第一个小于x的数
                }
                if (i < j) {
                    a[i++] = a[j];
                }
                while (i < j && a[i] < x) {
                    i++; // 从左向右找第一个大于x的数
                }
                if (i < j) {
                    a[j--] = a[i];
                }
            }
            a[j] = x;
            quickSort(a, l, i - 1); /* 递归调用 */
            quickSort(a, i + 1, r); /* 递归调用 */
        }
    }