排序算法--Java版（插入排序和希尔排序）

约定不等于承诺〃 2022-03-14 14:54 88阅读 0赞

插入排序：

*  从第一个元素开始，该元素可以认为已经被排序；
 *  取出下一个元素，在已经排序的元素序列中从后向前扫描；
 *  如果该元素（已排序）大于新元素，将该元素移到下一位置；
 *  重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
 *  将新元素插入到该位置后；
 *  重复步骤2~5。

希尔排序：

*  选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
 *  按增量序列个数k，对序列进行k 趟排序；
 *  每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

public class Main {
    
        public static void main(String[] args) {
            int[] list2={5,2,4,6,3,1};
            int[] newList2 =InsertionSort(list2);
            System.out.println(Arrays.toString(newList2));
            int[] list3={5,2,4,6,3,1};
            int[] newList3 =ShellSort(list3);
            System.out.println(Arrays.toString(newList3));
        }
    
        /**
         * 插入排序
         * @param list
         * @return
         */
        static int[] InsertionSort(int[] list){
            int index = 0;
            int temp = 0;
            for (int i=1;i<list.length;i++){
                index=i;
                temp=list[i];
                //因为前面的都是排好序的所以当temp>=list[index-1]时即可插入
                while (index>0 && temp<list[index-1]){
                    //大于第i个值的往后让一位
                    list[index]=list[index-1];
                    //记录index位置
                    index--;
                }
                //插入第i个值
                list[index]=temp;
            }
            return list;
        }
    
        /**
         * 希尔排序
         * @param list
         * @return
         */
        static int[] ShellSort(int[] list){
            int index = 0;
            int temp = 0;
            //增量
            int incrementNum = list.length/2;
            while (incrementNum>=1){
                for (int i=0;i<incrementNum;i++){
                    for (int j=i+incrementNum;j<list.length;j=j+incrementNum){
                        index=j-incrementNum;
                        temp=list[j];
                        while (index>=0 && temp<list[index]){
                            //大于第i个值的往后让incrementNum位
                            list[index+incrementNum]=list[index];
                            //记录index位置
                            index=index-incrementNum;
                        }
                        //插入第i个值
                        list[index+incrementNum]=temp;
                    }
                }
                //缩小增量
                incrementNum=(int) Math.ceil(incrementNum/2);
            }
            return list;
        }
    }