先简单说一下快速排序的原理(思路):
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 快速排序 折半查找的界面实现 (递归与分治法)
软件工程、快速排序法。绝顶的好东西。快速排序.Java快速排序.Java快速排序.Java
java 编写的快速排序程序递归形式我做的课堂作业,,希望能帮助大家。。。
快速排序方法...给新手一点指引,内置快速排序方法,有详细解析的链接地址,免费的
Java 快速排序,目前来说效率很高的一种排序算法,好理解。
之前做的四种排序动画,快排比较快,所以为快排专门做一个动画
java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码
java快速排序算法和案例
java 快速排序 折半查找 的界面实现(并附有递归分治法PPT)
清楚明确的代码书写,让你轻易学懂快速排序法
用Java对整型一维数组实现快速排序,pivot值默认为数组第一个值。
JAVA快速排序法.pdf
详细解释了快速排序的java实现.里面有代码,还有注释说明
使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。
基础编程:Java快速排序实例详解
两种方法: 传统的递归快速排序 采用非递归堆栈模拟
包括所有算法分析设计的实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)
快速排序是一个知名度极高的排序算法,其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。这里采用简单的小例子实现快速排序。