package com.liany.demo.sort;
import java.util.Random;
/**
* 参考wiki源码写了一遍,并加了注释和自己的理解。
*
* 步骤:
* 1、取一随机位置的元素作为基准(pivot,或叫枢纽)
* 2、将基准移到最后位置(方便数组的其它元素与之比较),将小于此基准的元素放到数组的前面,
然后将基准移到所有比它小的元素的最大序号的下一个位置。
* 3、将这个基准的新位置返回,并作为迭代的分割点。
* 4、迭代比基准的前面、后面两个部分。
*
* @author modiliany
* @date: 2012-04-05
*/
public class MyQuickSort {
private Random random = new Random();
/**
* 交换
* @param array
*/
public void swap(int[] array, int i, int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
/**
* 查找枢纽的索引号
*/
public int getPivotIndex(int[] array, int begin, int end){
int index = begin + random.nextInt(end-begin+1);
int pivot = array[index];
//把pivot换到最后
swap(array, index, end);
for(int i=index=begin; i < end; i++){
if(array[i] < pivot){
//index从0开始计算了,记录小于pivot的值
//将小于pivot的值的元素移动到index位置
swap(array, index++, i);
}
}
swap(array, index, end);//将pivot放到所有比它小的元素的下一个位置(即此时的index位置)。
return index;
}
/**
* 快速排序法(Divide and conquer)
* @param array 待排序的数据
* @param begin 开始序号
* @param end 最后一个元素的序号
*/
public void quickSort(int[] array, int begin, int end){
if(end > begin){
int index = getPivotIndex(array, begin, end);
quickSort(array, begin, index-1);
quickSort(array, index+1, end);
}
}
/**
* @param args
*/
public static void main(String[] args) {
int [] array = {3, 1, 7, 5, 2, 9, 10, 4, 8, 6};
MyQuickSort sort = new MyQuickSort();
sort.quickSort(array, 0, array.length-1);
//输出
for(int val : array){
System.out.println(val);
}
}
}
wiki:
http://zh.wikipedia.org/zh-cn/快速排序
这里为了简单和方便理解排序的原理,只用了int数组。对象要比较的话,可以自己实现Comparator接口。
分享到:
相关推荐
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
Java排序方法详解大全 Java排序 快速排序 冒泡排序
idea项目:一个主类选择调用6个排序类,记录了学习排序算法的过程,可以自己更改优化,每一种排序是一个类,有需要可以copy走,可重用性强
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
在这个教程中,我们将深入探讨快速排序的工作原理,并提供一个Java示例来演示如何实现它。无论您是新手还是有经验的Java开发者,通过学习这个算法,您将获得一个强大的排序工具,有助于解决各种排序问题。 快速排序...
软件工程、快速排序法。绝顶的好东西。快速排序.Java快速排序.Java快速排序.Java
详细解释了快速排序的java实现.里面有代码,还有注释说明
java算法,快速排序、冒泡排序、选择排序 快速排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51822361 冒泡排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51819045
java 快速排序 折半查找的界面实现 (递归与分治法)
//排序类 提供int排序的静态方法 有以下排序: 快速排序 堆排序 计数排序 桶排序 归并排序
排序算法java版,速度排行:冒泡排序、简单选择排序、直接插入排序、折半插入排序、希尔排序、堆排序、归并排序、快速排序.mht
JAVA冒泡排序和快速排序算法,符合实验报告要求哦
java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码 java 快速排序实现。可以跑的代码
快速排序 java实现
这是一个用Java语言实现的快速排序算法,快速排序算法是根据分冶思想去实现的。
Java几种排序方法:冒泡排序,插入法排序,快速排序,选择排序.
java实现的快速排序算法
常用三种排序:快速排序、冒泡排序、插入排序的java实现示例
Java 快速排序,目前来说效率很高的一种排序算法,好理解。
使用泛型的对象排序工具类(使用算法:快速排序),适合初学者学习快速排序的基本原理和实现。