选择排序、插入排序、希尔排序与归并排序

绝地灬酷狼 2022-09-25 13:19 258阅读 0赞

（1）选择排序

public class Sortexample {
        public void exch(int[] a,int i,int j){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        public void selection(int[] a){
            int len = a.length;
            for(int i = 0;i < len;i++){
                int minindex = i;
                for(int j = i + 1;j < len;j++){
                    if(a[minindex] > a[j])
                        minindex = j;
                }
                if(minindex != i){
                    exch(a,i,minindex);
                }
            }
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Sortexample example = new Sortexample();
            int[] a = new int[]{
       1,3,4,2,5,8,7,6};
            example.selection(a);
            for(int i = 0;i < a.length; i++)
                System.out.println(a[i]);
        }
    }

运行轨迹：  
![这里写图片描述][20160910205253988]

（2）插入排序

public class Sortexample {
        public void exch(int[] a,int i,int j){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        public void insertsort(int[] a){
            int len = a.length;
            for(int i = 1; i < len; i++){
                for(int j = i;j > 0;j--){
                    if(a[j] < a[j-1]){
                        exch(a,j-1,j);
                    }
                }
            }
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Sortexample example = new Sortexample();
            int[] a = new int[]{
       1,3,4,2,5,8,7,6};
            example.insertsort(a);
            for(int i = 0;i < a.length; i++)
                System.out.println(a[i]);
        }
    }

运行轨迹如图：  
![这里写图片描述][20160910205332894]  
插入排序对于部分有序的数组十分高效，也很适合小规模的数组

选择排序与插入排序对比：

![这里写图片描述][20160910205442897]  
（3）希尔排序

public class Sortexample {
        public void exch(int[] a,int i,int j){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
        public void shellsort(int[] a){
            int  len = a.length;
            int h = 1;
            while(h < len) h = 3*h+1;
            while(h >= 1){
                for(int i = h;i < len ;i++){
                    for(int j = i;j >= h;j-=h){
                        if(a[j]<a[j-h]){
                            exch(a,j-h,j);
                        }
                    }
                }
                h=h/3;
            }
        }
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Sortexample example = new Sortexample();
            int[] a = new int[]{
       1,3,4,2,5,8,7,6};
            example.shellsort(a);
            for(int i = 0;i < a.length; i++)
                System.out.println(a[i]);
        }
    }

运行轨迹：  
![这里写图片描述][20160910205510725]  
（4）归并排序

自顶向下的归并

public class Sortexample {
        private static int[] aux;//用于归并时存储
        //将两个有序数组进行归并
        public void mergesort(int[] a){
            aux = new int[a.length];
            sort(a,0,a.length-1);
        }
        public void merge(int[]a,int lo,int mid,int hi){
            int i = lo;
            int j = mid + 1;
            for(int k = lo;k <= hi;k++)//注意k与hi可以取等
                aux[k] = a[k];
            for(int k = lo;k <= hi;k++){
                if(i > mid)
                    a[k] = aux[j++];
                else if(j > hi)
                    a[k] =aux[i++];
                else if(aux[j] < aux[i])
                    a[k] = aux[j++];
                else 
                    a[k] = aux[i++];
            }
        }
        public void sort(int[] a,int lo,int hi){
            if(hi<=lo) return;
            int mid = (lo + hi)/2;
            sort(a,lo,mid);
            sort(a,mid+1,hi);
            merge(a,lo,mid,hi);
        }
    
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            Sortexample example = new Sortexample();
            int[] a = new int[]{
       1,3,4,2,5,8,7,6};
            example.mergesort(a);       
            System.out.println(Arrays.toString(a));
        }
    }

![这里写图片描述][20160910205956030]

自底向上的归并排序：

public class MergeBU{
        private static int[] aux;//归并所需的辅助数组
        public static void sort(int[] a){
            int N = a.length;
            aux = new int[N];
            for (int sz=1;sz<N;sz=sz+sz){
                for(int lo=0;lo<N-sz;lo+=sz+sz){
                    merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));//merge方法与自顶向下一致，都是合并两个有序数组
                }
            }
        }
    }

归并排序的优化：用不同的方法处理小规模问题能改进大多数递归算法的性能，因为递归会使小规模问题中方法的调用过于频繁，所以改进对它们的处理方法可以改进整个算法。使用插入排序处理小规模的子数组（比如长度小于15）一般可以将归并排序的运行时间缩短%10-%15.

[20160910205253988]: /images/20220717/f104f955622d4f54b3d5edb21ebd1697.png
[20160910205332894]: /images/20220717/2b851892b14541fdb0c0755cdcb8d5db.png
[20160910205442897]: /images/20220717/241600af11884b1481e0c4267e4ff821.png
[20160910205510725]: /images/20220717/753bec5c1da3452280cc840ed2b63e54.png
[20160910205956030]: /images/20220717/38be1c7877ae4ff8a0d8b96390900704.png