Shulou(Shulou.com)06/03 Report--

This article introduces the relevant knowledge of "how to use the merge sorting algorithm". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

The idea of merging sorting algorithm

To sort an array, you can first divide the array into two arrays and sort them separately, then merge the results together and repeat the recursive process until the array is ordered as a whole.

The advantage of merge sorting is that it can ensure that the time required for sorting arrays of arbitrary length N is proportional to NlogN, which can not be achieved by primary sorting.

The disadvantage is that the merge operation requires the introduction of additional arrays, and the extra space is proportional to N

Realization of in-situ merger

Before implementing merge sorting, we need to complete the merge operation of two ordered arrays, that is, two ordered numbers are combined into an ordered array.

In the process, we need to introduce an auxiliary array

The defined method signature is merge (a, lo, mid, hi), which merges the array a [lo..mid] and a [mid..hi] into an ordered array, and stores the results in a [lo.mid].

The common function less in the previous article, which needs to be used in this method, refers to the previous article, "Common primary sorting algorithms, get it all this time".

Public class MergeSort implements SortTemplate {private Comparable [] aux; @ Override public void sort (Comparable [] array) {/ / to be implemented} private void merge (Comparable [] a, int lo, int mid, int hi) {for (int I = lo; i hi) {a [k] = aux [iTunes +] } else if (less (aux [I], Auxu [j])) {a [k] = aux [iTunes +];} else {a [k] = aux [jacks +];}}

Top-down merge sort

Based on the idea of divide and conquer, the sorting of large arrays is first recursively split into small arrays to ensure that the small arrays are ordered and then merged until the whole array is ordered, which is the top-down merge sorting.

Public class MergeSort implements SortTemplate {private Comparable [] aux; @ Override public void sort (Comparable [] array) {aux = new Comparable [array.length]; doSort (array, 0, array.length-1);} private void doSort (Comparable [] array, int lo, int hi) {if (lo > = hi) {return;} int mid = (hi-lo) / 2 + lo DoSort (array, lo, mid); doSort (array, mid + 1, hi); merge (array, lo, mid, hi);} private void merge (Comparable [] a, int lo, int mid, int hi) {/ / omitted}}

The above code is a standard recursive merge sort operation, but after careful consideration, the algorithm still has room for optimization.

"Test whether the array is ordered"; if a [mid] = hi) {return;} int mid = (hi-lo) / 2 + lo; doSort (array, lo, mid); doSort (array, mid + 1, hi); if (array [mid + 1]) > = 0) {merge (array, lo, mid, hi);}}

"insert sort can be used for small arrays"; using merge sort for small arrays will increase the recursive call stack, so we can consider using insert sort to handle the sorting of subarrays.

Private void doSort (Comparable [] array, int lo, int hi) {if (lo > = hi) {return;} if (hi-lo)

< 5) { //测试，小于5就使用插入排序 insertionSort(array, lo, hi); return; } int mid = (hi - lo) / 2 + lo; doSort(array, lo, mid); doSort(array, mid + 1, hi); if (less(array[mid + 1], array[mid])) { merge(array, lo, mid, hi); } } //插入排序 private void insertionSort(Comparable[] array, int lo, int hi) { for (int i = lo; i lo && less(array[j], array[j - 1]); j--) { exch(array, j, j - 1); } } } 「节省复制元素到辅助数组的时间」；要实现该操作较麻烦，需要在每一层递归的时候交换输入数据和输出数组的角色；修改之后的完整代码如下： public class MergeSort implements SortTemplate { private Comparable[] aux; @Override public void sort(Comparable[] array) { aux = array.clone(); doSort(aux, array, 0, array.length - 1); } private void doSort(Comparable[] src, Comparable[] dest, int lo, int hi) { if (lo >

= hi) {return;} if (hi-lo

< 5) { //测试，小于5就使用插入排序 insertionSort(dest, lo, hi); return; } int mid = (hi - lo) / 2 + lo; doSort(dest, src, lo, mid); doSort(dest, src, mid + 1, hi); if (less(src[mid + 1], src[mid])) { merge(src, dest, lo, mid, hi); } } //插入排序 private void insertionSort(Comparable[] array, int lo, int hi) { for (int i = lo; i lo && less(array[j], array[j - 1]); j--) { exch(array, j, j - 1); } } } private void merge(Comparable[] src, Comparable[] dest, int lo, int mid, int hi) { int i = lo, j = mid + 1; for (int k = lo; k mid) { dest[k] = src[j++]; } else if (j >

Hi) {dest [k] = src [iTunes +];} else if (less (src [I], src [j])) {dest [k] = src [iTunes +];} else {dest [k] = src [jacks +];}}

Each layer of recursive operation makes the subarray ordered, but the subarray may be aux [lo..hi] or a [lo..hi]. Since the src=aux,dest=array is passed in the first call to doSort, the final result of recursion must be input to array, ensuring that the overall sorting of array is completed.

Bottom-up merging order

There is another way to realize the merging algorithm, that is, which small arrays are merged first, and then the subarrays are merged in pairs until the whole array is ordered.

Public class MergeSort implements SortTemplate {private Comparable [] aux; @ Override public void sort (Comparable [] array) {int length = array.length; aux = new Comparable [length]; for (int sz = 1; sz < length; sz + = sz) {for (int I = 0; I < length-sz) I + = 2 * sz) {merge (array, I, I + sz-1, Math.min (I + 2 * sz-1, length-1));} private void merge (Comparable [] a, int lo, int mid, int hi) {for (int I = lo; i hi) {a [k] = aux } else if (less (aux [I], auxj]) {a [k] = aux [iSuppli +];} else {a [k] = aux [junk +];}} "how to use the merge sorting algorithm" ends here, thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.