public class QuickSort {
private static Comparable median3(Comparable[] data, int left, int right){
int center = (left + right) / 2;
if(data[center].compareTo(data[left]) < 0)
swapReferences(data, left ,center);
if(data[right].compareTo(data[left]) < 0)
swapReferences(data, left, right);
if(data[right].compareTo(data[center]) < 0)
swapReferences(data, center, right);
swapReferences(data, center, right - 1);
return data[right - 1];
}
private static void swapReferences(Comparable[] data, int src, int des){
Comparable tmp;
tmp = data[des];
data[des] = data[src];
data[src] = tmp;
}
private static void quicksort(Comparable[] data, int left, int right){
if(left + CUTOFF <= right){
Comparable pivot = median3(data, left, right);
int i = left,j = right - 1;
for(;;){
while(data[++i].compareTo(pivot) < 0){}
while(data[--j].compareTo(pivot) > 0){}
if(i < j)
swapReferences(data, i, j);
else
break;
}
swapReferences(data, i, right - 1);
quicksort(data, left, i - 1);
quicksort(data,i + 1, right);
}
else
insertionSort(data, left, right);
}
private static void insertionSort(Comparable[] data, int left, int right){
int j;
for(int p = left; p <= right; p++){
Comparable tmp = data[p];
for(j = p; j > left && tmp.compareTo(data[j-1]) < 0; j--)
data[j] = data[j-1];
data[j] = tmp;
}
}
public static void quickSort(Comparable[] data){
quicksort(data, 0, data.length - 1);
}
public static void main(String[] args){
Comparable[] a = new Comparable[50];
for(int i = 0 ; i < a.length; i++)
a[i] = (int)(Math.random() * 1000);
for(int i = 0; i < a.length; i++)
System.out.print(a[i] + " , ");
System.out.println("After: ");
quickSort(a);
for(int i = 0; i < a.length; i++)
System.out.print(a[i] + ", ");
}
private final static int CUTOFF = 10;
}
分享到:
相关推荐
quickSort 方法实现了快速排序算法。通过选取一个基准值,将数组划分为左右两个子数组,并递归调用快速排序对子数组进行排序。在 partition 方法中,我们选择最右边的元素作为基准值,然后使用双指针进行比较和交换...
快速排序算法java实现,此程序所排序数组在程序中给出,没有输入。
快速排序方法...给新手一点指引,内置快速排序方法,有详细解析的链接地址,免费的
用Eclipse开发工具写的java,快速排序算法,被排序的数组是写死的,不过使用者可以更改被排序的数组
快速排序算法的Java实现。下载后把Package信息稍作修改即可运行。
主要介绍了Java中实现quickSort快速排序算法的方法,文章最后还介绍了一种单向扫描的实现方法,需要的朋友可以参考下
java写的八大经典排序算法(win7 jdk 1.6 下运行) 冒泡排序 BubbleSort 堆排序 HeapSort 插入排序 InsSort 快速排序 QuickSort 归并排序 MergeSort 基数排序 BucketSort 简单选择排序 SelectSort 希尔排序 Shell...
常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort), * 二路归并排序(MergeSort),堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现...
Java QuickSort and MergeSort 想要得快来拿吧!
用java实现了快速排序算法
该资源是一个快速排序的算法,很实用。开发语言是java,希望对大家有帮助。
自己用java寫的一個簡單的快速排序算法,實現從小到大的排序,之後的分治未涉及
本课程设计设计了一个快速排序的算法,该程序具有简单的排序功能。本程序采用了IntelliJ IDEA作为软件开发环境,采用了QuickSort核心算法来实现了对一些整数类型或字符类型的排序功能,操作简单,界面清晰,易于为...
快速排序-QuickSort | 堆排序-HeapSort :lion:搜索算法-搜索 与搜索相关的数据结构:二叉查找树,平衡查找树,散列表 线性查找-LinearSearch 二分查找-BinarySearch 广度优先搜索 深度优先搜索
可视化三种不同排序算法的Java应用程序:冒泡排序,快速排序和数组排序,可以选择对排序时进行的每个比较播放不同的音调。 该应用程序包含4个控件和一个按钮,用于开始可视化。 排序方法ChoiceBox允许在不同的排序...
代码如下:/* * quickSort.c * * Created on: 2012-4-9 * Author: LW */#include <stdio>#include typedef struct _student{ int id; char name[30];}student,*pStudent; student students[20] ={ {13,”...
leetcode切割分组 java_algorithm this is a sorting algorithm demo. created by InterlliJ. ...java ...快速排序 平均时间复杂度 O(n + k) 空间复杂度 O(k) CountingSort | 计数排序 | 用一个计算器
快速排序在这个项目中,我实现了最简单的Quicksort算法,并利用了两种不同的选择算法。 通过选择列表中的最后一个元素找到第一个枢轴,而使用中位数的中位数方法找到第二个枢轴,该方法将列表分为5s组,找到那些子组...
快速排序 7 20 10 合并排序 5 27 4 编译java部分 javac Main.java 编译scala部分 scalac Main.scala quicksort/Sort.scala mergesort/Sort.scala bubblesort/Sort.scala 回购的主要分支具有主要功能,该功能运行各种
演算法 实现搜索和排序算法,包括快速排序,合并排序和二进制搜索