排序--归并排序

             1
            /**
             2
             *归并排序的原理Demo：

             3
             * 1，申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

             4
             * 2， 设定两个指针，最初位置分别为两个已经排序序列的起始位置

             5
             * 3， 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

             6
             * 4，重复步骤3直到某一指针达到序列尾

             7
             * 5，将另一序列剩下的所有元素直接复制到合并序列尾 

             8
             *

             9
            */
            10
            public
            class
             Merge

            11
            {

            12
            13
            public
            static
            int[] mergeSort(int[] A,int[] B){
14//申请空间，大小等于2个已经排序的数列之和15int[] C = newint[A.length+B.length];
16//指针i，j分别指向2个数列的起始位置。17int i=0,j=0,k=0;
18//比较2个指针所指向的元素，将较小的元素放入到合并空间，并移动指针。19while(i<A.length && j<B.length){
20if(A[i] < B[j])
21                 C[k++] = A[i++];
22else23                 C[k++] = B[j++];
24        }
25//将另一个序列的元素全部复制到合并空间尾部
26//以下2个while只会执行其中一个27while(i<A.length){
28             C[k++] = A[i++];
29        }
30while(j<B.length){
31             C[k++] = B[j++];
32        }
33return C;
34    }
35publicstaticvoid main(String[] args)
36    {
37int[] A = {1,3,5,7,9,11};
38int[] B = {2,4,6,8,10,12};
39int[] C =mergeSort(A, B);
40for(int i: C)
41        {
42             System.out.print(i+" ");
43        }
44    }
45 }

             1
            public
            class
             Merge

             2
            {

             3
             4
            public
            static
            void
             main(String[] args)

             5
                {

             6         Integer[] arr = {5,3,4,6,3,1,4,6,5,36,5,44,22,88,99,5,555,3335,64,544,22333};
 7        merge(arr);
 8for(Integer i: arr)
 9        {
10             System.out.print(i + " ");
11        }
12    }
1314     @SuppressWarnings("unchecked")
15privatestatic <T extends Comparable<? super T>> void merge(T[] arr)
16    {
17         T[] temArr = (T[])new Comparable[arr.length];
18         mergeSort(arr, temArr, 0, arr.length - 1);
19    }
2021privatestatic <T extends Comparable<? super T>> void mergeSort(T[] arr, T[] temArr, int left, int right)
22    {
23if(left < right)
24         {//递归25int center = (left + right) / 2;
26            mergeSort(arr, temArr, left, center);
27             mergeSort(arr, temArr, center + 1, right);
28             merge(arr, temArr, left, center + 1, right);
29        }
30    }
3132privatestatic <T extends Comparable<? super T>> void merge(T[] arr, T[] temArr, int leftPos, int rightPos, int rightEnd)
33    {
34// 左边数列的最大索引35int leftEnd = rightPos - 1;
36// 合并空间的起始索引37int temPos = leftPos;
38// 用于复制最终数组用的左边数列的起始指针39int temLeft = leftPos;
40// 比较2个指针所指的元素的大小，将小的赋值给临时空间对应的位置。指针移动一个位置，继续比较。直到一个数列结尾。41while(leftPos <= leftEnd && rightPos <= rightEnd)
42        {
43if(arr[leftPos].compareTo(arr[rightPos]) <= 0)
44            {
45                 temArr[temPos++] = arr[leftPos++];
46            }
47else48            {
49                 temArr[temPos++] = arr[rightPos++];
50            }
51        }
52// 将另外一个数列全部复制到临时空间53while(leftPos <= leftEnd)
54        {
55             temArr[temPos++] = arr[leftPos++];
56        }
57while(rightPos <= rightEnd)
58        {
59             temArr[temPos++] = arr[rightPos++];
60        }
61// 将临时空间的值复制到对应位置的原来数组62for(int i = temLeft; i <= rightEnd; i++)
63        {
64             arr[i] = temArr[i];
65        }
66    }
67 }