力扣 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)
};