【java数据结构之八大排序（上）-直接插入排序，希尔排序，选择排序，堆排序，向下调整(大根堆，小根堆)等知识详解】

🌈个人主页：努力学编程’

⛅个人推荐：基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解

⚡学好数据结构，刷题刻不容缓：点击一起刷题

🌙心灵鸡汤：总有人要赢，为什么不能是我呢

hello,今天带大家学数据结构的一个非常重要的部分，排序！！！，回想博主的学习路程 ，好像真正学过的排序就是冒泡排序，其实数据结构里面有很多的排序的算法，针对不同的数据，我们往往采用不同的排序算法，合适的排序算法处理数据时可能会大大减少内存的消耗，和较短的运行时间。下面就带大家学习几种常见的排序算法。

🍪插入排序：

🍰直接插入排序：

直接插入排序是一种简单直观的排序算法，将待排序的元素逐个插入到已经排序好的序列中的适当位置，从而得到一个新的、更长的有序序列。具体的实现呢，给大家列出来了：

1.初始状态：假设第一个元素已经是有序的序列。

遍历未排序部分：从第二个元素开始，逐个遍历未排序的元素。

插入操作：对于当前遍历到的元素，将其与已经排序好的序列中的元素依次比较，找到合适的位置插入。

2.移动元素：如果发现当前元素比已排序序列中的某个元素小（或大，取决于排序顺序），则将该元素后移一位，为当前元素腾出插入位置。

插入元素：找到合适的位置后，将当前元素插入到该位置。

重复：重复上述步骤，直到所有元素都被插入到有序序列中。

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

直接插入排序的特性总结：

1. 元素集合越接近有序，直接插入排序算法的时间效率越高
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)，它是一种稳定的排序算法
4. 稳定性：稳定

🍰希尔排序

希尔排序又称为缩小增量排序，其本质是将所有的数据分成N组，每一组的元素对应的是从第一个开始，每N个的元素后的那个元素进行比较排序，依次对N组元素做同样的处理。

然后对数据重新分组，分为K组(K int gap = array.length;//n while (gap 1) { gap = gap/3 + 1; shell(array,gap); } } /** * 每组进行插入排序 * @param array * @param gap */ private static void shell(int[] array,int gap) { //i++ 交替进行插入排序 for (int i = gap; i = 0 ; j -= gap) { if(array[j] > tmp) { array[j+gap] = array[j]; }else { break; } } array[j+gap] = tmp; } } private static void swap(int[] array,int i,int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; }

这里还是给大家具体演示一下，帮助大家理解。

🍰选择排序

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

这里先给大家这个简单比较容易理解的版本：

public void selectSort(int[] array){
        for(int i=0;i
            int minindex=i;
            for(int j=i+1;j
                if(array[minindex]array[j]){
                    minindex=j;
                }
            }
            swap(array,minindex,i);
        }
    }
    public void swap(int[]array,int i,int j){
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
    }

        int left=0;
        int right=array.length-1;
        while(left
            int minIndex=left;
            int maxIndex=left;
            for(int i=left;i
               if(array[i]array[maxIndex])  maxIndex=i;
               if(array[i]
        for(int parent=(array.length-1-1)/2;parent0;parent--){
            //从最后一个叶子节点的父节点开始遍历，向下调整
            siftDown(parent,array,array.length);
        }
    }
    public void siftDown(int parent,int[] array,int end){
        int child=parent*2+1;
        while(child
            if(child+1
                child++;
            }
            if(array[child]array[parent]){
                swap(array,child,parent);
                //这里是因为把孩子节点与父节点交换之后可能有问题
                //所以对树的底层都要检查一下
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }

        for(int parent=(array.length-1-1)/2;parent0;parent--){
            //从最后一个叶子节点的父节点开始遍历，向下调整
            siftDown(parent,array,array.length);
        }
    }
    public void siftDown(int parent,int[] array,int end){
        int child=parent*2+1;
        while(child
            if(child+1
                child++;
            }
            if(array[child]array[parent]){
                swap(array,child,parent);
                //这里是因为把孩子节点与父节点交换之后可能有问题
                //所以对树的底层都要检查一下
                parent=child;
                child=parent*2+1;
            }else{
                break;
            }
        }
    }
    public void HeapSort(int[] array){
        createBigHeap(array);
        int end=array.length-1;
        while(end=0){
            swap(array,end,0);
            siftDown(0,array,end);
            end--;
        }
    }