Java ArrayList 的递归合并排序
Java Recursive MergeSort for ArrayLists
我的合并排序函数一直有问题,因为我无法在将一系列整数或字符串输入程序时对其进行排序。我有一个外部 class 将项目调用到其中,但它根本不对 numbers/strings 进行排序。两种方法如下,不知道问题出在哪里。数字随机输入
代码:
/**
* Takes in entire vector, but will merge the following sections together:
* Left sublist from a[first]..a[mid], right sublist from a[mid+1]..a[last].
* Precondition: each sublist is already in ascending order
*
* @param a
* reference to an array of integers to be sorted
* @param first
* starting index of range of values to be sorted
* @param mid
* midpoint index of range of values to be sorted
* @param last
* last index of range of values to be sorted
*/
private void merge(ArrayList<Comparable> a, int first, int mid, int last) {
int x;
int i;
ArrayList<Comparable> left = new ArrayList<Comparable>();
ArrayList<Comparable> right = new ArrayList<Comparable>();
mergeSort(a,first,mid);
for(i = 0; i < a.size() - mid; i++){
left.add(i,a.get(i));
a.remove(i);
}
mergeSort(a,mid,last);
for (x = mid; x < a.size(); x++) {
right.add(x,a.get(x));
a.remove(x);
}
if ((left.get(i).compareTo(right.get(x))) > 0) {
i++;
a.add(i);
} else if (i < x) {
x++;
a.add(x);
}
System.out.println();
System.out.println("Merge");
System.out.println();
}
/**
* Recursive mergesort of an array of integers
*
* @param a
* reference to an array of integers to be sorted
* @param first
* starting index of range of values to be sorted
* @param last
* ending index of range of values to be sorted
*/
public void mergeSort(ArrayList<Comparable> a, int first, int last) {
int mid = (first + last)/2;
if(first == last){
}else if(last - first == 1){
merge(a,first, mid ,last);
}else{
last = mid;
}
}
I have an outside class that calls items into it, however it simply doesn't sort the numbers/strings. The two methods are below, I don't know where the problem is.
第一个问题是,如果您使用 first = 0
和 last = a.size()
调用 mergeSort
方法,您将不会对任何内容进行排序,因为如果 last-first == 1
:
public void mergeSort(ArrayList<Comparable> a, int first, int last) {
int mid = (first + last)/2;
if(first == last){
}else if(last - first == 1){
// you only merge if last - first == 1...
merge(a,first, mid ,last);
}else{
last = mid;
}
}
从这一点来看,我不明白你是如何尝试实现合并排序算法的。它既不是自上而下,也不是自下而上的实现。你在 merge 方法中分裂,这也很奇怪。如果您提供了伪代码 + 调用 public
方法的方式,那么帮助您会更容易。恕我直言,您的算法确实存在问题。
事实上归并排序算法实现起来非常简单。为了说明这一点,我使用 Deque
而不是 List
对象编写了 top down implementation of the merge sort algorithm:
import java.util.Deque;
import java.util.LinkedList;
public class Example {
private LinkedList<Comparable> merge(final Deque<Comparable> left, final Deque<Comparable> right) {
final LinkedList<Comparable> merged = new LinkedList<>();
while (!left.isEmpty() && !right.isEmpty()) {
if (left.peek().compareTo(right.peek()) <= 0) {
merged.add(left.pop());
} else {
merged.add(right.pop());
}
}
merged.addAll(left);
merged.addAll(right);
return merged;
}
public void mergeSort(final LinkedList<Comparable> input) {
if (input.size() != 1) {
final LinkedList<Comparable> left = new LinkedList<Comparable>();
final LinkedList<Comparable> right = new LinkedList<Comparable>();
// boolean used to decide if we put elements
// in left or right LinkedList
boolean logicalSwitch = true;
while (!input.isEmpty()) {
if (logicalSwitch) {
left.add(input.pop());
} else {
right.add(input.pop());
}
logicalSwitch = !logicalSwitch;
}
mergeSort(left);
mergeSort(right);
input.addAll(merge(left, right));
}
}
}
我使用 Deque
因为 peek()
/ pop()
比 get(0)
和 remove(0)
更漂亮恕我直言,但这取决于您。如果你绝对想使用 ArrayList
这里遵循相应的实现。
import java.util.ArrayList;
import java.util.List;
public class Example {
private List<Comparable> merge(final List<Comparable> left, final List<Comparable> right) {
final List<Comparable> merged = new ArrayList<>();
while (!left.isEmpty() && !right.isEmpty()) {
if (left.get(0).compareTo(right.get(0)) <= 0) {
merged.add(left.remove(0));
} else {
merged.add(right.remove(0));
}
}
merged.addAll(left);
merged.addAll(right);
return merged;
}
public void mergeSort(final List<Comparable> input) {
if (input.size() != 1) {
final List<Comparable> left = new ArrayList<Comparable>();
final List<Comparable> right = new ArrayList<Comparable>();
boolean logicalSwitch = true;
while (!input.isEmpty()) {
if (logicalSwitch) {
left.add(input.remove(0));
} else {
right.add(input.remove(0));
}
logicalSwitch = !logicalSwitch;
}
mergeSort(left);
mergeSort(right);
input.addAll(merge(left, right));
}
}
}
这两种实现都适用于 Integer
和 String
或其他 Comparable
。
希望对您有所帮助。
如果您想使用合并排序对数组进行排序,而不是自己实现排序算法,
我建议使用标准 Java 排序算法,因为它为非基本类型实现了“Merge sort”算法。
Collections.sort();
如果您想实现自己的归并排序版本,那么您应该首先查看 this implementation。
如果您有兴趣更好地理解排序算法,我推荐 this book。
有几个问题,但一个重要的问题是您不应该在修改列表时迭代列表,即在:
for (i = 0; i < a.size() - mid; i++){
left.add(i,a.get(i));
a.remove(i);
}
因为一旦你删除了一个元素,其他元素的索引就不一样了...所以你添加了 a
的 left
个元素,这与你想的不一样。
工作代码如下(带有一些注释):
private static void merge(ArrayList<Comparable> a) {
if (a.size()<=1) return; // small list don't need to be merged
// SEPARATE
int mid = a.size()/2; // estimate half the size
ArrayList<Comparable> left = new ArrayList<Comparable>();
ArrayList<Comparable> right = new ArrayList<Comparable>();
for(int i = 0; i < mid; i++) left.add(a.remove(0)); // put first half part in left
while (a.size()!=0) right.add(a.remove(0)); // put the remainings in right
// Here a is now empty
// MERGE PARTS INDEPENDANTLY
merge(left); // merge the left part
merge(right); // merge the right part
// MERGE PARTS
// while there is something in the two lists
while (left.size()!=0 && right.size()!=0) {
// compare both heads, add the lesser into the result and remove it from its list
if (left.get(0).compareTo(right.get(0))<0) a.add(left.remove(0));
else a.add(right.remove(0));
}
// fill the result with what remains in left OR right (both can't contains elements)
while(left.size()!=0) a.add(left.remove(0));
while(right.size()!=0) a.add(right.remove(0));
}
已经在一些输入上进行了测试...示例:
[4, 7, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11]
[0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
为了提高效率,您可以使用 subList
方法来避免显式构建太多子列表,它需要注意索引。
有关 Kraal 实现的警告已打勾。这是一个很好的实现,但是 Kraal 的合并排序不会保留具有相同值的项目的相对顺序,在某些情况下,例如在对对象进行排序时,这是合并排序具有其他排序算法(如快速排序)的重要优势, 没有。我修改了 Kraal 的代码以保留相对顺序。
private static List<Object> merge(final List<Object> left, final List<Object> right) {
printArr("left", left);
printArr("Right", right);
final List<Object> merged = new ArrayList<>();
while (!left.isEmpty() && !right.isEmpty()) {
if(left.get(0).getValue()-right.get(0).getValue() <= 0){
merged.add(left.remove(0));
} else {
merged.add(right.remove(0));
}
}
merged.addAll(left);
merged.addAll(right);
return merged;
}
public static void mergeSort(final List<Object> input) {
if (input.size() > 1) {
final List<Object> left = new ArrayList<Object>();
final List<Object> right = new ArrayList<Object>();
boolean logicalSwitch = true;
while (!input.isEmpty()) {
if (logicalSwitch) {
left.add(input.remove(0));
} else {
right.add(input.remove(input.size()/2));
}
logicalSwitch = !logicalSwitch;
}
mergeSort(left);
mergeSort(right);
input.addAll(merge(left, right));
}
}
public class MergeSort{
public void sort(List<Integer> list){
sortAndMerge(list, 0, list.size()-1);
}
public void sortAndMerge(List<Integer> list, int start, int end){
if((end - start) >= 2){
int mid = (end - start)/2;
sortAndMerge(list, start, start + mid);
sortAndMerge(list, start + mid +1, end);
int i=start;
int j=start + mid +1;
while(i<j && j<=end){
if(list.get(i) > list.get(j)){
list.add(i, list.remove(j));
i++;
j++;
}else if(list.get(i) == list.get(j)){
list.add(i+1, list.remove(j));
i++;
j++;
}else{
i++;
}
}
}else{
if(end > start){
if(list.get(start) > list.get(end)){
int endValue = list.remove(end);
list.add(start, endValue);
}
}
}
}
我的合并排序函数一直有问题,因为我无法在将一系列整数或字符串输入程序时对其进行排序。我有一个外部 class 将项目调用到其中,但它根本不对 numbers/strings 进行排序。两种方法如下,不知道问题出在哪里。数字随机输入
代码:
/**
* Takes in entire vector, but will merge the following sections together:
* Left sublist from a[first]..a[mid], right sublist from a[mid+1]..a[last].
* Precondition: each sublist is already in ascending order
*
* @param a
* reference to an array of integers to be sorted
* @param first
* starting index of range of values to be sorted
* @param mid
* midpoint index of range of values to be sorted
* @param last
* last index of range of values to be sorted
*/
private void merge(ArrayList<Comparable> a, int first, int mid, int last) {
int x;
int i;
ArrayList<Comparable> left = new ArrayList<Comparable>();
ArrayList<Comparable> right = new ArrayList<Comparable>();
mergeSort(a,first,mid);
for(i = 0; i < a.size() - mid; i++){
left.add(i,a.get(i));
a.remove(i);
}
mergeSort(a,mid,last);
for (x = mid; x < a.size(); x++) {
right.add(x,a.get(x));
a.remove(x);
}
if ((left.get(i).compareTo(right.get(x))) > 0) {
i++;
a.add(i);
} else if (i < x) {
x++;
a.add(x);
}
System.out.println();
System.out.println("Merge");
System.out.println();
}
/**
* Recursive mergesort of an array of integers
*
* @param a
* reference to an array of integers to be sorted
* @param first
* starting index of range of values to be sorted
* @param last
* ending index of range of values to be sorted
*/
public void mergeSort(ArrayList<Comparable> a, int first, int last) {
int mid = (first + last)/2;
if(first == last){
}else if(last - first == 1){
merge(a,first, mid ,last);
}else{
last = mid;
}
}
I have an outside class that calls items into it, however it simply doesn't sort the numbers/strings. The two methods are below, I don't know where the problem is.
第一个问题是,如果您使用 first = 0
和 last = a.size()
调用 mergeSort
方法,您将不会对任何内容进行排序,因为如果 last-first == 1
:
public void mergeSort(ArrayList<Comparable> a, int first, int last) {
int mid = (first + last)/2;
if(first == last){
}else if(last - first == 1){
// you only merge if last - first == 1...
merge(a,first, mid ,last);
}else{
last = mid;
}
}
从这一点来看,我不明白你是如何尝试实现合并排序算法的。它既不是自上而下,也不是自下而上的实现。你在 merge 方法中分裂,这也很奇怪。如果您提供了伪代码 + 调用 public
方法的方式,那么帮助您会更容易。恕我直言,您的算法确实存在问题。
事实上归并排序算法实现起来非常简单。为了说明这一点,我使用 Deque
而不是 List
对象编写了 top down implementation of the merge sort algorithm:
import java.util.Deque;
import java.util.LinkedList;
public class Example {
private LinkedList<Comparable> merge(final Deque<Comparable> left, final Deque<Comparable> right) {
final LinkedList<Comparable> merged = new LinkedList<>();
while (!left.isEmpty() && !right.isEmpty()) {
if (left.peek().compareTo(right.peek()) <= 0) {
merged.add(left.pop());
} else {
merged.add(right.pop());
}
}
merged.addAll(left);
merged.addAll(right);
return merged;
}
public void mergeSort(final LinkedList<Comparable> input) {
if (input.size() != 1) {
final LinkedList<Comparable> left = new LinkedList<Comparable>();
final LinkedList<Comparable> right = new LinkedList<Comparable>();
// boolean used to decide if we put elements
// in left or right LinkedList
boolean logicalSwitch = true;
while (!input.isEmpty()) {
if (logicalSwitch) {
left.add(input.pop());
} else {
right.add(input.pop());
}
logicalSwitch = !logicalSwitch;
}
mergeSort(left);
mergeSort(right);
input.addAll(merge(left, right));
}
}
}
我使用 Deque
因为 peek()
/ pop()
比 get(0)
和 remove(0)
更漂亮恕我直言,但这取决于您。如果你绝对想使用 ArrayList
这里遵循相应的实现。
import java.util.ArrayList;
import java.util.List;
public class Example {
private List<Comparable> merge(final List<Comparable> left, final List<Comparable> right) {
final List<Comparable> merged = new ArrayList<>();
while (!left.isEmpty() && !right.isEmpty()) {
if (left.get(0).compareTo(right.get(0)) <= 0) {
merged.add(left.remove(0));
} else {
merged.add(right.remove(0));
}
}
merged.addAll(left);
merged.addAll(right);
return merged;
}
public void mergeSort(final List<Comparable> input) {
if (input.size() != 1) {
final List<Comparable> left = new ArrayList<Comparable>();
final List<Comparable> right = new ArrayList<Comparable>();
boolean logicalSwitch = true;
while (!input.isEmpty()) {
if (logicalSwitch) {
left.add(input.remove(0));
} else {
right.add(input.remove(0));
}
logicalSwitch = !logicalSwitch;
}
mergeSort(left);
mergeSort(right);
input.addAll(merge(left, right));
}
}
}
这两种实现都适用于 Integer
和 String
或其他 Comparable
。
希望对您有所帮助。
如果您想使用合并排序对数组进行排序,而不是自己实现排序算法, 我建议使用标准 Java 排序算法,因为它为非基本类型实现了“Merge sort”算法。
Collections.sort();
如果您想实现自己的归并排序版本,那么您应该首先查看 this implementation。
如果您有兴趣更好地理解排序算法,我推荐 this book。
有几个问题,但一个重要的问题是您不应该在修改列表时迭代列表,即在:
for (i = 0; i < a.size() - mid; i++){
left.add(i,a.get(i));
a.remove(i);
}
因为一旦你删除了一个元素,其他元素的索引就不一样了...所以你添加了 a
的 left
个元素,这与你想的不一样。
工作代码如下(带有一些注释):
private static void merge(ArrayList<Comparable> a) {
if (a.size()<=1) return; // small list don't need to be merged
// SEPARATE
int mid = a.size()/2; // estimate half the size
ArrayList<Comparable> left = new ArrayList<Comparable>();
ArrayList<Comparable> right = new ArrayList<Comparable>();
for(int i = 0; i < mid; i++) left.add(a.remove(0)); // put first half part in left
while (a.size()!=0) right.add(a.remove(0)); // put the remainings in right
// Here a is now empty
// MERGE PARTS INDEPENDANTLY
merge(left); // merge the left part
merge(right); // merge the right part
// MERGE PARTS
// while there is something in the two lists
while (left.size()!=0 && right.size()!=0) {
// compare both heads, add the lesser into the result and remove it from its list
if (left.get(0).compareTo(right.get(0))<0) a.add(left.remove(0));
else a.add(right.remove(0));
}
// fill the result with what remains in left OR right (both can't contains elements)
while(left.size()!=0) a.add(left.remove(0));
while(right.size()!=0) a.add(right.remove(0));
}
已经在一些输入上进行了测试...示例:
[4, 7, 1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11]
[0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
为了提高效率,您可以使用 subList
方法来避免显式构建太多子列表,它需要注意索引。
有关 Kraal 实现的警告已打勾。这是一个很好的实现,但是 Kraal 的合并排序不会保留具有相同值的项目的相对顺序,在某些情况下,例如在对对象进行排序时,这是合并排序具有其他排序算法(如快速排序)的重要优势, 没有。我修改了 Kraal 的代码以保留相对顺序。
private static List<Object> merge(final List<Object> left, final List<Object> right) {
printArr("left", left);
printArr("Right", right);
final List<Object> merged = new ArrayList<>();
while (!left.isEmpty() && !right.isEmpty()) {
if(left.get(0).getValue()-right.get(0).getValue() <= 0){
merged.add(left.remove(0));
} else {
merged.add(right.remove(0));
}
}
merged.addAll(left);
merged.addAll(right);
return merged;
}
public static void mergeSort(final List<Object> input) {
if (input.size() > 1) {
final List<Object> left = new ArrayList<Object>();
final List<Object> right = new ArrayList<Object>();
boolean logicalSwitch = true;
while (!input.isEmpty()) {
if (logicalSwitch) {
left.add(input.remove(0));
} else {
right.add(input.remove(input.size()/2));
}
logicalSwitch = !logicalSwitch;
}
mergeSort(left);
mergeSort(right);
input.addAll(merge(left, right));
}
}
public class MergeSort{
public void sort(List<Integer> list){
sortAndMerge(list, 0, list.size()-1);
}
public void sortAndMerge(List<Integer> list, int start, int end){
if((end - start) >= 2){
int mid = (end - start)/2;
sortAndMerge(list, start, start + mid);
sortAndMerge(list, start + mid +1, end);
int i=start;
int j=start + mid +1;
while(i<j && j<=end){
if(list.get(i) > list.get(j)){
list.add(i, list.remove(j));
i++;
j++;
}else if(list.get(i) == list.get(j)){
list.add(i+1, list.remove(j));
i++;
j++;
}else{
i++;
}
}
}else{
if(end > start){
if(list.get(start) > list.get(end)){
int endValue = list.remove(end);
list.add(start, endValue);
}
}
}
}