数据结构-归并排序

[ Compare类见前面冒泡查找 ]

```package com.algorithm.sorting;

import java.util.ArrayList;
import java.util.List;
import com.algorithm.utils.Compare;

/*
* Merge sortting 归并排序
* time:O(N*logN)
*/
public class Merge<E> {
/*
*  sort array
*/
public void sort(E list[]) {
divide(list, 0, list.length - 1);
}

public void divide(E list[], int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
divide(list, left, mid);// sort left
divide(list, mid + 1, right);// sort right
merge(list, left, mid, right);// merge
}
}

public void merge(E list[], int leftstart, int mid, int rightend) {
Compare compare = new Compare();
int start = leftstart;//必须单独记住开始下标 start
int leftend = mid;
int rightstart = mid + 1;
int k = 0;
int size = rightend - leftstart + 1;
E[] temp = (E[]) new Object[size];
while (leftstart <= leftend && rightstart <= rightend) {
if (compare.compare(list[leftstart], list[rightstart]) < 0) {
temp[k++] = list[leftstart++];
} else {
temp[k++] = list[rightstart++];
}

}

while (leftstart <= leftend) {
temp[k++] = list[leftstart++];
}
while (rightstart <= rightend) {
temp[k++] = list[rightstart++];
}

/*
* copy temp array back to list attention
* 必须单独记住开始下标 start
*/

for (int i = 0; i < temp.length; i++) {
list[start + i] = temp[i];
}

}

/*
*  sort colllection
*/
public List<E> sort(List<E> list) {
return divide(list, 0, list.size() - 1);
}

public List<E> divide(List<E> list, int left, int right) {
if (left < right) {
int mid = (left + right) / 2;
divide(list, left, mid);
divide(list, mid + 1, right);
merge(list, left, mid, right);
}
return list;
}

public void merge(List<E> list, int leftstart, int mid, int rightend) {
Compare compare = new Compare();
int start = leftstart;
int leftend = mid;
int rightstart = mid + 1;
int k = 0;
List<E> temp = new ArrayList<E>();
while (leftstart <= leftend && rightstart <= rightend) {
if (compare.compare(list.get(leftstart), list.get(rightstart)) <= 0) {
} else {
}
}

while (leftstart <= leftend) {
}

while (rightstart <= rightend) {
}
/*
* 因为集合的数据如果超出容量的话，集合会自动扩容，添加在尾部。
* 所以应该采用set方法，修改数据，达到交换数据的目的。
*/

for (int i = 0; i < temp.size(); i++) {
list.set(start + i, temp.get(i));
}
}

}
//该片段来自于http://outofmemory.cn
```

0人收藏

0

0