ArrayUtil:
import org.apache.commons.lang3.time.StopWatch;
public class ArrayUtil {
//交换数组元素
public static void swap(Comparable[] array, int left, int right) {
Comparable tempValue = array[left];
array[left] = array[right];
array[right] = tempValue;
}
//比较元素
public static boolean less(Comparable v, Comparable w) {
return v.compareTo(w) < 0;
}
//打印
public static void show(Comparable[] array) {
StringBuilder sb = new StringBuilder();
for (Comparable a : array) {
sb.append(a).append(" ");
}
System.out.println("排序后:" + sb.toString());
}
//判断是否有序
public static boolean isSort(Comparable[] array) {
for (int i = 1; i < array.length; i++) {
if (less(array[i], array[i - 1])) {
return false;
}
}
return true;
}
//选择排序方式,计算时间
public static double runTime(String method, Comparable[] array) throws Exception {
StopWatch watch = new StopWatch();
watch.start();
switch (method) {
case "Insertion": {
InsertSort.sort(array, 0, array.length);
break;
}
case "Selection": {
SimpleSelectionSort.sort(array);
break;
}
case "Shell": {
ShellSort.sort(array);
break;
}
case "Quick": {
QuickSort.optimizeSort(array, 0, array.length - 1);
break;
}
//快速排序的三向切分
case "Quick3Way":{
QuickSort.quick3way(array,0,array.length-1);
break;
}
case "Heap": {
HeapSort.sort(array);
break;
}
case "Bubble": {
BubbleSort.sort(array);
break;
}
//自顶向下归并
case "Merge": {
Comparable[] aux = new Comparable[array.length];
Merge.mergeSort(array, aux, 0, array.length - 1);
break;
}
//自底向上归并
case "MergeBU": {
Merge.mergeSortBu(array);
break;
}
default: {
throw new Exception("error");
}
}
watch.stop();
if (isSort(array)) {
return watch.getNanoTime();
}
throw new RuntimeException(method+"排序不成功");
}
/**
* @param method 使用排序方法的名称
* @param count 生成几组数据
* @param length 每组数据的长度
* @return total 平均使用时间 单位ms
* @throws Exception e
*/
public static void timeRandomInput(String method, int count, int length) throws Exception {
double total = 0.0;
Comparable[] array = new Comparable[length];
for (int i = 0; i < count; i++) {
for (int j = 0; j < length; j++) {
array[j] = StdRandom.uniform() * 100;
}
total += runTime(method, array);
}
double ms = total/count/100000;
String formatMs = String.format("%.2f", ms);
System.out.println(method+" 平均运行时间:"+formatMs);
}
}
随机数生成类:
import java.util.Random;
/**
* 此类提供一系列产生随机数的方法,以满足不同用例需要
*
* @author crazyMonkey
*/
public final class StdRandom {
//随机数对象
private static Random random;
//用于产生随机数的种子
private static long seed;
// 静态初始化区域
static {
//产生随机数种子
seed = System.currentTimeMillis();
random = new Random(seed);
}
private StdRandom() {
}
/***********************************************************
* 产生基本的随机数
***********************************************************/
/**
* 获取此类实例的伪随机种子生成器
*/
public static void setSeed(long s) {
seed = s;
random = new Random(seed);
}
/**
* 获取此类实例提供的伪随机种子生成器
*/
public static long getSeed() {
return seed;
}
/**
* 返回一个随机的范围在[0,1)之间的double类型的数
*/
public static double uniform() {
return random.nextDouble();
}
/**
* 返回一个随机的范围在[0,N)之间的int类型的数
*/
public static int uniform(int N) {
return random.nextInt(N);
}
/**
* 返回一个范围在 [0, 1)的实数
*/
public static double random() {
return uniform();
}
/**
* 返回一个范围在 [a, b)的int类型值
*/
public static int uniform(int a, int b) {
return a + uniform(b - a);
}
/**
* 返回一个范围在 [a, b)的实数
*/
public static double uniform(double a, double b) {
return a + uniform() * (b - a);
}
}
它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序。
代码:
public class QuickSort {
public static void optimizeSort(Comparable[] array, int left, int right) {
optimizeAdjust(array, left, right);
}
/**
* @param array 待排序数组
* @param left 数组的左界
* @param right 数组的右界
*/
//三数取中切分
private static void optimizeAdjust(Comparable[] array, int left, int right) {
if (left < right) {
if (right - left <= 15) {
InsertSort.sort(array, left, right);
return;
}
int i, j;
Comparable key;
i = left;
j = right;
int mid = i + (j - i) / 2;
if (ArrayUtil.less(array[j], array[mid])) {
ArrayUtil.swap(array, mid, j);
}
if (ArrayUtil.less(array[j], array[i])) {
ArrayUtil.swap(array, i, j);
}
if (ArrayUtil.less(array[i], array[mid])) {
ArrayUtil.swap(array, mid, i);
}
key = array[i];
while (ArrayUtil.less(i, j)) {
while (ArrayUtil.less(i, j) && !ArrayUtil.less(array[j], key)) {
// 从右向左找第一个小于x的数
j--;
}
array[i] = array[j];
while (i < j && !ArrayUtil.less(key, array[i])) {
// 从左向右找第一个大于x的数
i++;
}
array[j] = array[i];
}
array[i] = key;
commonAdjust(array, left, i - 1);
commonAdjust(array, i + 1, right);
}
}
public static void quick3way(Comparable[] a,int left,int right){
if (right<=left) return;
int lt =left, i = left+1,gt = right;
Comparable key = a[left];
while (i<=gt){
int temp = a[i].compareTo(key);
if (temp<0){
ArrayUtil.swap(a,lt++,i++);
}else if (temp>0){
ArrayUtil.swap(a,gt--,i);
}else {
i++;
}
}
quick3way(a,left,lt-1);
quick3way(a,gt+1,right);
}
}
public class BubbleSort {
public static void sort(Comparable[] array) {
int len = array.length;
int key = len - 1;
//用来标记,如果未标记,则表示没有发生交换,说明数组有序
int flag = 0;
//用来记录发生交换时的位置,这个位置之后,数组有序
int pos = 0;
//进行正向遍历后,再进行反向遍历
int start = 0;
for (int i = 0; i < len - 1; i++) {
flag = 0;
for (int j = start; j < key; j++) {
if (ArrayUtil.less(array[j+1],array[j])) {
ArrayUtil.swap(array, j, j + 1);
flag = 1;
pos = j;
}
}
if (flag == 0) {
break;
}
flag = 0;
key = pos;
//反向遍历,把最小值遍历到数组的左端
for (int k = key;k>start;k--){
if (ArrayUtil.less(array[k],array[k-1])){
ArrayUtil.swap(array,k,k-1);
flag = 1;
}
}
start++;
if (flag == 0) {
break;
}
}
}
}
public class InsertSort {
/*
* 插入排序 整体思路还是很简单,稍微优化,减少了数组的交换 复杂度N^2
*/
public static void sort(Comparable[] array,int start,int end) {
Comparable key;
for (int i = start+1; i < end; i++) {
key = array[i];
int j = i;
for (;j > start && ArrayUtil.less(key, array[j - 1]); j--) {
array[j] = array[j-1];
}
array[j] = key;
}
}
}
public class ShellSort {
/*
* 希尔排序 插入排序的优化算法
* h相等于步长,计算h的方法3*h+1,(1,4,13,40.....)
* 数组从0开始,步长为h,将0,0+h,0+2h...算作一个新的数组,对它们进行插入排序
* 从最大的h开始,每次插入排序后,h/=3,直到h=1,排序完成
* 运用了和插入排序同样的优化方法,减少了数组的交换
*/
public static void sort(Comparable[] array){
int len = array.length;
int h =1;
while (h<len/3){
h=3*h+1;
}
Comparable key;
while (h>=1){
for (int i = h;i<len;i++){
int j =i;
key = array[i];
for (;j>=h && ArrayUtil.less(key,array[j-h]);j-=h){
array[j] = array[j-h];
}
array[j] = key;
}
h/=3;
}
}
}
//简单选择排序,选择数组中最小的数,与数组左端交换,交换过后将左端下标+1
public class SimpleSelectionSort {
public static void sort(Comparable[] array){
int min;
int len = array.length;
for(int i = 0;i<len-1;i++){
min = i;
for (int j=min+1;j<len;j++){
if (ArrayUtil.less(array[j],array[min])){
min = j;
}
}
if (i!=min){
ArrayUtil.swap(array,i,min);
}
}
}
}
public class HeapSort {
/*
*初始化堆,规则:非叶子结点的值必定大于它的叶子结点,堆的顶端为数组的最大值
*建立堆过程自下而上
*/
public static void sort(Comparable[] array) {
initHeap(array);
int count = array.length;
while (count > 1) {
//交换数组的第0位和最后一位,第一位总是为数组最大值,然后将待排序个数减一
ArrayUtil.swap(array,count-1,0);
count--;
buildHeap(array, count, 0);
}
}
private static void initHeap(Comparable[] array) {
int arrayLen = array.length;
for (int index = (arrayLen / 2 - 1); index >= 0; index--) {
buildHeap(array, arrayLen, index);
}
}
/**
*
* @param array 待排序数组
* @param count 待排序元素的个数
* @param index 元素的索引值
*/
private static void buildHeap(Comparable[] array, int count, int index) {
int maxChildIdx;
while (index <= count / 2 - 1) {
//判断结点时候为偶数,如果是则只有左叶子结点
if (count % 2 == 0 && index == count / 2 - 1) {
maxChildIdx = index * 2 + 1;
} else {
int leftChildIdx = index * 2 + 1;
int rightChildIdx = index * 2 + 2;
//判断左右叶子结点谁大,并赋值
maxChildIdx = ArrayUtil.less(array[leftChildIdx],array[rightChildIdx]) ?
rightChildIdx: leftChildIdx;
}
/*
*判断结点是否大于它的父节点,是就交换它们,赋值进入下一次判断
* 建堆是自下而上的过程,while循环是自上而下再判断
*/
if (ArrayUtil.less(array[index] , array[maxChildIdx])) {
ArrayUtil.swap(array,index,maxChildIdx);
index = maxChildIdx;
} else {
break;
}
}
}
}
public class Merge {
public static void mergeSort(Comparable[] dest, Comparable[] src, int l, int r) {
if (l < r) {
int mid = (l + r) / 2;
mergeSort(dest, src, l, mid);
mergeSort(dest, src, mid + 1, r);
merge(dest, src, l, mid, r);
}
}
public static void mergeSortBu(Comparable[] array){
int N = array.length;
Comparable[] aux = new Comparable[N];
for (int n = 1; n < N; n = n+n) {
for (int i = 0; i < N-n; i += n+n) {
int lo = i;
int m = i+n-1;
int hi = Math.min(i+n+n-1, N-1);
merge(array, aux, lo, m, hi);
}
}
}
public static void merge(Comparable[] a,Comparable[] aux,int left,int mid,int right){
int i = left;
int j = mid+1;
for (int k = left;k<=right;k++){
aux[k] = a[k];
}
for (int k = left;k<=right;k++){
if (i>mid){
a[k] = aux[j++];
} else if (j>right) {
a[k] = aux[i++];
}
else if (ArrayUtil.less(aux[j],aux[i])){ a[k] = aux[j++];
}else {
a[k] = aux[i++];
}
}
}
}
public class Test {
public static void main(String[] args) throws Exception {
int count = 3;
int Length = 10000;
ArrayUtil.timeRandomInput(SortMethod.INSERTION, count, Length);
ArrayUtil.timeRandomInput(SortMethod.SELECTION, count, Length);
ArrayUtil.timeRandomInput(SortMethod.MERGE_BU, count, Length);
ArrayUtil.timeRandomInput(SortMethod.MERGE, count, Length);
ArrayUtil.timeRandomInput(SortMethod.BUBBLE, count, Length);
ArrayUtil.timeRandomInput(SortMethod.COMMON_QUICK, count, Length);
ArrayUtil.timeRandomInput(SortMethod.QUICK_3WAY, count, Length);
ArrayUtil.timeRandomInput(SortMethod.HEAP, count, Length);
}
}
运行截图:
如果您发现该资源为电子书等存在侵权的资源或对该资源描述不正确等,可点击“私信”按钮向作者进行反馈;如作者无回复可进行平台仲裁,我们会在第一时间进行处理!
加入交流群
请使用微信扫一扫!