目录

希尔排序

基本思想

代码设计

代码实现

时间、空间复杂度

相关小问题

堆排序

基本思想

代码设计

代码实现

时间、空间复杂度

归并排序

基本思想

代码设计

代码实现

时间、空间复杂度

希尔排序是不稳定的。

基本思想

希尔排序是插入排序的一种，是对插入排序的一种优化。

按照  gap = length /2 ; 随后以增量gap = gap / 2取值;每次按增量对相应的元素进行比较交换。

直到增量为1时，排序完成。

代码设计

定义 i , j  , temp;

和插入排序相似，只不过将增量从1变为5，3，等。

代码实现

    private static> void shellSort(T[] element ,int gap ){
        for(int i=gap;i=0;j-=gap){
                if(element[j].compareTo(temp) > 0){
                    element[j+gap] = element[j];
                }else{
                    element[j+gap] = temp;
                    break;
                }
            }
            element[j+gap] = temp;
        }
    }
    public static > void shellSort1(T[] element){
        if(element == null||element.length == 1){
            return;
        }
        int[] gap = {5,3,1};
        for (int i = 0; i < gap.length; i++) {
            shellSort(element,gap[i]);
        }
    }
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{7,4,6,3,2,7,13,11,8,0,5};
        shellSort1(arr);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+" ");
        }
    }

时间、空间复杂度

空间复杂度：O(1)

时间复杂度：O(n^1.3  ~ n ^ 1.5)

相关小问题

1.gap（即分组）为什么取奇数 （eg :  5   3   1）而不取偶数 （4   2   1）？

答：避免分组重复，若取偶数，容易出现两个数又一次作比较。

2.若数据量比较大，怎么取gap？

答：gap = length /2;随后以增量gap = gap / 2取值;避免取偶数，遇到偶数，可在gap上  +1；

堆排序

堆排序是不稳定的。

基本思想

堆总是一棵完全二叉树。其实际存储结构是数组，逻辑结构上的左右孩子遵循的规律是  根节点（i）、左孩子（2*i+1）、右孩子（2*i+2）

1，根据元素构建堆

2，将初始文件调整成一个大根堆

3，将根节点取出，与堆的最后一个节点进行交换，最后一个元素即为最大值，构成有序序列。

4，将下标为  0 至下标为 arr.length-1-1 的元素进行堆调整。

5，将根节点和下标为 arr.length -1-1 的元素进行交换，arr[arr.length-1-1]为无序序列的最大值，成为有序序列。

6.依次进行调整。

 

代码设计

大根堆调整过程：传入参数begin，end，end为数组最后一个元素的下标，begin从倒数第一个根节点开始。

         定义下标 i ，i = begin *2+1(即begin的左孩子结点)，保存当前最大值；判断该结点是否有右孩子，若没有，则 i =为左孩子，若有，判断左右孩子的大小，左>右，i不变；左<右,i++;

        定义过渡遍量 temp，存放 temp = arr[begin] ; 比较 temp和arr[i]大小，temp > arr[i],结束；temp < arr[i] ,交换arr[begin]和arr[i],重复以上操作，直到arr[begin] >arr[i]，arr[begin] = temp;结束；

        通过 index*2+1 = arr.length-1,（若有右孩子，计算结果一样）计算得出 index = (arr.length -1-1)/2; index --;自小而上，将堆调整成大根堆。

堆排序：将arr[arr.length -1](最后一个元素)和arr[0] 交换，最大的元素找到，构成有序序列。

        从下标为0至下标为arr.length-1-1调整为大根堆，将arr[arr.length -1-1](最后一个元素)和arr[0] 交换，无序序列最大元素找到，并加入有序序列（由小到大排列）。

        重复以上操作，得到结果。        

代码实现

import java.util.Arrays;

// TODO: 2021/9/14 堆排序
public class HeapSort {

    
    public static> void adjust(T[] arr,int begin,int end){
        T temp = arr[begin]; // 存放begin
        for(int i = begin*2+1;i<=end;i=i*2+1){
            // 挑选左右孩子
            if((i+1)<=end && arr[i].compareTo(arr[i+1])<0){
                // 判断是否存在右孩子,且左孩子小于右孩子
                i++;
            }
            if(arr[i] .compareTo(temp)>0){
                arr[begin] = arr[i];
                begin = i;
            }else{
                break;
            }
        }
        arr[begin] = temp;
    }
    public static> void heapSort(T[] arr) {
        if(arr == null||arr.length ==1){
            return;
        }
        // 先调整成大根堆，必须从下往上进行调整  index*2+1 = arr.length-1;
        for(int i = (arr.length-1-1)/2;i>=0;i--){
            adjust(arr,i,arr.length-1);
        }
        for(int i =0;i void swap(T[] arr,int index1,int index2){
        T temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }

    public static void main(String[] args) {
        Integer[] element = {1,4,2,1,5,3,11,8,6};
        heapSort(element);
        System.out.println(Arrays.toString(element));
    }
}

时间、空间复杂度

平均时间复杂度：O(n log2^n)

空间复杂度：O(1)

归并排序

归并排序是稳定的

基本思想

归并排序是将已经有序的子序列进行排序，得到完全有序的序列，是将每一小段有序，再将小段之间变得有序。将两个有序段合成一个有序段，称为二路归并。

代码设计

L1、R1分别为第一个归并段的左、右边界；L2、R2分别为第一个归并段的左、右边界

1）L1和L2进行比较，若L1

2）检查L1是否等于R1+1或L2是否等于R2+1;若相等，说明该归并段遍历完，另一个归并段的元素按照顺序复制到新的空间。若不相等，进行步骤 3）。

3）得到新的L1或L2,重复步骤 1）。

4）组成新的归并段，重新复制L1,R1,L2,R2,重复步骤 1），2），3）

代码实现

       private static> void merge(T[] element,int gap){
        // 定义left1 ,right1,left2,right2
        int left1 = 0;
        int right1 = left1+gap-1;
        int left2 = right1 + 1;
        int right2 = left2+gap-1 < element.length?left2+gap-1:element.length-1;
        // 判断第二个归并段的右边界是否越界
        T[] temp = (T[]) new Comparable[element.length];
        int tempIndex = 0;
        // 两个归并段
        while(left2right1
            while (left2<=right2){
                temp[tempIndex++]=element[left2++];
            }
            // left2>right2
            while (left1<=right1){
                temp[tempIndex++]=element[left1++];
            }
            left1 = right2+1;
            right1 = left1+gap-1;
            left2 = right1+1;
            right2 = left2+gap-1 < element.length?left2+gap-1:element.length-1;
        }
        // 只剩下一个归并段
        while (left1= element.length){
            temp[tempIndex++] = element[left1++];
        }
        for (int i = 0; i < temp.length; i++) {
            element[i] = temp[i];
        }
        temp = null;
    }

    public static> void mergeSort(T[] element){
        if(element == null || element.length == 1){
            return;
        }

        for(int i = 1;i 
时间、空间复杂度 
空间复杂度：O(n)
 
平均时间复杂度：O(nlog2^n)