Java教程
排序算法
本文主要是介绍排序算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
1.排序分类
2.时间\空间复杂度
图片来自：https://www.cnblogs.com/onepixel/articles/7674659.html
原图的快排的空间复杂度错误
3. 具体实现
tips: 按升序排序
3.1 插入排序
1）直接插入排序
思路：
- 1 在有序队列 [0, j] 中插入 [i] 元素
- 2.1 若 [i] < [j] 则移动元素 [j] 到相邻的下一个位置 j + 1
- 2.2 若 [i] > [j] 则将 [i] 元素插入到位置 j + 1
- 如此反复
复杂度
- 时间复杂度：O(n2)
- 空间复杂度：O(1)
public class InsertSort {
private static void insertSort(int[] nums) {
for (int i=1; i<nums.length; i++) {
int j = i - 1;
int cur = nums[i];
while (j >= 0 && nums[j] > cur) {
nums[j+1] = nums[j];
j--;
}
nums[j + 1] = cur;
}
}
}
2）希尔排序
思路：是一种特殊的插入排序，其根据不同的步长更新成最终的有序序列
public class S4_ShellSort {
private static void shellSort(int[] nums) {
for (int i=(int)Math.floor(nums.length); i>0; i=(int)Math.floor(i/2)) {
insertSort(nums, i);
}
}
private static void insertSort(int[] nums, int len) {
for (int i=len; i<nums.length; i++) {
int j = i - len;
int cur = nums[i];
while (j >= 0 && cur < nums[j]) {
nums[j + len] = nums[j];
j = j - len;
}
nums[j + len] = cur;
}
}
}
3.2 交换排序
1）冒泡排序
思路：在一趟排序中，若[i] < [j]，交换两个元素，否则继续向下走。一趟排序结束后，最大关键字被交换到了最后固定位置。如此反复多趟，直到在某一趟一次交换也不发生，排序结束
复杂度：
- 时间复杂度：O(n2)
- 空间复杂度：O(1)
public class BubbleSort {
private static void bubbleSort(int[] nums) {
boolean flag = true;
for (int i=0; flag; i++) {
flag = false;
// 若未发生交换则已经排好序
for (int j=nums.length-1; j>=1; j--) {
if (nums[j] < nums[j-1]) {
swap(nums, j, j-1);
flag = true;
}
}
}
}
private static void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
2）快速排序
思路：根据分割函数，确定分割数字的最终位置，分成左右两侧。左侧 <=【分割数字】，【分割数字】 <= 右侧。递归执行
复杂度：
- 时间复杂度：O(nlogn)
- 空间复杂度：O(logn)
代码1
public class S2_QuickSort {
private static void quickSort(int [] nums, int l, int r) {
if (l < r) {
int mid = partition(nums, l, r);
quickSort(nums, l, mid - 1);
quickSort(nums, mid+1, r);
}
}
private static int partition(int[] nums, int l, int r) {
int flag = nums[r];
while (l < r) {
while (l < r && nums[l] < flag) l++;
if (l < r) nums[r--] = nums[l];
while (l < r && nums[r] > flag) r--;
if (l < r) nums[l++] = nums[r];
}
nums[l] = flag;
return l;
}
}
代码2
public class S2_QuickSort2 {
private static void quickSort(int [] nums, int l, int r) {
if (l < r) {
int mid = partition(nums, l, r);
quickSort(nums, l, mid - 1);
quickSort(nums, mid+1, r);
}
}
private static int partition(int[] nums, int l, int r) {
int flag = nums[r];
int i = l - 1; // i指向的位置是分割左侧的最后一个位置
for (int j=l; j<r; j++) {
if (nums[j] < flag) {
i = i + 1;
swap(nums, i, j);
}
}
swap(nums, i + 1, r);
return i + 1;
}
private static void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
3.3 选择排序
1）简单选择排序
思路：从头到尾在无序序列找到最小关键字，和无序序列第一个元素进行交换。如此反复，直至排序结束
复杂度：
- 时间复杂度：O(n2)
- 空间复杂度：O(1)
public class SelectSort {
private static void selectSort(int[] nums) {
for (int i=0; i<nums.length-1; i++) {
int minj = i;
for (int j=i; j<nums.length; j++) {
if (nums[j] < nums[minj]) minj = j;
}
int t = nums[i]; nums[i] = nums[minj]; nums[minj] = t;
}
}
}
2）堆排序
思路：
- 构建最大堆（存储形式：数组）
- 将头部最大元素与尾部元素交换，将除尾部以外的元素堆堆化调整最大堆（此次堆化，有头节点开始向下堆化即可）
- 如此反复上述步骤
复杂度：
- 时间复杂度：O(nlogn)
- 堆化：O(logn)
- 交换n次
- 空间复杂度：O(1)
public class HeapSort {
private static void heapSort(int[] nums) {
int n = nums.length - 1;
// 堆化成大根堆
for (int i=n/2; i>=0; i--) {
heapify(nums, n, i);
// System.out.println(nums[0]);
}
while (n > 0) {
// 排序 选取关键字
swap(nums, 0, n);
n--;
// 堆化
heapify(nums, n, 0);
}
}
// 建立大根堆
private static void heapify(int[] nums, int n, int i) {
int l = 2 * i + 1;
int r = 2 * i + 2;
int t = i;
if (l <= n && nums[l] > nums[t]) t = l;
if (r <= n && nums[r] > nums[t]) t = r;
if (t != i) {
swap(nums, t, i);
heapify(nums, n, t);
}
}
private static void swap(int[] nums, int i, int j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
3.4 归并排序
1）二路归并排序
思路：递归分割为多个有序数组，后合并为一个有序数组
复杂度：
- 时间复杂度：O(nlogn)
- 空间复杂度：O(n)
public class MergeSort {
private static void mergeSort(int[] nums, int l, int r) {
if (l >= r) return ;
int mid = l + r >> 1;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
merge(nums, l, mid, r);
}
private static void merge(int[] nums, int l, int mid, int r) {
int[] tmp = new int[r - l + 1];
int i1 = l;
int i2 = mid + 1;
int idx = 0;
while (i1 <= mid && i2 <= r) {
if (nums[i1] < nums[i2]) tmp[idx++] = nums[i1++];
else tmp[idx++] = nums[i2++];
}
while (i1 <= mid) tmp[idx++] = nums[i1++];
while (i2 <= r) tmp[idx++] = nums[i2++];
for (int j=l, j1=0; j<=r; j++) nums[j] = tmp[j1++];
}
}
3.5 基数排序
思路：多关键字排序
3.6 计数排序
思路：
- 记录所有数组元素出现的次数在数组C
- 求其数组C的前缀和，（求前缀和的目的是放置元素的对应位置）
- 放置元素是从某一组元素的最后一个位置开始放置，（如：C[1] = 3，那么 B[3] = 1, B[2] = 1, B[1] = 1）
- 恢复元素到原有数组，（因为B数组元素从1开始）
public class CountSort {
private static int NMAX = 1000; // 数字最大值
private static void countSort(int[] nums) {
int n = nums.length;
int[] C = new int[NMAX + 1];
int[] B = new int[n + 1];
for (int i=0; i<n; i++) C[nums[i]]++;
for (int i=1; i<=NMAX; i++) C[i] = C[i] + C[i-1];
for (int i=0; i<n; i++) {
B[C[nums[i]]] = nums[i];
C[nums[i]]--;
}
// System.out.println(Arrays.toString(B));
for (int i=1; i<=n; i++) nums[i - 1] = B[i];
}
}
参考链接：
https://www.cnblogs.com/onepixel/articles/7674659.html
这篇关于排序算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
手写消息中间件：从零开始的指南11-26
-
Java语音识别项目资料：新手入门教程11-26
-
JAVA语音识别项目资料：新手入门教程11-26
-
Java语音识别项目资料：入门与实践指南11-26
-
Java云原生资料入门教程11-26
-
Java云原生资料入门教程11-26
-
Java云原生资料：新手入门教程11-26
-
Java创意资料：新手入门的创意学习指南11-25
-
JAVA对接阿里云智能语音服务资料详解：新手入门指南11-25
-
Java对接阿里云智能语音服务资料详解11-25
-
Java对接阿里云智能语音服务资料详解11-25
-
JAVA副业资料：新手入门及初级提升指南11-25
-
Java副业资料：入门到实践的全面指南11-25
-
Springboot应用的多环境打包项目实战11-25
-
SpringBoot应用的生产发布项目实战入门教程11-25
栏目导航
