`
alchimie
  • 浏览: 20459 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

随机快速排序

 
阅读更多

快速排序的基准数随机选择版本:

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【必备】随机快速排序.pptx

    算法讲解023【必备】随机快速排序

    概率与计算课程作业 随机化快速排序和确定型快速排序的比较

    最省时间的是确定型算法,其次是随机基准快速排序算法,最后是随机化输入快速排序算法;后面两个算法较之确定型算法要费时的原因是:(1)随机选取基准花费了一些时间,(2)随机化输入是将原来数组打乱花费了一些时间。...

    随机快速排序算法

    算法导论及算法设计与分析(高级版)的程序

    确定性快速排序与随机化快速排序的比较

    在随机化快速排序中,可以通过随机选择一个元素作为基准,或者对输入序列进行随机重排,然后对重排后的序列应用快速排序。 为了验证两种快速排序的性能,可以通过实验对比它们在不同输入数据规模和不同数据分布情况...

    Quicksort-and-Randomized-Quicksort.zip_Randomizedquicksort_随机快速排

    随机快速排序则是快速排序的一种变体,它在选取基准元素时引入了随机性,以提高算法在最坏情况下的表现。 在标准的快速排序中,基准元素通常选择为数组的第一个元素或者最后一个元素。但这种固定的选择方式可能会...

    算法实验1-快速排序

    在给出的"Lab 1"文件中,可能包含了实现快速排序的代码,包括普通快速排序和随机快速排序的版本,以及统计两种排序算法运行时间的代码。通过分析和运行这些代码,你可以更深入地理解快速排序的工作原理和性能特性。

    算法导论中科大实验一__快速排序

    通过对普通快速排序和随机快速排序的实现与比较,我们可以得出以下结论:随机快速排序相比普通快速排序在处理随机数据时表现更优,能够有效避免最坏情况的发生,提高排序效率。这对于实际应用中处理大规模数据集非常...

    冒泡排序 直接选择排序 直接插入排序 随机快速排序 归并排序 堆排序.zip

    直接插入排序 直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下...

    数据结构快速排序算法实现

    此外,快速排序的多种变种,如平衡快速排序、随机快速排序等,旨在解决特定场景下的问题,提高算法的稳定性和性能。这些变种通过调整枢轴的选择策略或采用不同的分区方法,能够有效避免最坏情况的发生,从而提升整体...

    随机排序小工具

    在计算机科学和编程领域,随机排序是一种常见的算法应用,它不同于常见的排序算法如冒泡排序、快速排序或归并排序,而是通过某种随机化过程来打乱数据的原有顺序。 随机排序的主要实现方法包括 Fisher-Yates(也...

    三个排序问题的实现(桶排,合并,随机快排)

    本文将详细讨论三种排序算法的实现:桶排序、合并排序和随机快速排序。这些算法都是C语言实现的,旨在帮助程序员理解和应用这些方法来解决实际问题。 1. 桶排序(Bucket Sort) 桶排序是一种分布式排序算法,适用...

    快速排序算法相关分析

    快速排序算法是一种有效的排序算法,虽然算法在最坏的情况下运行时间为 O(n^2),但由于平均运行时间为 O(nlogn),并且在内存使用、程序实现复杂性上表现优秀,尤其是对快速排序算法进行随机化的可能,使得快速排序在...

    随机生成10000数字,进行快速排序

    随机生成10000数字,进行快速排序,并输出排序后的数组,及耗时

    快速排序 快速排序例子

    ### 快速排序知识点解析 #### 一、快速排序简介 快速排序是一种高效的排序算法,由英国计算机科学家托尼·霍尔(Tony Hoare)在1960年提出。它采用分治策略来把一个序列分为较小和较大的两个子序列,然后递归地...

    高级随机算法

    本文将深入探讨“高级随机算法”中的三个重要概念:随机快速排序、随机选择以及随机采样,并阐述它们的实现方式以及如何通过直接读取后台数据来提高效率。 首先,我们来讨论随机快速排序。这是一种基于快速排序算法...

    C语言实现多种链表快速排序

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R. Hoare在1960年提出,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录...

Global site tag (gtag.js) - Google Analytics