排序算法的实现

用java对常用内部排序算法的实现。

对冒泡排序，简单选择排序，直接插入排序，希尔排序，归并排序的简单实现（缺少快速排序和堆排序，改天补充），只是对其排序原理的理解，并没有做算法的优化。

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。

        // 冒泡排序。设置标志位，当某一次排序没有发生交换时表示当前序列已经有序。
        private static int[] BubbleSort(int[] is) {
            for (int i = 0; i < is.length; i++) {
                boolean isChanged = true;
                for (int j = i + 1; j < is.length; j++) {
                    if (is[i] > is[j]) {
                        int tmp = is[i];
                        is[i] = is[j];
                        is[j] = tmp;
                        isChanged = false;
                    }
                }
                if (isChanged == true)
                    break;
            }
            return is;
        }

简单选择排序

选择排序是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

//简单选择排序。设置标志位，当某一次排序没有发生交换时表示当前序列已经有序。
        private static int[] SelectSort(int[] is){
            for(int i=0;i<is.length;i++){
                boolean isChanged = true;
                for(int j=i+1;j<is.length;j++){
                    if(is[j]<is[i]){
                        int tmp=is[i];
                        is[i]=is[j];
                        is[j]=tmp;
                        isChanged = false;
                    }
                }
                if(isChanged == true)
                    break;
            }
            return is;
        }

直接插入排序

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

//直接插入排序。设置标志位，当某一次排序没有发生交换时表示当前序列已经有序。
        private static int[] InsertionSort(int[] is){
            for(int i=1;i<is.length;i++){
                boolean isChanged=true;
                for(int j=i;j>0;j--){
                    if(is[j]<is[j-1]){
                        int tmp = is[j];
                        is[j] = is[j-1];
                        is[j-1] = tmp;
                        isChanged = false;
                    }
                }
                if (isChanged == true)
                    break;
            }
            return is;
        }

希尔排序

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

//希尔排序。
        private static int[] ShellSort(int[] is){       
            for(int step=is.length/2;step>0;step=step/2){//设置排序的步长，默认都是从n/2开始
                //直接插入排序
                for(int j=0;j<step;j++){
                    for(int k=j+step;k<is.length;k+=step){
                        if(is[k]<is[k-step]){
                            int tmp = is[k];
                            int t=k-step;
                            while(t>=0&&is[t]>tmp){
                                is[t+step]=is[t];
                                t-=step;
                            }
                            is[t+step] = tmp;
                        }
                    }
                }
            }
            return is;
        }

归并排序

归并排序，是创建在归并操作上的一种有效的排序算法。

        //归并排序,采用递归方式
        private static int[] MergeSort(int[] is){
            if(is.length==1){
                return is;
            }
            int half=is.length/2;
            int[] ary1=new int[half];
            int[] ary2=new int[is.length-half];
            System.arraycopy(is, 0, ary1, 0, ary1.length);
            System.arraycopy(is, half, ary2, 0, ary2.length);
            ary1=MergeSort(ary1);
            ary2=MergeSort(ary2);
            return Merge(ary1, ary2);
        }
        //合并两个有序数组，并且合并后的数组也有顺序
        private static int[] Merge(int[] A,int[] B){
            int[] tmp=new int[A.length+B.length];
            int i=0,j=0,k=0;
            while(i<A.length&&j<B.length){
                if(A[i]<B[j]){
                    tmp[k++]=A[i++];
                }else{
                    tmp[k++]=B[j++];
                }
            }
            
            while(i<A.length){
                tmp[k++]=A[i++];
            }
            while(j<B.length){
                tmp[k++]=B[j++];
            }
            
            return tmp;
        }