七个排序

首先是几个简单排序：选择、冒泡、插入、希尔，重点关注希尔排序，这个复杂度有时间再看吧。。。

四个简单排序

    /**
     * 选择排序O(n^2)
     * 
     * @param 待排序数组
     */
    public static void selectionSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }

    /**
     * 冒泡排序O(n^2)
     * 
     * @param 待排序数组
     */
    public static void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j + 1 < nums.length - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j + 1, j);
                }
            }
        }
    }

    /**
     * 插入排序（交换）
     * 
     * @param 待排序数组
     */
    public static void insertionSortI(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j > 0 && nums[j - 1] > nums[j]; j--) {
                swap(nums, j - 1, j);
            }
        }
    }

    /**
     * 插入排序（移动)
     * 
     * @param nums
     */
    public static void insertionSortII(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int a = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > a) {
                nums[j + 1] = nums[j];
                j--;
            }

            nums[j + 1] = a;// 空位是J+1处
        }
    }

    /**
     * 希尔排序（递增序列1/2(3^k - 1)
     * 
     * @param 待排序数组
     */
    public static void shellSort(int[] nums) {
        int N = nums.length;
        int h = 1;
        while (h < N / 3) {
            h = 3 * h + 1;
        }

        while (h >= 1) {
            for (int i = h; i < N; i++) {
                for (int j = i; j >= h && nums[j - h] > nums[j]; j -= h) {
                    swap(nums, j - h, j);
                }
            }
            h = h / 3;
        }
    }

快速排序

提供三种切分方法。

    public static class QuickSort {
        public static void qSort(int[] nums, int l, int r) {
            if (l >= r) {
                return;
            }
            // int m = partitionI(nums,l,r);
            int m = partitionII(nums, l, r);
            qSort(nums, l, m - 1);
            qSort(nums, m + 1, r);
        }

        public static int partitionI(int[] nums, int l, int r) {
            Random random = new Random();
            int m = random.nextInt(r - l + 1) + l;
            swap(nums, l, m);

            int pivot = nums[l];
            int j = l;
            for (int i = l + 1; i <= r; i++) {
                if (nums[i] < pivot) {
                    swap(nums, i, j + 1);
                    j++;
                }
            }

            swap(nums, l, j);
            return j;
        }

        public static int partitionII(int[] nums, int l, int r) {
            Random random = new Random();
            int m = random.nextInt(r - l + 1) + l;
            swap(nums, l, m);

            int pivot = nums[l];

            int i = l + 1;
            int j = r;

            while (true) {
                while (i <= r && nums[i] < pivot)
                    i++;
                while (j >= l + 1 && nums[j] > pivot)
                    j--;

                if (i >= j) {
                    break;
                }

                swap(nums, i, j);
                i++;
                j--;
            }

            swap(nums, l, j);
            return j;

        }

        public static void qSortThreeWays(int[] nums, int l, int r) {
            if (l >= r) {
                return;
            }

            Random random = new Random();
            int m = random.nextInt(r - l + 1) + l;
            swap(nums, l, m);

            int pivot = nums[l];

            int lt = l;// [l+1....lt]
            int gt = r + 1;// [gt....r]
            int j = l + 1;
            while (j < gt) {
                if (nums[j] < pivot) {
                    swap(nums, lt + 1, j);
                    lt++;
                    j++;
                } else if (nums[j] == pivot) {
                    j++;
                } else {
                    swap(nums, gt - 1, j);
                    gt--;
                }
            }

            swap(nums, l, lt);
            lt--;
            qSortThreeWays(nums, l, lt);
            qSortThreeWays(nums, gt, r);
        }
    }

归并排序

以前总是一次一次在merge函数里面去创建aux，算法第四版上直接在构造函数里面一次性分配空间，后面的下标转换就没有那么麻烦了，代码如下：

    public static class MergeSort {
        private static int[] aux;

        private static void merge(int[] nums, int l, int mid, int r) {
            int i = l;
            int j = mid + 1;

            for (int k = l; k <= r; k++) {
                aux[k] = nums[k];
            }

            for (int k = l; k <= r; k++) {
                if (i > mid) {
                    nums[k] = aux[j++];
                } else if (j > r) {
                    nums[k] = aux[i++];
                } else if (aux[j] < aux[i]) {
                    nums[k] = aux[j++];
                } else {
                    nums[k] = aux[i++];
                }
            }
        }

        public static void mSort(int[] nums) {
            aux = new int[nums.length];

            mSort(nums, 0, nums.length - 1);
        }

        private static void mSort(int[] nums, int l, int r) {
            if (r <= l) {
                return;
            }

            int mid = l + (r - l) / 2;
            mSort(nums, l, mid);
            mSort(nums, mid + 1, r);
            merge(nums, l, mid, r);
        }
    }

下面的是由底向上非递归
几个说明：

1. sz就是分割的数组长度
2. i + sz -1 就是分割的子数组的最后一个元素下标
3. sz从1开始，每次扩大一倍
4. 第二层循环i + sz < nums.length是确保第二段分割的数组存在
5. [i,.....,i + sz -1] [i + sz,......,i + 2sz -1]， [i +2sz......

        private static void mSortBottomToUp(int[] nums) {
            for(int sz = 1; sz <= nums.length; sz = sz+sz) {
                for(int i = 0; i+sz < nums.length; i += sz + sz) {
                    merge(nums, i, i+sz-1, Math.min(i+sz+sz-1, nums.length - 1));
                }
            }
        }

堆排序

堆排序就是对传进来的数组先Heapify，这个复杂度是O（n），然后再进行堆排序。即先建堆，再排序。整个过程只涉及了shiftDown操作，这个函数要能熟练书写。

    public static void heapSort(int[] nums) {
        for (int i = parent(nums.length - 1); i >= 0; i--) {
            shiftDown(nums, i, nums.length - 1);
        }
        
        int i = nums.length - 1;
        while(i > 0) {
            swap(nums, 0, i--);
            shiftDown(nums, 0, i);
            
        }
        /*for(int i = nums.length - 1; i >0; i--) {
            swap(nums, 0, i);
            shiftDown(nums, 0, i-1);
        }*/
    }

    public static void shiftUp(int[] nums, int index) {
        while(index >= 0 && nums[index] > nums[parent(index)]) {
            swap(nums, index, parent(index));
            index = parent(index);
        }
    }

    public static void shiftDown(int[] nums, int start, int end) {
        while (leftChild(start) <= end) {
            int j = leftChild(start);

            if (j+1 <= end && nums[j] < nums[rightChild(start)]) {
                j = rightChild(start);
            }
            if(nums[start] > nums[j]) {
                break;
            } else {
                swap(nums, start, j);
                start = j;
            }
        }
    }

    public static int parent(int index) {
        return (index - 1) / 2;
    }

    public static int leftChild(int index) {
        return index * 2 + 1;
    }

    public static int rightChild(int index) {
        return index * 2 + 2;
    }