【算法思想-排序】排序数组-力扣 912 题

💝💝💝欢迎来到我的博客，很高兴能够在这里和您见面！希望您在这里可以感受到一份轻松愉快的氛围，不仅可以获得有趣的内容和知识，也可以畅所欲言、分享您的想法和见解。

推荐:kuan 的首页,持续学习,不断总结,共同进步,活到老学到老
导航
檀越剑指大厂系列:全面总结 java 核心技术点,如集合,jvm,并发编程 redis,kafka,Spring,微服务,Netty 等
常用开发工具系列:罗列常用的开发工具,如 IDEA,Mac,Alfred,electerm,Git,typora,apifox 等
数据库系列:详细总结了常用数据库 mysql 技术点,以及工作中遇到的 mysql 问题等
懒人运维系列:总结好用的命令,解放双手不香吗?能用一个命令完成绝不用两个操作
数据结构与算法系列:总结数据结构和算法,不同类型针对性训练,提升编程思维,剑指大厂

非常期待和您一起在这个小小的网络世界里共同探索、学习和成长。💝💝💝 ✨✨ 欢迎订阅本专栏 ✨✨

博客目录

- - 1.题目描述
  - 2.示例
  - 3.提示
  - 4.题解

1.题目描述

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

2.示例

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

3.提示

提示：

1 <= nums.length <= 5 * 104
-5 * 104 <= nums[i] <= 5 * 104

4.题解

冒泡排序超时
选择排序超时
插入排序超时
堆排序通过
希尔排序通过
归并排序(递归-合并-插入) 通过
归并排序(递归-合并) 通过
归并排序(迭代-合并) 通过
单边快排超时
双边快排超时
双边快排+随机基准位通过
双边快排+随机基准位+等值处理通过

堆排序

public static void sort(int[] a) {buildHeap(a);//排序for (int i = a.length - 1; i >= 0; i--) {swap(a, 0, i);down(a, 0, i);}
}/*** 建堆** @param a*/
private static void buildHeap(int[] a) {for (int i = a.length / 2 - 1; i >= 0; i--) {down(a, i, a.length);}
}/*** 下潜方法** @param a      原数组* @param parent 父节点* @param size   长度*/
private static void down(int[] a, int parent, int size) {while (true) {int left = parent * 2 + 1;int right = left + 1;int max = parent;if (left < size && a[left] > a[max]) {max = left;}if (right < size && a[right] > a[max]) {max = right;}if (max == parent) {break;}swap(a, max, parent);parent = max;}
}/*** 交换位置** @param a* @param right* @param max*/
private static void swap(int[] a, int right, int max) {int t = a[max];a[max] = a[right];a[right] = t;
}

希尔排序:

public static void sort(int[] a) {for (int gap = a.length >> 1; gap > 0; gap = gap >> 1) {//插入排序for (int low = gap; low < a.length; low++) {int t = a[low];int i = low - gap;while (i >= 0 && t < a[i]) {a[i + gap] = a[i];i -= gap;}if (i != low - gap) {a[i + gap] = t;}}}
}

归并排序:

public class Sort_06_MergeInsertionSort_01 {/*** 归并排序思想:先分割** @param a1*/public static void sort(int[] a1) {int[] a2 = new int[a1.length];split(a1, 0, a1.length - 1, a2);}private static void split(int[] a1, int left, int right, int[] a2) {// 2. 治if (right - left <= 32) {// 插入排序insertion(a1, left, right);return;}// 1. 分int m = (left + right) >>> 1;split(a1, left, m, a2);split(a1, m + 1, right, a2);// 3. 合merge(a1, left, m, m + 1, right, a2);//把a2中的元素复制回a1System.arraycopy(a2, left, a1, left, right - left + 1);}public static void merge(int[] a1, int i, int iEnd, int j, int jEnd, int[] a2) {int k = i;while (i <= iEnd && j <= jEnd) {if (a1[i] < a1[j]) {a2[k] = a1[i];i++;} else {a2[k] = a1[j];j++;}k++;}if (i > iEnd) {System.arraycopy(a1, j, a2, k, jEnd - j + 1);}if (j > jEnd) {System.arraycopy(a1, i, a2, k, iEnd - i + 1);}}public static void insertion(int[] a, int left, int right) {for (int low = left + 1; low <= right; low++) {int t = a[low];int i = low - 1;// 自右向左找插入位置，如果比待插入元素大，则不断右移，空出插入位置while (i >= left && t < a[i]) {a[i + 1] = a[i];i--;}// 找到插入位置if (i != low - 1) {a[i + 1] = t;}}}public static void main(String[] args) {int[] a = {9, 3, 7, 2, 8, 5, 1, 4};System.out.println(Arrays.toString(a));sort(a);System.out.println(Arrays.toString(a));}
}

双边快排

public class Sort_07_02_QuickSortHoare_07 {/*** 双边快排** @param a*/public static void sort(int[] a) {quick(a, 0, a.length - 1);}/*** 快排** @param a* @param left* @param right*/private static void quick(int[] a, int left, int right) {if (left >= right) {return;}int mid = partition(a, left, right);quick(a, left, mid - 1);quick(a, mid + 1, right);}private static int partition(int[] a, int left, int right) {//添加left随机final int index = ThreadLocalRandom.current().nextInt(right - left + 1) + left;swap(a, left, index);int pv = a[left];int i = left + 1;int j = right;//j找小的while (i <= j) {while (i <= j && a[j] > pv) {j--;}while (i <= j && a[i] < pv) {i++;}if (i <= j) {swap(a, i, j);i++;j--;}}swap(a, left, j);return j;}/*** 交换位置** @param a* @param right* @param max*/private static void swap(int[] a, int right, int max) {int t = a[max];a[max] = a[right];a[right] = t;}public static void main(String[] args) {int[] a = {6, 5, 4, 3, 2, 1};System.out.println(Arrays.toString(a));sort(a);System.out.println(Arrays.toString(a));}
}