排序算法之归并排序及Java实现

忘是亡心i 2022-05-26 04:07 159阅读 0赞

## 一、排序算法的分类 ##

1.  选择排序（[直接选择排序][Link 1]，[堆排序][Link 2]）
2.  交换排序（[冒泡排序][Link 3]，[快速排序][Link 4]）
3.  插入排序（[直接插入排序][Link 5]，[希尔排序][Link 6]）
4.  [归并排序][Link 7]
5.  桶式排序
6.  基数排序

## 二、归并排序的原理 ##

归并排序利用的是分治的思想实现的，对于给定的一组数据，利用递归与分治技术将数据序列划分成为越来越小的子序列，之后对子序列排序，最后再用递归方法将排好序的子序列合并成为有序序列。合并两个子序列时，需要申请两个子序列加起来长度的内存，临时存储新的生成序列，再将新生成的序列赋值到原数组相应的位置。

## 三、归并排序的实现 ##

public class MergeSort {
        
    
        public static void merSort(int[] arr,int left,int right){
    
            if(left<right){
                int mid = (left+right)/2;
                merSort(arr,left,mid);//左边归并排序，使得左子序列有序
                merSort(arr,mid+1,right);//右边归并排序，使得右子序列有序
                merge(arr,left,mid,right);//合并两个子序列
            }
        }
        private static void merge(int[] arr, int left, int mid, int right) {
            int[] temp = new int[right - left + 1];//ps：也可以从开始就申请一个与原数组大小相同的数组，因为重复new数组会频繁申请内存
            int i = left;
            int j = mid+1;
            int k = 0;
            while(i<=mid&&j<=right){
                if (arr[i] < arr[j]) {
                    temp[k++] = arr[i++];
                } else {
                    temp[k++] = arr[j++];
                }
            }
            while(i<=mid){
       //将左边剩余元素填充进temp中
                temp[k++] = arr[i++];
            }
            while(j<=right){
       //将右序列剩余元素填充进temp中
                temp[k++] = arr[j++];
            }
            //将temp中的元素全部拷贝到原数组中
            for (int k2 = 0; k2 < temp.length; k2++) {
                arr[k2 + left] = temp[k2];
            }
        }
        public static void main(String args[]){
            int[] test = {
       9,2,6,3,5,7,10,11,12};
            merSort(test,0,test.length-1);
            for(int i=0; i<test.length;i++){
                System.out.print(test[i] + " ");
            }
        }
    
    }

测试结果

2 3 5 6 7 9 10 11 12

[Link 1]: https://blog.csdn.net/xdzhouxin/article/details/80017538
[Link 2]: https://blog.csdn.net/xdzhouxin/article/details/80079195
[Link 3]: https://blog.csdn.net/xdzhouxin/article/details/80017719
[Link 4]: https://blog.csdn.net/xdzhouxin/article/details/80031668
[Link 5]: https://blog.csdn.net/xdzhouxin/article/details/80024190
[Link 6]: https://blog.csdn.net/xdzhouxin/article/details/80070031
[Link 7]: https://blog.csdn.net/xdzhouxin/article/details/80070839