/* MergeSort.java
CSC 225 - Spring 2016
Assignment 2 - Template for Merge Sort (Linked List version)
This template includes some testing code to help verify the implementation.
To interactively provide test inputs, run the program with
java MergeSort
To conveniently test the algorithm with a large input, create a
text file containing space-separated integer values and run the program with
java MergeSort file.txt
where file.txt is replaced by the name of the text file.
NOTE: For large input files, the depth of recursion may cause the Java
runtime environment to run out of stack space. To remedy this, run java
with the extra parameter "-Xss64m" (which increases the stack size to 64
megabytes). For example: java -Xss64m MergeSort input_data.txt
B. Bird & M. Simpson - 03/22/2015
*/
import java.util.Scanner;
import java.util.Vector;
import java.util.Arrays;
import java.io.File;
//Do not change the name of the MergeSort class
public class MergeSort{
/* MergeSort(head)
Given a reference to the head of a list, sort the contents of the list
with merge sort and return a reference to the sorted list. Your
implementation may create a new list or modify the input list.
To achieve full marks, you may not use any iterative loop constructs
(including for loops, while loops or do-while loops); all iteration
must be accomplished with recursion.
You may add additional functions (or classes) if needed, but the entire program must be
contained in this file.
Do not change the function signature (name/parameters).
*/
public static ListNode MergeSort(ListNode head){
/* ... Your code here ... */
return head;
}
/* ListNode class */
/* Do not change, add or remove any aspect of the class definition below.
If any of the contents of this class are changed, your submission will
not be marked.
The members of the class should be accessed directly (e.g. node.next,
node.value), since no get/set methods exist.
However, you may create a subclass of this class if you want to extend
its functionality. Ensure that your subclass is contained in MergeSort.java
with the rest of your code (since you may only submit one file).
*/
public static class ListNode{
int value;
ListNode next;
public ListNode(int value){
this.value = value;
this.next = null;
}
public ListNode(int value, ListNode next){
this.value = value;
this.next = next;
}
}
/* Testing code */
/* listLength(node)
Compute the length of the list starting at the provided node.
*/
public static int listLength(ListNode node){
if (node == null)
return 0;
return 1 + listLength(node.next);
}
/* testSorted(node)
Returns true if all elements of the list starting at the provided node
are in ascending order.
*/
public static boolean testSorted(ListNode node){
//An empty list is always considered sorted.
if (node == null)
return true;
//A list with one element is always considered sorted.
if (node.next == null)
return true;
//Test whether the first element is greater than the second element
if (node.value > node.next.value){
//If so, the list is not sorted.
return false;
}else{
//Otherwise, test whether the remaining elements are sorted and
//return the result.
return testSorted(node.next);
}
}
/* printList(node)
Print all list elements starting at the provided node.
*/
public static void printList(ListNode node){
if (node == null)
System.out.println();
else{
System.out.print(node.value + " ");
printList(node.next);
}
}
/* readInput(inputScanner)
Read integer values from the provided scanner into a linked list.
Each recursive call reads one value, and recursion ends when the user
enters a negative value or the input file ends.
*/
public static ListNode readInput(Scanner inputScanner){
//If no input is left, return an empty list (i.e. null)
if (!inputScanner.hasNextInt())
return null;
int v = inputScanner.nextInt();
//If the user entered a negative value, return an empty list.
if (v < 0)
return null;
//If the user entered a valid input value, create a list node for it.
ListNode node = new ListNode(v);
//Scan for more values recursively, and set the returned list of values
//to follow the node we just created.
node.next = readInput(inputScanner);
//Return the created list.
return node;
}
/* main()
Contains code to test the MergeSort function. Nothing in this function
will be marked. You are free to change the provided code to test your
implementation, but only the contents of the MergeSort() function above
will be considered during marking.
*/
public static void main(String[] args){
Scanner s;
if (args.length > 0){
try{
s = new Scanner(new File(args[0]));
} catch(java.io.FileNotFoundException e){
System.out.printf("Unable to open %s\n",args[0]);
return;
}
System.out.printf("Reading input values from %s.\n",args[0]);
}else{
s = new Scanner(System.in);
System.out.printf("Enter a list of non-negative integers. Enter a negative value to end the list.\n");
}
ListNode inputListHead = readInput(s);
int inputLength = listLength(inputListHead);
System.out.printf("Read %d values.\n",inputLength);
long startTime = System.currentTimeMillis();
ListNode sortedListHead = MergeSort(inputListHead);
long endTime = System.currentTimeMillis();
double totalTimeSeconds = (endTime-startTime)/1000.0;
//Compute the length of the output list
int sortedListLength = listLength(sortedListHead);
//Don't print out the values if there are more than 100 of them
if (sortedListLength <= 100){
System.out.println("Sorted values:");
printList(sortedListHead);
}
//Check whether the sort was successful
boolean isSorted = testSorted(sortedListHead);
System.out.printf("List %s sorted.\n",isSorted? "is":"is not");
System.out.printf("Total Time (seconds): %.2f\n",totalTimeSeconds);
}
}
- 大小: 518.4 KB
- 大小: 169.5 KB
分享到:
相关推荐
非递归归并排序.cpp
归并排序,消除递归归并排序,快排,Java实现
非递归归并排序详细分析,Java实现. 非常详细,基本上可以看明白
用C++实现的非递归的归并排序,此为实验小程序,仅供参考。
分治法排序算法
归并排序的非递归实现详细介绍了归并排序的非递归实现
c++实现的合并排序算法 用递归和非递归两种方式实现的
插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序
合并排序的C程序。递归写法。第一次上传文件。谢谢大家支持。
NULL 博文链接:https://yuan.iteye.com/blog/308778
递归实现的二路归并排序算法,其中对结构体按其内部一个关键字(本例是对一个任务结构体,按其收益排序)进行排序
源程序给出了插入排序、选择排序、希尔排序、堆排序、冒泡、双向冒泡、快速排序、归并排序、递归的归并排序、基数排序等多种排序算法,其中有17处需要填空。
8645 归并排序 (非递归算法).txt
用C语言写的归并排序的递归写法.这是本人按照书本上的定义揣摩出来的写法。仅供大家参考。另外我的资源中还有非递归和自然归并。敬请下载。
直接插入排序 冒泡排序 快速排序 直接选择排序 堆排序 二路归并排序 C#源代码 使用C#实现的数据结构中的排序算法
归并排序的非递归排序的代码解析
递归调用归并排序.cpp
c语言实现归并排序,递归方式实现,含详细注释
一个Java小程序,利用递归思想实现的归并排序算法。其中有两个类,排序数据是写死在main方法中的。
归并排序,两种实现方法,一种是递归实现,另一种是非递归实现……可直接在vc6.0平台上编译运行,并按要求输入,便可从小到大的顺序输出……