java排序--归并排序

谁践踏了优雅 2022-09-20 05:48 204阅读 0赞

**1.概念:**

**归并（Merge）**[**排序**][Link 1]**法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。**

归并 [排序][Link 1] 是建立在归并操作上的一种有效的 [排序][Link 1] 算法。该算法是采用 [分治法][Link 2] （Divide and Conquer）的一个非常典型的应用。值得注意的是归并排序是一种 [稳定][Link 3] 的排序方法。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序 [表][Link 4] ，称为二路 [归并][Link 5]。

**2.归并操作:**

归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。

如　设有数列\{6，202，100，301，38，8，1\}

初始状态：6,202,100,301,38,8，1

第一次归并后：\{6,202\},\{100,301\},\{8,38\},\{1\}，比较次数：3；

第二次归并后：\{6,100,202,301\}，\{1,8,38\}，比较次数：4；

第三次归并后：\{1,6,8,38,100,202,301\},比较次数：4；

总的比较次数为：3+4+4=11,；

逆序数为14；

**3.示例代码:**

**//排序器**

/\*\*

\* 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换)

\*/

public interface Sorter \{

/\*\*

\* 排序

\* @param list 待排序的数组

\*/

public <T extends Comparable<T>> void sort(T\[\] list);

/\*\*

\* 排序

\* @param list 待排序的数组

\* @param comp 比较两个对象的比较器

\*/

public <T> void sort(T\[\] list, Comparator<T> comp);

public class MergeSorter implements Sorter \{

@Override

public <T extends Comparable<T>> void sort(T\[\] list) \{

T\[\] temp = (T\[\]) new Comparable\[list.length\];

mSort(list, temp, 0, list.length - 1);

private <T extends Comparable<T>> void mSort(T\[\] list, T\[\] temp, int low, int high) \{

if(low == high) \{

return ;

else \{

int mid = low + ((high - low) >> 1);

mSort(list, temp, low, mid);

mSort(list, temp, mid + 1, high);

merge(list, temp, low, mid + 1, high);

private <T extends Comparable<T>> void merge(T\[\] list, T\[\] temp, int left, int right, int last) \{

int j = 0;

int lowIndex = left;

int mid = right - 1;

int n = last - lowIndex + 1;

while (left <= mid && right <= last) \{

if (list\[left\].compareTo(list\[right\]) < 0) \{

temp\[j++\] = list\[left++\];

\} else \{

temp\[j++\] = list\[right++\];

while (left <= mid) \{

temp\[j++\] = list\[left++\];

while (right <= last) \{

temp\[j++\] = list\[right++\];

for (j = 0; j < n; j++) \{

list\[lowIndex + j\] = temp\[j\];

@Override

public <T> void sort(T\[\] list, Comparator<T> comp) \{

T\[\] temp = (T\[\]) new Comparable\[list.length\];

mSort(list, temp, 0, list.length - 1, comp);

private <T> void mSort(T\[\] list, T\[\] temp, int low, int high, Comparator<T> comp) \{

if(low == high) \{

return ;

else \{

int mid = low + ((high - low) >> 1);

mSort(list, temp, low, mid, comp);

mSort(list, temp, mid + 1, high, comp);

merge(list, temp, low, mid + 1, high, comp);

private <T> void merge(T\[\] list, T\[\] temp, int left, int right, int last, Comparator<T> comp) \{

int j = 0;

int lowIndex = left;

int mid = right - 1;

int n = last - lowIndex + 1;

while (left <= mid && right <= last) \{

if (comp.compare(list\[left\], list\[right\]) < 0) \{

temp\[j++\] = list\[left++\];

\} else \{

temp\[j++\] = list\[right++\];

while (left <= mid) \{

temp\[j++\] = list\[left++\];

while (right <= last) \{

temp\[j++\] = list\[right++\];

for (j = 0; j < n; j++) \{

list\[lowIndex + j\] = temp\[j\];

[Link 1]: http://baike.baidu.com/view/58783.htm
[Link 2]: http://baike.baidu.com/view/1583824.htm
[Link 3]: http://baike.baidu.com/view/309421.htm
[Link 4]: http://baike.baidu.com/view/24860.htm
[Link 5]: http://baike.baidu.com/view/711818.htm

java排序--归并排序

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关【排序】归并排序

相关 java排序--归并排序

相关归并排序 Java

相关【排序】归并排序

相关排序-归并排序-Java

相关归并排序java

相关归并类排序-----归并排序

相关 Java归并排序

相关【Java】归并排序

相关 java归并排序