力扣 912. 排序数组（排序算法合集）

题目描述：

给你一个整数数组 nums，请你将该数组升序排列。

解析：

快速排序：

class Solution {
    public int[] sortArray(int[] nums) {
        qSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void qSort(int[] arr, int start, int end) {
        int left = start, right = end;
        if(left < right) {
            int temp = arr[left];
            while(left < right) {
                while(left < right && arr[right] >= temp) {
                    right--;
                }
                if(left < right) {
                    arr[left] = arr[right];
                }
                while(left < right && arr[left] < temp) {
                    left++;
                }
                if(left < right) {
                    arr[right] = arr[left];
                }
            }
            arr[left] = temp;
            qSort(arr, start, left);
            qSort(arr, left + 1, end);
        }
    }
}

JavaScript:

var sortArray = function(nums) {
    qSort(nums, 0, nums.length - 1);
    return nums;

    function qSort(arr, start, end) {
        let left = start, right = end;
        if(left < right) {
            let temp = arr[left];
            while(left < right) {
                while(left < right && arr[right] >= temp) {
                    right--;
                }
                if(left < right) {
                    arr[left] = arr[right];
                }
                while(left < right && arr[left] < temp) {
                    left++;
                }
                if(left < right) {
                    arr[right] = arr[left];
                }
            }
            arr[left] = temp;
            qSort(arr, start, left);
            qSort(arr, left + 1, end);
        }
    }
};

堆排序：

堆排序的思想借助于二叉堆中的最大堆得以实现。首先，将待排序数列抽象为二叉树，并构造出最大堆；然后，依次将最大元素（即根节点元素）与待排序数列的最后一个元素交换（即二叉树最深层最右边的叶子结点元素）

每次遍历，刷新最后一个元素的位置（自减1），直至其与首元素相交，即完成排序。
时间复杂度：O(NlogN)
稳定性：不稳定

大顶堆：堆可以看做一个完全二叉树，如果该完全二叉树满足双亲结点大于等于孩子结点，则这样的堆也称为大顶堆。

小顶堆：如果完全二叉树满足双亲结点小于等于孩子结点，则这样的堆也称为小顶堆。
对于一个数组生成的完全二叉树，如果完全二叉树中的一个节点对应数组中的下标索引为index,则这个节点的左右子节点对应数组中的下标索引为：

                             left = index * 2 + 1

                             right = index * 2 + 2      保证 left<arr.length;

（1）数组中的下标索引依次对应完全二叉树的节点，然后把完全二叉树变成大顶堆，这样数组中的第一个元素就是完全二叉树根节点的值。

（2）把数组中的第一个元素与第arr.length个元素交换位置，然后对前arr.length-1个元素重新生成大顶堆。以后依次把第一个元素与第arr.length - i 个元素交换位置。直到arr.length - i =1。

（3）此时的数组就是进行升序排序后的数组。如果进行降序排序，可以选择小顶堆的方式。

Java:

class Solution {
    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }
    public void heapSort(int[] nums) {
        int size = nums.length;
        for(int i = size / 2 - 1; i >= 0; i--) {
            adjust(nums, size, i);
        }
        for(int i = size - 1; i >= 1; i--) {
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            adjust(nums, i, 0);
        }
    }
    public void adjust(int[] nums, int len, int index) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int maxIndex = index;
        if(left < len && nums[left] > nums[maxIndex]) {
            maxIndex = left;
        }
        if(right < len && nums[right] > nums[maxIndex]) {
            maxIndex = right;
        }
        if(maxIndex != index) {
            int temp = nums[maxIndex];
            nums[maxIndex] = nums[index];
            nums[index] = temp;
            adjust(nums, len, maxIndex);
        }
    }
}

JavaScript:

var sortArray = function(nums) {
    heapSort(nums);
    return nums;

    function heapSort(nums) {
        let size = nums.length;
        for(let i = Math.floor(size / 2) - 1; i >= 0; i--) {
            adjust(nums, size, i);
        }
        for(let i = size - 1; i >= 1; i--) {
            let temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
            adjust(nums, i, 0);
        }
    }

    function adjust(nums, len, index) {
        let left = 2 * index + 1;
        let right = 2 * index + 2;
        let maxIndex = index;
        if(left < len && nums[left] > nums[maxIndex]) {
            maxIndex = left;
        }
        if(right < len && nums[right] > nums[maxIndex]) {
            maxIndex = right;
        }
        if(maxIndex !== index) {
            let temp = nums[maxIndex];
            nums[maxIndex] = nums[index];
            nums[index] = temp;
            adjust(nums, len, maxIndex);
        }
    }
};

冒泡排序：

Java:

class Solution {
    public int[] sortArray(int[] nums) {
        BubbleSort(nums);
        return nums;
    }
    public void BubbleSort(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            boolean flag = true;
            for(int j = 0; j < nums.length - i - 1; j++) {
                if(nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    flag = false;
                }
            }
            if(flag) {
                break;
            }
        }
    }
}

JavaScript:

var sortArray = function(nums) {
    BubbleSort(nums);
    return nums;

    function BubbleSort(nums) {
        for(let i = 0; i < nums.length; i++) {
            let flag = true;
            for(let j = 0; j < nums.length - i - 1; j++) {
                if(nums[j] > nums[j + 1]) {
                    let temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                    flag = false;
                }
            }
            if(flag) {
                break;
            }
        }
    }
};

归并排序：

Java:

class Solution {
    public int[] sortArray(int[] nums) {
        return mergeSort(nums, 0, nums.length - 1);
    }
    private int[] mergeSort(int[] nums, int left, int right) {
        if(left == right) {
            return new int[] {nums[left]};
        }
        int mid = left + (right - left) / 2;
        int[] leftRes = mergeSort(nums, left, mid);
        int[] rightRes = mergeSort(nums, mid + 1, right);
        return merge(leftRes, rightRes);
    }
    private int[] merge(int[] leftRes, int[] rightRes) {
        int[] res = new int[leftRes.length + rightRes.length];
        int p = 0, l = 0, r = 0;
        while(l < leftRes.length && r < rightRes.length) {
            if(leftRes[l] <= rightRes[r]) {
                res[p++] = leftRes[l++];
            } else {
                res[p++] = rightRes[r++];
            }
        }
        while(l < leftRes.length) {
            res[p++] = leftRes[l++];
        }
        while(r < rightRes.length) {
            res[p++] = rightRes[r++];
        }
        return res;
    }
}

JavaScript:

var sortArray = function(nums) {
    const merge = (right, left) => {
        let res = [];
        let i = 0, j = 0;
        while(i < left.length && j < right.length) {
            if (left[i] < right[j]) {
                res.push(left[i++])
            } else {
                res.push(right[j++])
            }
        }
        while(i < left.length) {
            res.push(left[i++])
        }
        while(j < right.length) {
            res.push(right[j++])
        }
        return res
    }
    var Mergesort = (arr) => {
        if(arr.length == 1) {
            return arr;
        }
        let mid = Math.floor(arr.length / 2);
        let left = arr.slice(0, mid);
        let right = arr.slice(mid);
        return merge(sortArray(left), sortArray(right));
    }
    return Mergesort(nums)
};