912、排序数组
给你一个整数数组 nums，将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 50000-50000 <= nums[i] <= 50000
题解
常见的排序算法：
- 快速排序
- 堆排序
- 归并排序
- 希尔排序
- 冒泡排序、鸡尾酒排序
- 插入排序、快速插入排序
- 选择排序
1、快速排序
- 随机选择一个数字，利用原地算法，按照这个数字将数组一分为二。
class Solution {
public int[] sortArray(int[] nums) {
quickSort(nums,0,nums.length-1);
return nums;
}
private void quickSort(int[] nums,int left,int right){
if (left > right) return;
int p = partition(nums,left,right);
// System.out.println("p: "+p);
quickSort(nums,left,p-1);
quickSort(nums,p+1,right);
}
private int partition(int[] nums,int left,int right){
// 移动大于p的数字
// int p = nums[left];
// int index = right;
// for (int i = right;i >= left;i--){
// if (nums[i] > p) {
// int t = nums[i];
// nums[i] = nums[index];
// nums[index] = t;
// index--;
// }
// }
// 移动小于p的数字
int p = nums[right];
int index = left;
for (int i = left;i <= right;i++){
if (nums[i] < p) {
int t = nums[i];
nums[i] = nums[index];
nums[index] = t;
index++;
}
}
int t = nums[index];
nums[index] = nums[right];
nums[right] = t;
return index;
}
}
2、堆排序
完全二叉树，根>左、右——>大顶堆；根<左、右——>小顶堆
class Solution {
public int[] sortArray(int[] nums) {
heapSort(nums);
}
// 对调整
private void maxHeapify(int[] nums,int i,int len) {
for (;(i << 1) + 1 <= len) {
// 找出根、左、右那个最大
int lson = (i << 1) + 1;
int rson = (i << 1) + 2;
int large = 0;
if (lson <= len && nums[lson] > nums[i]) {
large = lson;
} else {
large = i;
}
if (rson <= len && nums[rson] > nums[large]) {
large = rson;
}
// 用i索引最大的元素
if (large != i) {
swap(nums,i,large);
i = large;
} else {
break;
}
}
}
private void swap(int[] nums,int i,int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = nums[i];
}
private void buildMaxHeap(int[] nums.int len) {
for (int i = len / 2;i >= 0;i--) {
maxHeapify(nums,i,len);
}
}
private void heapSort(int[] nums) {
int len = nums.length - 1;
buildMaxHeap(nums,len);
for (int i = len;i >= 1;i--){
// 将堆顶元素移动到最后一位
swap(nums,i,0);
// 堆的长度减1
len -= 1;
// 调整堆，确保最大的值在堆顶
maxHeapify(nums,0,len);
}
}
}
3、归并排序
二分递归+归并。
class Solution {
int[] tmp;
private void mergeSort(int[] nums,int l,int r) {
if (l >= r) {return;}
int mid = (l + r) >> 1;
mergeSort(nums,l,mid);
mergeSort(nums,mid,r);
int i = l,j = mid + 1;
// 将数据从小到大放到新的空间
int cnt = 0;
while (i <= mid && j <= r) {
if (nums[i] < nums[j]) {
tmp[cnt++] = nums[i++];
} else {
tmp[cnt++] = nums[j++];
}
}
while (i <= mid) {tmp[cnt++] = nums[i++];}
while (j <= r) {tmp[cnt++] = nums[j++];}
// 将数据从小到大放回原位
for (i = 0;i < r - l + 1; i++) {
nums[i + 1] = tmp[i];
}
}
public int[] sortArray(int[] nums) {
tmp = new int[nums.length];
mergeSort(nums,0,nums.lenght - 1);
return nums;
}
}
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
