排序算法大汇总

快速排序选取一个值value作为参照（一般是数组的第一个值），把比value大的放到数组的后半部分，比value小的放到数组的前半部分。然后递归的在前半部分和后半部分继续重复上述的 *** 作。
时间复杂度O(nlogn),空间复杂度O(logn)
快速排序是不稳定的

   public static int[] fastSort(int[] nums, int bg, int end) {
        if (bg >= end)
            return nums;
        int last = end;
        int first = bg;
        int value = nums[bg];
        while (first < last) {
            if (nums[last] > value) {
                last--;
            } else {// 调头
                nums[first] = nums[last];
                while (first < last) {
                    if (nums[first] < value) {
                        first++;
                    } else {
                        nums[last--] = nums[first];
                        break;
                    }
                }

            }
        }
        nums[first] = value;
        fastSort(nums, bg, last);
        fastSort(nums, last + 1, end);

        return nums;
    }

归并排序首先将数组递归的向下对半划分，划分到不能划分（每个子序列只有一个元素）后再将子序列向上合并成有序序列，直到合并为最后一个有需序列。
时间复杂度O(nlogn)，空间复杂度O(n)。(需要一个辅助数组来合并两个序列)。
归并排序是稳定的

 public static int[] mergeSort(int[] nums, int bg, int end) {
        int mid = (bg + end) / 2;
        if (bg >= end)
            return nums;

        mergeSort(nums, bg, mid);
        mergeSort(nums, mid + 1, end);

        return merge(nums, bg, end);

    }

    public static int[] merge(int[] nums, int bg, int end) {
        int temp[] = new int[end - bg + 1];
        int mid = (bg + end) / 2;
        int index = 0;
        int i = bg, j = mid + 1;
        while (i <= mid && j <= end) {
            if (nums[i] > nums[j]) {
                temp[index++] = nums[j++];
            } else {
                temp[index++] = nums[i++];
            }
        }
        while (i <= mid) {
            temp[index++] = nums[i++];
        }
        while (j <= end) {
            temp[index++] = nums[j++];
        }
        for (int a = 0; a < temp.length; a++) {
            nums[bg++] = temp[a];
        }
        return nums;
    }

堆是一个完全二叉树，且符合以下条件（小根堆就反一下）

1. 节点大于等于根节点
2. 左右子树都是符合上述要求

我们可以很完美的使用一维数组来表示一个堆。

由于完全二叉树的特殊结构，我们可以获得几条很有用的规律，设一颗完全二叉树的节点数量为n。位置表示在一维坐标中的索引(i从0开始)

1. 第i个节点的左孩子位置为2i+1
2. 第i个节点的右孩子位置为2i+2
3. 第i个节点的父节点位置为 ⌊ i / 2 ⌋ \lfloor i/2 \rfloor ⌊i/2⌋

综上我们可以用一个一维数组来表示一个堆，并且在数组上模拟对堆的 *** 作
例如，交换第3个节点和他的右孩子的值，就只需要交换数组下标2和6的值即可。

下面以小根堆为例
在堆的最后添加一个元素，然后比较这个元素和他父节点的值大小，小于父节点就交换两个节点的值，然后继续与上一级的父节点比较。

找到最后一个非叶子节点， ⌊ s i z e / 2 ⌋ \lfloor size/2 \rfloor ⌊size/2⌋的位置。对这个节点进行调整，让他变成堆。然后找他上一个子树 ⌊ s i z e / 2 ⌋ \lfloor size/2 \rfloor ⌊size/2⌋-1，重复这个 *** 作直到根节点。

   /**
     * 调整堆
     * @param nums
     * @param size 堆最后一个元素坐标
     * @param last  当前调整位置
     * @return
     */
    public static int[] heapAdj(int[] nums, int size, int last) {

        int maxIndex = last;
        while (last <= (size + 1) / 2 - 1) {
            if (last * 2 + 1 > size) {// 是叶子节点
                return nums;
            } else if (last * 2 + 2 <= size) {// 有两个孩子
                if (nums[last * 2 + 1] >= nums[last * 2 + 2]) {
                    maxIndex = last * 2 + 1;
                } else if (nums[last * 2 + 1] < nums[last * 2 + 2]) {
                    maxIndex = last * 2 + 2;
                }
                if (nums[last] < nums[maxIndex]) {
                    swap(nums, last, maxIndex);
                    heapAdj(nums, size, maxIndex);
                } else
                    break;
            } else if (last * 2 + 1 <= size) {// 只有左孩子
                if (nums[last] < nums[last * 2 + 1]) {
                    maxIndex = last * 2 + 1;
                    swap(nums, last, maxIndex);
                    heapAdj(nums, size, maxIndex);
                } else
                    break;
            }
        }
        return nums;
    }

首先将原始数据修改成堆，然后交换第一个元素和最后一个元素。然后再把这个数据调整成堆，重复 *** 作即可。
时间复杂度O(nlogn),空间复杂度O(1)
堆排序不稳定

  public static int[] heapSort(int[] nums) {
        
        downAdj(nums);// 调整为初始堆

        for (int i = 0; i < nums.length; i++) {// 自顶向下调整为堆
            swap(nums, 0, nums.length - i - 1);
            heapAdj(nums, nums.length - i - 2, 0);
        }

        return nums;
    }

    /**
     * 创建大根堆
     * 
     * @param nums
     * @return
     */
    public static int[] downAdj(int[] nums) {
        int parent = nums.length / 2 - 1;
        for (int i = parent; i >= 0; i--) {
            heapAdj(nums, nums.length - 1, i);
        }
        return nums;
    }

源代码地址，给个star吧兄弟们!