【Java数据结构】---七大排序（插入排序和选择排序）

乐观学习，乐观生活，才能不断前进啊！！！

我的主页：optimistic_chen

我的专栏：c语言 ，Java

欢迎大家访问~
创作不易，大佬们点赞鼓励下吧~

什么是排序？

使一串数据根据大小，递增或递减的排列起来的操作

排序的稳定性：

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若 经过排序，这些记录的 相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前 则称这种排序算法是 稳定的；否则称为不稳定的。

常见的排序分组

插入排序

把 待排序的数据按其关键码值的大小逐个插入到一个已经排好序的 有序序列中，直到所有的数据插入完为止，得到一个 新的有序序列 。

直接插入排序

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

一般情况下，我们排序都是排升序。

此图仅仅展示了必要步骤

public static void insertSort(int[] array){
    for (int i = 1; i < array.length; i++) {
        int tmp=array[i];
        int j = i-1;
        for (; j >=0 ; j--) {
            if (tmp<array[j]){
                array[j+1]=array[j];
            }
            else {
                break;
            }
        }
        array[j+1]=tmp;
    }
}

总结：
· 对于直接插入排序，越有序，排序越快，所以如果一组数据趋于有序时，可以优先选择直接插入排序
· 时间复杂度：O（n^2）
· 空间复杂度：O（1）
· 稳定性：稳定

希尔排序

即分组排序：先选定一个整数，把待排序文件中所有数据分成多个组，所有距离为选定整数的数据分在同一组内，并对每一组内的数据进行排序。然后重复上述分组和排序的工作 。当到达分组=1时，所有数据在统一组内排好序。

public static void shellSort(int[] array){
    int gap= array.length;
    while (gap>1){
        gap/=2;
        shell(array,gap);
    }
}
public static void shell(int []array,int gap){
    for (int i = gap; i < array.length; i++) {
        int tmp=array[i];
        int j = i-gap;
        for (; j >=0 ; j=j-gap) {
            if (tmp<array[j]){
                array[j+gap]=array[j];
            }
            else {
                break;
            }
        }
        array[j+gap]=tmp;
    }
}

总结： 希尔排序是对直接插入排序的优化
· 因为分组的值取法各不相同，所以很难去算时间复杂度
· 空间复杂度：O（1）
· 稳定性：不稳定

选择排序

每一次从待排序的数据元素中选出 最小（或最大） 的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完

直接选择排序

以升序排序来说，直接选择排序可以将一个序列看成两个部分：已经有序的序列和待排序的序列，每一趟从待排序序列中选取一个最小的元素 ，与待排序序列的第一个元素相比较 ，如果这个最小的元素小于 待排序序列第一个元素，则交换 这两个元素的位置，然后原先这个待排序序列的第一个元素就变成了有序序列的最后一个

public static void main(String[] args) {
        int[] array={10,6,18,20,8};
        System.out.println("排序前："+ Arrays.toString(array));
        selectSort(array);
        System.out.println("排序后："+ Arrays.toString(array));
    }
    public static void selectSort(int[] array){
        int minIndex=0,tmp;
        for (int i = 0; i < array.length; i++) {
            //初始化最小值的下标为第一个待排序数据下标
            minIndex=i;
            //遍历待排序数据，找最小数据,更新下标
            for (int j = i+1; j < array.length; j++) {
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            if(minIndex==i){
                continue;
            }
            //交换
            tmp=array[i];
            array[i]=array[minIndex];
            array[minIndex]=tmp;
        }
    }

总结： 直接选择排序思路非常简单，但是效率太低（不是在遍历中，就是在去遍历的路上）

1. 时间复杂度：O(N^2)
2. 空间复杂度：O(1)
3. 稳定性：不稳定

堆排序

堆排序是指利用树（堆）这种数据结构所设计的一种排序算法，需要注意的是排升序要建大堆，排降序建小堆

堆的理解可以参考二叉树，如果对二叉树有所遗忘，可以回顾之前的博客【Java数据结构】— 二叉树

对于排升序采用大根堆，每个结点的值都大于或等于其左右孩子结点的值

我们根据最后一个非子叶节点（array.length/2-1），从左到右，由上到下开始调整

找第二个非子叶节点，继续调整，满足大根堆定义(注意：此时20与10进行交换后，可能导致子树结构混乱，需要继续调整。) 此时刚好满足条件，不需要调整

回到选择排序定义：将堆顶元素与末尾元素进行交换,使末尾元素最大。

然后继续调整堆, 再 将堆顶元素与末尾元素交换，得到第二大元素 如此反复进行交换、重建、交换。

最后得到升序排列

public static void main(String[] args) {
        int[] array={10,6,18,20,8};
        System.out.println("排序前："+Arrays.toString(array));
        heapSort(array);
        System.out.println("排序后："+Arrays.toString(array));
    }
    public static void heapSort(int[] array){
        for (int i = array.length/2-1; i>=0 ; i--) {
            swapHeap(array,i, array.length);
        }
         //继续交换堆顶元素和当前末尾元素
        for (int j = array.length-1; j > 0; j--) {
            int tmp=array[j];
            array[j]=array[0];
            array[0]=tmp;
             //重新调整结构，满足大根堆定义
            swapHeap(array,0,j);
        }
    }

    /**
     *
     * @param array 要调整的数组
     * @param i 非叶子节点的下标
     * @param length 表示待排序数组长度
     */
    public static void swapHeap(int[] array,int i,int length){
        //保存临时变量
        int tmp=array[i];
        //j是i节点的右子节点
        for (int j = i*2+1; j < length; j=j*2+1) {
            //如果右子节点下标有效 并且 左子节点《右子节点
            if(j+1<length && array[j]<array[j+1]){
                //下标递增
                j++;
            }
            //如果右子节点》父节点
            if(array[j]>array[i]){
                //交换
                array[i]=array[j];
                i=j;
            }else{
                break;
            }
        }
        //调整为大根堆
        array[i]=tmp;
    }

完结

好了，到这里Java语法部分就已经结束了~
如果这个系列博客对你有帮助的话，可以点一个免费的赞并收藏起来哟~
可以点点关注，避免找不到我~ ，我的主页：optimistic_chen
我们下期不见不散~~Java

下期预告: 【Java数据结构】- - -排序