`
superich2008
  • 浏览: 323305 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

java快速排序

阅读更多
先简单说一下快速排序的原理(思路):
1、给定一个数组,选取其中一个元素作为枢纽元(pivot)通常为数组最中间的那个元素;
2、由枢纽元(pivot)将数组分为不相交的2个集合,S1和S2;
3、从S1的第一个元素开始和枢纽元(pivot)比较,找到第一个大于枢纽元(pivot)的元素后停止;
4、从S2的最后一个元素开始和枢纽元(pivot)比较,找到第一个小于枢纽元(pivot)的元素后停止;
5、交换第3步和第4步找到的2个元素,递归此操作;
6、此时枢纽元(pivot)左边集合S1都比枢纽元(pivot)小,右边集合S2都比枢纽元(pivot)大,递归2、3、4、5步,直到所有元素有序。

例如:
第1步:13、81、92、43、65、31、57、26、75 选取枢纽元(pivot)65
第2步:S1(13、81、92、43)找到第一个大于65的数81,S2(31、57、26、75)找到第一个小于65的数(从后往前找26
第3步:交换81和26的位置S1(13、26、92、43)S2(31、57、81、75)
第4步:递归操作,最后结果:S1(13、26、57、43、31)S2(92、81、75),此时数组元素顺序为:13、26、57、43、31、65、92、81、75
第5步:分别递归操作S1和S2,最后结果:13、26、31、43、57、65、75、81、92(有序数组)

代码如下:

 /**
	 * 快速排序
	 * 
	 * @param nums
	 */
	public static void quickSort(int[] nums)
	{
		if (null == nums || nums.length < 1)
			return;
		
		final int len = nums.length;
		sort(nums, 0, len-1);
	}
	
	private static void sort(int[] nums, int low, int high)
	{
		if (low < high)
		{
			int m = getPartition(nums, low, high);
			sort(nums, low, m-1);
			sort(nums, m+1, high);
		}
	}
	
	private static int getPartition(int[] nums, int low, int high)
	{
		int tmp = nums[(low+high)/2];
		while (low < high)
		{
			while(low < high && nums[high] > tmp)
			{
				high--;
			}
			while (low < high && nums[low] < tmp)
			{
				low++;
			}
			if (low < high)
			{
				swap(nums, low, high);
			}
		}
		return low;
	}
	
	/**
	 * 交换元素
	 * 
	 * @param nums
	 * @param i
	 * @param j
	 */
	private static void swap(int[] nums, int i, int j)
	{
		if (i == j)
			return;
		
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}


运行测试,测试结果ok,是不是就没问题了呢?采用随机数组测试,发现只要数组中有相同元素存在,就会导致没有结果(死循环)!!why?

稍微修改一下getPartition方法即可:在交换2个元素之前判断一下是否相等

	private static int getPartition(int[] nums, int low, int high)
	{
		int tmp = nums[(low+high)/2];
		while (low < high)
		{
			while(low < high && nums[high] > tmp)
			{
				high--;
			}
			while (low < high && nums[low] < tmp)
			{
				low++;
			}
			if (low < high)
			{
				if (nums[low] == nums[high])
				{
					low++;
					continue;
				}
				swap(nums, low, high);
			}
		}
		return low;
	}



ok,再接着测试,没问题了。。。。

备注:可以单独写一个检查数组是否有序的方法

 /**
	 * 检查数组是否有序
	 * 
	 * @param nums
	 * @return true:有序 false:无序
	 */
	private static boolean checkIsSortNums(int[] nums)
	{
		boolean flag = true;
		int tmp = -1;
		final int len = nums.length;
		for (int i = 0; i < len; i++)
		{
			if (i > 0 && nums[i] < tmp)
			{
				flag = false;
				System.err.println("该数组不是有序数组!!!");
				break;
			} else
			{
				tmp = nums[i];
			}
		}
		return flag;
	}
分享到:
评论

相关推荐

    java快速排序算法实现

    快速排序是一种高效的排序算法,由英国计算机科学家C.A.R....这个压缩包中的"java快速排序算法"可能包含了更多关于快速排序的示例代码、详细解析和实践练习,可以帮助初学者更好地理解和掌握这种高效的排序算法。

    java 快速排序 折半查找的界面实现 (递归与分治法)

    总的来说,快速排序和折半查找是计算机科学中不可或缺的算法,通过递归和分治策略,可以在Java中高效地实现这些算法,并结合界面设计,为用户提供直观的交互体验。在实际项目中,理解和掌握这些算法有助于优化数据...

    Java 快速排序

    以下是一个简单的Java快速排序算法的实现: ```java public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low ) { // 找到基准元素的正确位置 int pivotIndex = ...

    java 快速排序程序

    java 编写的快速排序程序递归形式我做的课堂作业,,希望能帮助大家。。。

    Java 快速排序算法

    Java 快速排序,目前来说效率很高的一种排序算法,好理解。

    java快速排序动画jar

    之前做的四种排序动画,快排比较快,所以为快排专门做一个动画

    java 快速排序 折半查找的界面实现

    总的来说,"java 快速排序 折半查找的界面实现"项目旨在通过可视化的方式帮助学习者理解和掌握这两种经典的算法。通过实际的代码实现和交互式的界面,不仅能够锻炼编程技能,还能加深对算法本质的理解,对于提升编程...

    JAVA快速排序法.pdf

    JAVA快速排序法 JAVA快速排序法是一种高效的排序算法,属于选择排序的一种。它的主要思想是通过选择一个基准元素,将数组分成两个部分:一部分比基准元素小,一部分比基准元素大,然后递归地对这两个部分进行排序。...

    快速排序 java代码

    java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码

    [原]Java 快速排序

    以上就是Java快速排序的基本原理和源码分析。快速排序的平均时间复杂度为O(n log n),在最坏情况下(已经排序或逆序)时间复杂度为O(n^2)。由于其高效的性能和相对简单的实现,快速排序在实际应用中被广泛使用。

    java快速排序算法和案例

    java快速排序算法和案例

    快速排序算法的java实现

    在Java中实现快速排序,我们通常会定义一个`quickSort()`方法,该方法接受一个整数数组作为参数。快速排序的核心在于选择一个基准元素(pivot),并重新排列数组使得所有小于基准的元素都在其前,所有大于基准的元素...

    java实现快速排序

    在Java中实现快速排序,我们可以遵循以下步骤: 1. **选择基准值(Pivot)**:首先,我们需要从数组中选取一个元素作为基准,这个元素将被用来分割数组。通常选择第一个或最后一个元素,但也可以是随机选取的。 2....

    java快速排序法

    清楚明确的代码书写,让你轻易学懂快速排序法

    简单的快速排序

    在Java中实现快速排序,我们需要定义一个方法来执行这个过程。下面是一个简化的快速排序算法的Java实现: ```java public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if ...

    java快速排序工具类

    使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。

    基础编程:Java快速排序实例详解

    基础编程:Java快速排序实例详解

    快速排序算法java代码

    "快速排序算法java代码" 快速排序算法是由Tony Hoare在1960年提出的一种排序算法,它的平均时间复杂度为O(n log n),是目前最快的排序算法之一。下面我们将详细地讲解快速排序算法的java代码实现。 快速排序算法的...

    算法实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)

    包括所有算法分析设计的实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)

    java快速排序、随机优化快排

    java快速排序,和随机优化快排 注解详细,多个版本可选,最简洁版、最高效率版、随机优化版...

Global site tag (gtag.js) - Google Analytics