结果:
2097151
合并排序执行时间:443
合并排序递归树深度:4194301
快速排序执行时间:207
快速排序递归树深度:2795757
package com.zte.it.study.sort;
import java.util.Arrays;
/**
* 类名: 排序算法比较 <br/>
* 功能: TODO ADD FUNCTION. <br/>
* 时间:2015-3-6 下午6:55:52
*
* @author 10156351
* @version
* @since JDK 1.6
*/
public class 排序算法比较
{
static int recursive = 0;
/**
* main:(这里用一句话描述这个方法的作用). <br/>
*
* @author 10156351
* @param args
* @since JDK 1.6
*/
public static void main(String[] args)
{
int num = Integer.MAX_VALUE >> 10;
System.out.println(num);
int[] array = new int[num];
int[] array2 = new int[num];
int[] array3 = new int[num];
int[] array4 = new int[num];
for (int i = 0; i < num; i++)
{
array[i] = (int) (Math.random() * Integer.MAX_VALUE);
array2[i] = array[i];
array3[i] = array[i];
array4[i] = array[i];
}
long startTime = System.currentTimeMillis();
recursive = 0;
mergeSort(array);
System.out.println("合并排序执行时间:" + (System.currentTimeMillis() - startTime));
System.out.println("合并排序递归树深度:" + recursive);
//
startTime = System.currentTimeMillis();
recursive = 0;
quicksort(array2, 0, num - 1);
System.out.println("快速排序执行时间:" + (System.currentTimeMillis() - startTime));
System.out.println("快速排序递归树深度:" + recursive);
// startTime = System.currentTimeMillis();
// recursive = 0;
// quickSort2(array3, 0, num - 1);
// System.out.println("快速排序执行时间:" + (System.currentTimeMillis() - startTime));
// System.out.println("快速排序递归树深度:" + recursive);
//
// startTime = System.currentTimeMillis();
// recursive = 0;
// quickSort3(array4, 0, num - 1);
// System.out.println("快速排序执行时间:" + (System.currentTimeMillis() - startTime));
// System.out.println("快速排序递归树深度:" + recursive);
// for (int i = 0; i < num / 1024; i++)
// {
// System.out.print(array2[i] + " ");
// if (i % 20 == 19)
// System.out.println(array2[i]);
// }
}
public static void quicksort(int[] v, int left, int right)
{
recursive++;
if (left < right)
{
int key = v[left];
int low = left;
int high = right;
while (low < high)
{
while (low < high && v[high] > key)
{
high--;
}
if (low < high)
{
v[low] = v[high];
low++;
}
while (low < high && v[low] < key)
{
low++;
}
if (low < high)
{
v[high] = v[low];
high--;
}
}
v[low] = key;
quicksort(v, left, low - 1);
quicksort(v, low + 1, right);
}
}
public static int[] quickSort2(int[] targetArr, int start, int end)
{
recursive++;
int i = start + 1, j = end;
int key = targetArr[start];
if (start >= end)
return targetArr;
/*
* 从i++和j--两个方向搜索不满足条件的值并交换
*
* 条件为:i++方向小于key,j--方向大于key
*/
while (true)
{
while (targetArr[j] > key)
j--;
while (targetArr[i] < key && i < j)
i++;
if (i >= j)
break;
swap(targetArr, i, j);
if (targetArr[i] == key)
{
j--;
}
else
{
i++;
}
}
/* 关键数据放到‘中间’ */
swap(targetArr, start, j);
if (start < i - 1)
{
quickSort2(targetArr, start, i - 1);
}
if (j + 1 < end)
{
quickSort2(targetArr, j + 1, end);
}
return targetArr;
}
public static void quickSort3(int[] targetArr, int start, int end)
{
recursive++;
int i = start, j = end;
int key = targetArr[start];
while (i < j)
{
/* 按j--方向遍历目标数组,直到比key小的值为止 */
while (j > i && targetArr[j] >= key)
{
j--;
}
if (i < j)
{
/* targetArr[i]已经保存在key中,可将后面的数填入 */
targetArr[i] = targetArr[j];
}
/* 按i++方向遍历目标数组,直到比key大的值为止 */
while (i < j && targetArr[i] <= key)
/* 此处一定要小于等于零,假设数组之内有一亿个1,0交替出现的话,而key的值又恰巧是1的话,那么这个小于等于的作用就会使下面的if语句少执行一亿次。 */
{
i++;
}
if (i < j)
{
/* targetArr[j]已保存在targetArr[i]中,可将前面的值填入 */
targetArr[j] = targetArr[i];
}
}
/* 此时i==j */
targetArr[i] = key;
if (i - start > 1)
{
/* 递归调用,把key前面的完成排序 */
quickSort3(targetArr, start, i - 1);
}
if (end - j > 1)
{
/* 递归调用,把key后面的完成排序 */
quickSort3(targetArr, j + 1, end);
}
}
public static void swap(int[] arr, int start, int end)
{
int tmp = arr[start];
arr[start] = arr[end];
arr[end] = tmp;
}
public static void mergeSort(int[] array)
{
recursive++;
int length = array.length;
int middle = length / 2;
if (length > 1)
{
int[] left = Arrays.copyOfRange(array, 0, middle);// 拷贝数组array的左半部分
int[] right = Arrays.copyOfRange(array, middle, length);// 拷贝数组array的右半部分
mergeSort(left);// 递归array的左半部分
mergeSort(right);// 递归array的右半部分
merge(array, left, right);// 数组左半部分、右半部分合并到Array
}
}
// 合并数组,升序
private static void merge(int[] result, int[] left, int[] right)
{
int i = 0, l = 0, r = 0;
while (l < left.length && r < right.length)
{
if (left[l] < right[r])
{
result[i] = left[l];
i++;
l++;
}
else
{
result[i] = right[r];
i++;
r++;
}
}
while (r < right.length)
{// 如果右边剩下合并右边的
result[i] = right[r];
r++;
i++;
}
while (l < left.length)
{
result[i] = left[l];
l++;
i++;
}
}
}
相关推荐
java 快速排序 折半查找的界面实现 (递归与分治法)
编写选择排序,插入排序,自顶向上合并排序,合并排序,快速排序,理解各排序算法的实现原理,加深对排序算法的理解。
问题描述:实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法 实验要求: A. 在随机产生的空间大小分别为 N = 10, 1000,10000,100000 的排序样本(取值为[0,1])上测试以上算法。 B.结果输出...
Java QuickSort and MergeSort 想要得快来拿吧!
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
一个算法设计与分析的实验报告,比较归并排序与快速排序的时间差异,这里采用在一个java程序中对随机生成的任意个数分别进行两种方法的排序并记录各自的时间,最后得出结论。 本实验报告附代码以及详细解释
快速排序:是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短; 堆排序 : 如果内存空间允许且要求稳定性的, 归并排序:它有一定数量的数据移动,所以我们...
Java数组排序:冒泡排序、选择排序 、插入排序 、快速排序、希尔排序、堆排序和归并排序 三种Java数组复制方法 Java数组最大最小值 四种合并Java数组方法 Java数组升降序排序 Java数组查找:二分查找、顺序查找、...
包含各种典型内排序的java算法,包括:...冒泡排序,堆排序,插入排序,合并排序,快速排序,Shell排序(代码未完成),直接选择排序。 各种排序效率对比参见: http://blog.csdn.net/tanggod/article/details/19149007
随机生成10000数字,进行快速排序,并输出排序后的数组,及耗时
Java的算法 排序算法 冒泡排序 堆排序 插入排序 合并排序 快速排序 选择排序 希尔排序
Java排序 四.插入排序及其实现 五.快速排序及其实现 六.合并排序及其实现
快速排序(Quick Sort):通过选取一个基准元素,将数组分为两部分,一部分小于基准元素,另一部分大于基准元素,然后递归地对这两部分进行排序。 归并排序(Merge Sort):将数组分成两半,分别对这两部分进行排序...
增加了使用随机值做分割的快速排序,算法效果相比使用最后一个数做分割的快速排序较好
主要实现算法:冒泡排序、选择排序、插入排序、快速排序、合并排序、堆排序。
插入排序,合并排序,快速排序
合并排序法 基数排序法 循序搜寻法(使用卫兵) 二分搜寻法(搜寻原则的代表) 插补搜寻法 费氏搜寻法 堆叠 - 使用阵列实作 堆叠 - 使用链结实作(C 语言动态记忆体宣告) 堆叠 - 使用 Java 作物件封装 佇...
快速排序算法是基于分治策略的另一个排序算法。其基本思想是:对输入的子数组a[p:r],按以下三个步骤进行排序。 1) 分解(Divide)(2) 递归求解(Conquer)(3) 合并(Merge)
SortingAlgorithmSpeedTest 在我的学校课程中为COMP 2080制作对Java中的选择排序,插入排序,合并排序和快速排序进行速度测试,以查看它们之间的差异-基于来自相同核心数据池的50、1000、10000、100000和1000000组在...
演算法 实现搜索和排序算法,包括快速排序,合并排序和二进制搜索