排序算法
2021/6/26 20:29:51
本文主要是介绍排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
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
这篇关于排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求