Java实现七大排序（一）

目录

一.插入排序

1.直接插入排序

2.希尔排序

二.选择排序

1.选择排序

2.堆排序

三.总结

---

一.插入排序

1.直接插入排序

直接插入排序的原理与线下玩扑克牌类似。我们拿到一张牌后要排序，方法就是一张一张对。直接插入排序也是这样的，我们得到一张“牌”，从后往前对比，如果“牌”比刚得到的“牌”大就继续往前找，如果“牌”比刚得到的要小就插在它的后面。

//直接插入排序
    public static void insetSort(int[] array){
        for(int i=1;i<array.length;i++){
            //从前往后遍历
            int j=i-1;
            int tem=array[i];   //当前i的值
            for(;j>=0;j--){
                if(array[j]>tem){
                    //如果比tem大就继续往前找
                    array[j+1]=array[j];
                }else{
                    //如果比tem小就插在j的后面，也就是j+1的位置
                    array[j+1]=tem;
                    break;
                }
            }
            //如果找到头都没找到，说明其实最小的
            array[j+1]=tem;
        }
    }

特性：当数组越有序，时间效率越高。

2.希尔排序

又名缩小增量排序。希尔排序是直接插入排序的优化，其时间复杂度最坏就是直接插入排序。思路是先分小组，组内排序；再分组，但组内元素增多，组内排序，直到最后只分1组，这时再进行排序就有序了。

首先我们要解决这么分组的问题。

如图，正常我们想到的是第一种分组，将连续的几个元素分成一组。但希尔排序用的是第二种，定义一个gap，让前一个加上一个gap找到第二个。

前面说了希尔排序是直接插入排序的优化，其代码和直接插入排序极其相似。

    //希尔排序
    public static void shellSort(int[] array){
        int gap=array.length/2;
        //分组
        while(gap>1){
            gap=gap/2;
            shell(array,gap);
        }
    }
    //直接插入排序的变种
    private static void shell(int[] array, int gap) {
        for(int i=gap;i<array.length;i++){
            int j=i-gap;
            int tem=array[i];
            for(;j>=0;j-=gap){
                if(array[j]>array[j+gap]){
                    array[j+gap]=array[j];
                }else{
                    array[j+gap]=tem;
                    break;
                }
            }
            array[j+gap]=tem;
        }
    }

二.选择排序

1.选择排序

选择排序的原理很简单，从前到后遍历每一个元素，再遍历这个元素后面的元素，找到后面比该元素更小的元素，交换其位置即可。

 public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int mindIndex = i;
            for (int j = i+1; j < array.length; j++) {
                if(array[j] < array[mindIndex]) {
                    mindIndex = j;
                }
            }
            swap(array,i,mindIndex);
        }
    }

这种方式排序比较慢，我们可以对其进行优化，优化思路：同时排序大值和小值。

public static void SelectSortOptimize(int[] array){
        int left=0;
        int right=array.length-1;
 
        while(left<right){
            int minIndex=left;
            int maxIndex=left;
 
            for (int i = left+1; i <= right; i++) {
                if(array[i]>array[maxIndex]){
                    maxIndex=i;
                }
                if(array[i]<array[minIndex]){
                    minIndex=i;
                }
            }
 
            swap(array,left,minIndex);
            if(maxIndex==left){
                //因为left已经被minIndex换走了
                maxIndex=minIndex;
            }
            swap(array,right,maxIndex);
            left++;
            right--;
        }
    }

2.堆排序

在堆排序中，要想升序排序要大根堆，要降序需要小根堆。思路：定义一个引用指向堆的最后一个元素，将堆顶元素与指向元素交换，然后指向向前移动，将堆顶元素进行向下调整。

public static void heapSort(int[] array){
        createHeap(array);
        for(int i=array.length-1;i>0;i--){
            swap(array,0,i);
            siftdown(array,0,i);
        }
    }

三.总结