数据结构与算法之随机算法与快速排序
2022/4/22 1:12:37
本文主要是介绍数据结构与算法之随机算法与快速排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
快速随机排序的思路是从一个数组中随机选择一个主元,然后将这个主元放到数组的最后.循环数组时,先定义一个指针,发现了比主元小的元素,如果指针和循环下标相同
则只是把指针自增,如果发现循环下标不同则将循环下标与指针位置交换,这样做的目的是始终保证指针左边的元素小于主元,最后循环结束将主元与指针位置交换.这样
就将数组分成了left pivot right.然后再递归left,right.
private static void quickInternal(int[] a, int l, int r) { // 终止条件 if (l >= r) { return; } // 查找分区点 int q = partition(a, l, r); quickInternal(a, l, q - 1); quickInternal(a, q + 1, r); } // 排序 private static int partition(int[] a, int l, int r) { if (a.length == 1) { return 0; } int random; if (l == 0) { random = new Random().nextInt(r + 1); } else { // 不为0 则 random = new Random().nextInt(r - l) + l; } if (random != r) { int tmp = a[random]; a[random] = a[r]; a[r] = tmp; } int pivot = a[r]; int m = l; for (int j = l; j < r; j++) { if (a[j] < pivot) { // 如果相等,不交换,同时后移一位 if (m == j) { m++; } else { int temp = a[m]; a[m++] = a[j]; a[j] = temp; } } } int temp = a[m]; a[m] = a[r]; a[r] = temp; return m; }
以下提供一个测试方法.
public static void main(String[] args) { Random random = new Random(); while (true) { int length = random.nextInt(10); int[] arr = new int[length]; int[] arr2 = new int[length]; for (int x = 0; x < length; x++) { int i = random.nextInt(10); arr[x] = i; arr2[x] = i; } quickInternal(arr, 0, arr.length - 1); Arrays.sort(arr2); boolean equals = Arrays.equals(arr2, arr); System.out.println(equals); if (!equals) { break; } } }
这篇关于数据结构与算法之随机算法与快速排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性