快速排序的基准数随机选择版本:
package arithmetic.sort; import java.util.Arrays; import java.util.Random; /** * * @author alchimie * * 随机快速排序(不稳定) * */ public class RandomQuickSort { Random random = new Random(); public void randomQuickSort(int[] arrs) { randomQuickSort(arrs, 0, arrs.length - 1); } private void randomQuickSort(int[] arrs, int low, int high) { int p; if (low < high) { p = randomPartition(arrs, low, high); randomQuickSort(arrs, low, p - 1); randomQuickSort(arrs, p + 1, high); } } /* * 划分基准数 */ private int randomPartition(int[] arrs, int left, int right) { int i, j, p; // 随机选择基准数 int ranInt = random.nextInt(right-left+1); int w = left + ranInt; p = arrs[w]; // p中存的就是基准数 swap(arrs, left, w); i = left; j = right; while (i != j) { // 顺序很重要,要先从右边开始找,否则i指针有可能停留在比p大的数上,导致归位交换出错 while (arrs[j] >= p && i < j) j--; // 再找右边的 while (arrs[i] <= p && i < j) i++; // 交换两个数在数组中的位置 if (i < j) { swap(arrs, i, j); } } // 最终将基准数归位 arrs[left] = arrs[i]; arrs[i] = p; System.out.println("基准数: " + p + " " + Arrays.toString(arrs)); return i; } /* * 交换指定数组的left和right索引的值 */ private void swap(int[] arrs, int left, int right){ int c = arrs[left]; arrs[left] = arrs[right]; arrs[right] = c; } public static void main(String args[]) { RandomQuickSort rqs = new RandomQuickSort(); int arrs[] = { 49, 38, 65, 97, 76, 13, 27, 49, 5, 83 }; rqs.randomQuickSort(arrs); for (int i = 0; i < arrs.length; i++) { System.out.println(arrs[i]); } } }
执行结果:
基准数: 76 [49, 38, 65, 5, 49, 13, 27, 76, 97, 83]
基准数: 5 [5, 38, 65, 49, 49, 13, 27, 76, 97, 83]
基准数: 13 [5, 13, 65, 49, 49, 38, 27, 76, 97, 83]
基准数: 49 [5, 13, 38, 27, 49, 49, 65, 76, 97, 83]
基准数: 38 [5, 13, 27, 38, 49, 49, 65, 76, 97, 83]
基准数: 97 [5, 13, 27, 38, 49, 49, 65, 76, 83, 97]
5
13
27
38
49
49
65
76
83
97
相关推荐
(1)用随机快速排序的方法,对输入的数值以从大到小的顺序进行快速排序。 (2)对随机快速排序和冒泡排序这两种排序方法进行比较,测试其在不同数值大小的情况下算法运行的时间复杂度。 二、 实验要求 快速排序...
在这个“普通快速排序随机快速排序算法实验”中,我们可以深入理解快速排序的实现细节和性能优化。首先,代码是用C语言编写的,C语言因其高效和灵活性,是实现算法的理想选择。实验包含了计时功能,这有助于我们分析...
随机主元快速排序的时间复杂度在平均情况下为O(nlogn),这是因为随机化使得快速排序在最坏情况下的可能性大大减小,更接近于平均情况。 在实际应用中,随机化快速排序通常优于非随机化的版本,因为它更稳定,对于...
算法讲解023【必备】随机快速排序
最省时间的是确定型算法,其次是随机基准快速排序算法,最后是随机化输入快速排序算法;后面两个算法较之确定型算法要费时的原因是:(1)随机选取基准花费了一些时间,(2)随机化输入是将原来数组打乱花费了一些时间。...
算法导论及算法设计与分析(高级版)的程序
在随机化快速排序中,可以通过随机选择一个元素作为基准,或者对输入序列进行随机重排,然后对重排后的序列应用快速排序。 为了验证两种快速排序的性能,可以通过实验对比它们在不同输入数据规模和不同数据分布情况...
随机快速排序则是快速排序的一种变体,它在选取基准元素时引入了随机性,以提高算法在最坏情况下的表现。 在标准的快速排序中,基准元素通常选择为数组的第一个元素或者最后一个元素。但这种固定的选择方式可能会...
在给出的"Lab 1"文件中,可能包含了实现快速排序的代码,包括普通快速排序和随机快速排序的版本,以及统计两种排序算法运行时间的代码。通过分析和运行这些代码,你可以更深入地理解快速排序的工作原理和性能特性。
通过对普通快速排序和随机快速排序的实现与比较,我们可以得出以下结论:随机快速排序相比普通快速排序在处理随机数据时表现更优,能够有效避免最坏情况的发生,提高排序效率。这对于实际应用中处理大规模数据集非常...
直接插入排序 直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下...
此外,快速排序的多种变种,如平衡快速排序、随机快速排序等,旨在解决特定场景下的问题,提高算法的稳定性和性能。这些变种通过调整枢轴的选择策略或采用不同的分区方法,能够有效避免最坏情况的发生,从而提升整体...
在计算机科学和编程领域,随机排序是一种常见的算法应用,它不同于常见的排序算法如冒泡排序、快速排序或归并排序,而是通过某种随机化过程来打乱数据的原有顺序。 随机排序的主要实现方法包括 Fisher-Yates(也...
本文将详细讨论三种排序算法的实现:桶排序、合并排序和随机快速排序。这些算法都是C语言实现的,旨在帮助程序员理解和应用这些方法来解决实际问题。 1. 桶排序(Bucket Sort) 桶排序是一种分布式排序算法,适用...
快速排序算法是一种有效的排序算法,虽然算法在最坏的情况下运行时间为 O(n^2),但由于平均运行时间为 O(nlogn),并且在内存使用、程序实现复杂性上表现优秀,尤其是对快速排序算法进行随机化的可能,使得快速排序在...
随机生成10000数字,进行快速排序,并输出排序后的数组,及耗时
### 快速排序知识点解析 #### 一、快速排序简介 快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它采用分治策略来把一个序列分为较小和较大的两个子序列,然后递归地...
本文将深入探讨“高级随机算法”中的三个重要概念:随机快速排序、随机选择以及随机采样,并阐述它们的实现方式以及如何通过直接读取后台数据来提高效率。 首先,我们来讨论随机快速排序。这是一种基于快速排序算法...
快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录...