堆排序、快速排序和归并排序

堆排序、快速排序和归并排序是所有排序中最重要的三个排序，也是难度最大的三个排序；所以本文单独拿这三个排序来讲解

目录

一、堆排序 

1.建堆

2.堆排序

二、快速排序

1.思想解析

2.Hoare版找基准

3.挖坑法找基准

4.快速排序的优化

5.快速排序非递归

三、归并排序

1.归并思路

2.代码展示及步骤

3.代码分析

 4.归并排序非递归

 5.使用归并排序解决海量数据

一、堆排序 

所谓堆排序，就是在堆的基础上进行排序，那么如何建堆，就是堆排序的重点。

堆排序核心思想：

1.建堆：排升序建大根堆，排降序建小根堆

2.在建好堆后，每次堆顶元素和最后一个位置的元素交换

3.每交换一次，就进行向下调整操作，使其满足堆的性质

4.交换后，最后一个位置向前走一步

1.建堆

堆有两种，大根堆和小根堆。

（1）排升序，建立大根堆

（2）排降序，建立小根堆

再利用大根堆或者小根堆进行排序

（1）建堆

我们建堆使用向下调整的方式，从最后一棵子树开始。每一棵子树都需要进行向下调整。

向下调整创建大根堆

核心：先将一维数组以层序遍历的方式创建成一棵完全二叉树，然后从最后一棵子树（最后一个父亲结点）开始，向下调整（从父亲到最后一个孩子）。每一轮结束，父亲结点减一。

回忆父亲结点和孩子结点的关系：假设知道父亲结点的下标为i，则左孩子的下标为：(2*i)-1；如果知道孩子结点的下标（左右都可）为i，则父亲结点为：（i-1）/2。

通过图示理解大根堆的向下调整创建:

有该数组：{27,15,19,18,28,34,65,49,25,37}

得到一棵逻辑上的完全二叉树：

然后从最后一棵子树开始向下调整：

调整的步骤：

（1）左右孩子比较，找出孩子大的下标（2）大孩子与父亲结点比较，大于父亲结点则交换（3）父亲结点下标走到孩子位置，孩子再等于新的下标

下面是调整的过程：

第一轮：调整最后一棵子树，p的开始位置为4

c=2*9+1=18，上面标错了 

第二轮：p--，走到3的位置

c=2*7+1=15，上面标错了  

第三轮：p--，走到2的位置

c=2*6+1=13，上面标错了  

第四轮：p--，走到1的位置

第五轮：p--，走到0的位置

上面就是堆调整的全过程，我们总结一下：

p代表需要调整的子树，每调整完一轮，p--，直到p调整完；而在每一轮的调整中，交换完一小轮，p就要向下走，c也要继续往下走，直到不满足条件。

下面是建立大根堆的代码：

public void create(int[] arr) {
        //从最后一棵子树向下调整
        for (int parent = (arr.length -1-1)/2; parent >= 0 ; parent--) {
            siftDown(arr,parent,arr.length);
        }
    }
    /**
     *  向下调整
     */
public void siftDown(int[] arr,int parent,int len) {
        int child = parent*2 + 1;
        while(child < len) {
            //1.找左右孩子最大的
            if(child+1 < len && arr[child+1] > arr[child]) {
               child = child + 1;
            }
            if(arr[child] > arr[parent]) {
                swap(arr,child,parent);
                parent = child;
                child = parent*2 + 1;
            }else {
                break;
            }

        }
}
public void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

下面是建立小根堆的代码：

 public void createminHeap() {
        for (int parent = (usedSize-1)/2; parent >= 0 ; parent--) {
            siftDown2(parent,usedSize);
        }
    }
    private void siftDown2(int parent,int end) {
        int child = parent*2+1;//找到左孩子下标
        //循环结束，说明一棵子树调整完成
        while (child < end) {
            //1.找左右孩子最小的一个.进入if说明第二个孩子比较大
            if(child+1 < usedSize && elem[child] > elem[child+1]) {
                child++;
            }
            //2.比较父亲结点和大孩子结点
            if(elem[parent] > elem[child]) {
                swap(parent,child);
                parent = child;
                child = parent*2+1;//找到左孩子下标
            }else {
                break;//满足则结束循环
            }
        }
    }
public void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

2.堆排序

在学会如何建堆之后，才能进行堆排序操作，堆排序操作是比较简单的

思想：每次堆顶元素和最后一个元素交换，交换完进行一次向下调整，每次过后最后一个元素向前走

 大根堆可以保证堆顶元素是最大的，每次和最后一个位置交换；不断交换，就会形成升序。

 堆排序部分代码：

public void headSort(int[] arr) {
        //1.排升序，建大根堆
        create(arr);
        int end = arr.length - 1;
        while(end > 0) {
            //2.每次交换堆顶和最后一个元素
            swap(arr,0,end);
            //3.交换完调整
            siftDown(arr,0,end);
            end--;
        }
    }

堆排序完整代码：

public class heapSort {


    public void headSort(int[] arr) {
        //1.排升序，建大根堆
        create(arr);
        int end = arr.length - 1;
        while(end > 0) {
            //2.每次交换堆顶和最后一个元素
            swap(arr,0,end);
            //3.交换完调整
            siftDown(arr,0,end);
            end--;
        }
    }
    /**
     * 交换
     */
    public void swap(int[] arr,int i,int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
    public void create(int[] arr) {
        //从最后一棵子树向下调整
        for (int parent = (arr.length -1-1)/2; parent >= 0 ; parent--) {
            siftDown(arr,parent,arr.length);
        }
    }
    /**
     *  向下调整
     */
    public void siftDown(int[] arr,int parent,int len) {
        int child = parent*2 + 1;
        while(child < len) {
            //1.找左右孩子最大的
            if(child+1 < len && arr[child+1] > arr[child]) {
               child = child + 1;
            }
            if(arr[child] > arr[parent]) {
                swap(arr,child,parent);
                parent = child;
                child = parent*2 + 1;
            }else {
                break;
            }

        }
    }


}

总结：

（1）时间复杂度：O(n*logn)

（2）空间复杂度：O(1)

（3）稳定性：不稳定

二、快速排序

快速排序是一种基于二叉树形式的交换数据排序，快听名字就知道他很快

下面介绍的快速排序，我们会介绍：快排的思想、Hoare版分割法、挖坑法分割法、如何优化快速排序和快速排序的非递归写法

1.思想解析

（1）官方概念

在待排序的 N个记录中任意取一个记录，把该 记录放在最终位置后， 数据序列被此记录分成两部分。 （如何分成两个部分：所有关键字比该记录关键 字小的放在前一部分, 所有比它大的放置在后一部分, 并把该记录排在这两部分 的中间，这个过程称作一次快速排序）之后重复上述过程， 直到每一部分内只有 一个记录为止。

（2）简述概念

（1）每次找一个基准，再定义两个指针（分别指向数据序列的两头），遍历该数据序列。（2）遍历时，满足一定的条件，就交换指针所指向的值或者其他操作，直到两个指针相遇。

（3）指针相遇的位置就将该序列分成左右两部分

（4）左右两个部分再重复（1）-（3）的操作，直到不能再分解，排序完成

我们这里暂时称（1）（2）两个步骤为：寻找基准法 

上面的都是干巴巴的概念，很难理解，下面结合图解。

（3）图解如何完成排序

下面第一步到找到下一个基准的过程称为：找基准法（官方概念为Hoare版）；找基准法还有另一种称为：挖坑法

使用Hoare找基本法的每一轮：

（4）部分代码

根据上述的图解，我们得出，每次结束，就会将数组分成两个部分，然后每个部分再重复步骤，可以想到使用递归的方式完成。

partition2方法就是找基准法，具体实现下面介绍

private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        int pivot = partition2(array,start,end);//记录每一轮基准的位置
        //递归左边
        quick(array,start,pivot-1);
        //递归右边
        quick(array,pivot+1,end);

    }

找基准法一共有三种：Hoare版、挖坑法、前后指针法，其中最常用的是：挖坑法；不常见的是：前后指针法

2.Hoare版找基准

根据Hoare版的思想完成的代码，具体思想不再重复

private static int partition1(int[] array,int left,int right) {
        //1.确定基准
        int tmp = array[left];
        int l = left;
        //2.遍历数组，直到相遇
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            //交换两个值
            swap(array,left,right);
        }
        //3.交换相遇位置和基本位置的值
        swap(array,l,right);
        //4.返回相遇位置，作为下一次的分割点
        return right;
}
private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

第一种快速排序完整代码：

public static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        int pivot = partition(array,start,end);//记录每一轮基准的位置
        //递归左边
        quick(array,start,pivot-1);
        //递归右边
        quick(array,pivot+1,end);
}
private static int partition(int[] array,int left,int right) {
        //1.确定基准
        int tmp = array[left];
        int l = left;
        //2.遍历数组，直到相遇
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right && array[left] <= tmp) {
                left++;
            }
            //交换两个值
            swap(array,left,right);
        }
        //3.交换相遇位置和基本位置的值
        swap(array,l,right);
        //4.返回相遇位置，作为下一次的分割点
        return right;
}
private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
}

3.挖坑法找基准

挖坑法是最常用的一种，具体实现和Hoare版很相似。

（1）挖坑法思想

每一轮的结果：

（2）挖坑法代码

private static int partition(int[] array,int left,int right) {
        //1.将基准存入临时变量中，形成一个坑
        int tmp = array[left];
        //2.遍历数组，直到相遇
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            //3.放入left位置
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            //4.放入right位置
            array[right] = array[left];
        }
        //5.补坑
        array[right] = tmp;
        return right;
}
private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
 }

第二种快速排序完整代码：

public static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        int pivot = partition(array,start,end);//记录每一轮基准的位置
        //递归左边
        quick(array,start,pivot-1);
        //递归右边
        quick(array,pivot+1,end);
}
private static int partition(int[] array,int left,int right) {
        //1.将基准存入临时变量中，形成一个坑
        int tmp = array[left];
        //2.遍历数组，直到相遇
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            //3.放入left位置
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            //4.放入right位置
            array[right] = array[left];
        }
        //5.补坑
        array[right] = tmp;
        return right;
}
private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
 }

4.快速排序的优化

对于不同的数据，死板的写法不一定有其他排序快；但是根据不同的场景进行不同的优化，可以大大提高快速排序的效率。

下面介绍两种常见的优化方式 

（1）三数取中法

思想：在一堆序列中，找到最左边的数、中间的数和最右边的数中 中间小的一个数与最左边的数进行交换，再以最左边的数为基准进行划分。可以防止升序或者逆序而造成的单分支情况。

应对情况：常见与已有序的序列（顺序或者逆序） 

核心：找到三个数中排在中间的数

举例：下面为顺序的序列，当默认选择第一个数为基准时，右边都是比基准大的而不会交换；在递归过程中，就会形成单分支的二叉树，复杂度进而变大

 三数取中，取的数为：

 如何找中间值：

代码如下：

private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        //三数取中法（优化）
        int index = findMid(array,start,end);
        swap(array,index,start);
        int pivot = partition(array,start,end);
        //递归左边
        quick(array,start,pivot-1);
        //递归右边
        quick(array,pivot+1,end);

 }
/*
        找中间大的元素下标
     */
    private static int findMid(int[] array,int left,int right) {
        int mid = left+( (right - left) >> 1 );
        if(array[left] > array[right]) {
           if(array[left] < array[mid]) {
               return left;
           }else if(array[right] > array[mid]) {
               return right;
           }else  {
               return mid;
           }
        }else {
            if(array[mid] > array[right]) {
                return right;
            }else if(array[left] > array[mid]) {
                return left;
            }else {
                return mid;
            }
        }
    }

（2）递归到小区间时，使用插入排序

思想：结合插入排序

应对情况：一棵二叉树的结点，一般2/3都集中在最后面的几层；如果一直递归下去，计算量是非常大的。

核心：会使用插入排序

private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
        //递归到一定的区间，使用插入排序(优化)
        if((end-start+1) < 5) {
            insertSort(array,start,end);
            return;
        }
        int pivot = partition2(array,start,end);
        //递归左边
        quick(array,start,pivot-1);
        //递归右边
        quick(array,pivot+1,end);

}
 /**
     * 区间插入排序
     */
    private static void insertSort(int[] array,int start,int end) {
        for (int i = start+1; i <= end; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= start ; j--) {
                if(array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }

总结：针对递归法

（1）时间复杂度：O(N*logN)

（2）空间复杂度：O(logN)

（3）稳定性：不稳定

（4）使用场景：数据较乱，不适合趋于有序或者已有序的

5.快速排序非递归

思想：

（1）先找一次基准（借助挖坑法）

（2）（判断：如果基准的左边：pivot-1>left不成立，则不放入栈；右边：pivot+1>right不成立也不放入）放入基准左边头跟尾的两个元素，再放入基准右边的头跟尾两个元素。

（3）栈不为空，取fenbuie除两个元素，分别赋值给右跟左

（4）以左跟右的区间继续找基准

（5）重复（2）-（4）

图解：

判断是否入栈：

代码： 

public static void quickSortNor(int[] array) {
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = array.length - 1;
        //1.找第一次基准
        int pivot = partition(array,left,right);
        //2.将基准左右两边存入栈中
        if(pivot-1>left) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if(pivot+1<right) {
            stack.push(pivot+1);
            stack.push(right);
        }
        //3.栈不为空出栈
        while (!stack.empty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition2(array,left,right);
            //2.将基准左右两边存入栈中
            if(pivot-1>left) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot+1<right) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }


}
private static int partition(int[] array,int left,int right) {
        //1.将基准存入临时变量中，形成一个坑
        int tmp = array[left];
        //2.遍历数组，直到相遇
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            //3.放入left位置
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            //4.放入right位置
            array[right] = array[left];
        }
        //5.补坑
        array[right] = tmp;
        return right;
}
private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
 }

时间复杂度：nlogn

空间复杂度：longn

稳定性：不稳定

三、归并排序

下面的归并排序，我们注重介绍：归并排序的思路（包括文字思路，图片思路）、归并排序的代码和代码执行过程的讲解

归并排序和快速排序类型，使用了分治的思想，其中，也需要用到递归的。而归并排序的核心就是一分为二，再合并。

1.归并思路

（1）大致思想

（1）将数据不断平分为两段，直到不能再分解，形成一个单独的有序个体。

（2）然后在往回走的过程中，不断合并做到有序。

（2）具体图解：

分解思路：

并起思路：在合并的过程中就完成了排序

（3）如何分解：加入一点数学知识

下面是所有片段的left，mid和right位置

根据这里得出一个规律：当left>=right时，分解停止。

2.代码展示及步骤

代码中的注释很全面的介绍了每个步骤

（1）代码展示

public class mergeSort {


    public static void mergeS(int[] array){
        mergeF(array,0,array.length-1);
    }
    //一.分解的方法（归）
    private static void mergeF(int[] array,int left,int right){
        //1.停止分解的条件
        if(left>=right) {
            return;
        }
        //2.记录拆分的位置
        int mid = left + ((right - left)>>1);
        //3.拆成的左半部分（使用递归）
        mergeF(array,left,mid);
        //4.拆成的右半部分（使用递归）
        mergeF(array,mid+1,right);
        //5.开始合并
        merge(array,left,mid,right);
    }
    //二.合并的方法（并）
    private static void merge(int[] array,int left,int mid,int right) {
        int[] arrTmp = new int[right-left+1];
        int s1 = left;//遍历第一个子序列
        int e1 = mid; //记录第一个子序列末端位置
        int s2 = mid+1;//遍历第二个子序列
        int e2 = right;//记录第二个子序列末端位置
        int k = 0;//遍历临时数组
        //1.将其中一个序列的数据全部拷入临时数组中
        while (s1<=e1 && s2<=e2) {
            if(array[s1] > array[s2]) {
                arrTmp[k++] = array[s2++];
            }else {
                arrTmp[k++] = array[s1++];
            }
        }
        //2.将未拷完的子序列继续拷入
        while (s1<=e1) {
            arrTmp[k++] = array[s1++];

        }
        while (s2<=e2) {
            arrTmp[k++] = array[s2++];

        }
        //3.将排序好的临时数组中的数据拷回原数组
        for (int i = 0; i < arrTmp.length; i++) {
            array[i+left] = arrTmp[i];
        }

    }
}

（2）数据拷贝回原数组部分

//3.将排序好的临时数组中的数据拷回原数组
        for (int i = 0; i < arrTmp.length; i++) {
            array[i+left] = arrTmp[i];
        }

3.代码分析

上面对代码的简述也只是一种简单的概述，下面详细介绍一下代码的执行过程，包括是如何递归，及如何并。

部分过程：

类似二叉树的递归，当递归到一定条件时，才会开始合并；并不是和前面的图片一样，要全部分解完才开始逐一递归。

部分合并过程：

总结：

（1）时间复杂度：O(N*logN)

（2）空间复杂度：O(logn)

（3）稳定性：稳定

（4）使用场景：在磁盘中的外排序问题

 4.归并排序非递归

引入：非递归的归并排序，重点也在后面的合并方法上；递归法是先递归到最小单元才开始合并，而非递归是直接开始合并。

步骤分析：

（1）定义一个变量gap，用来标识最小的有序集；每次合并两个有序集，当gap>=数组长度一半时，代表排序完成。

（2）定义一个变量i，用来遍历数组中所有的有序集，每次跳过两个有序集

（3）我们只需要根据合并的方法拿到对应的下标即可

思路解析：非递归，我们使用直接从最小单元开始合并，也就是以一个数据作为最小单位。

需要拿到的下标：这是根据上面递归法写的合并方法，这里通用。

根据上面得到以下代码：

public static void mergeSortNor(int[] array) {
        int gap = 1;//一组的数据个数
        //循环一次，完成一轮合并
        while (gap < array.length) {
             //每循环一次，代表合并两个组
            for (int i = 0; i < array.length; i = i+2*gap) {
                int left = i;
                int mid = left+gap-1;
                //两个if，防止数组越界
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid+gap;
                if(right >= array.length) {
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap = gap*2;
        }
    }

完整非递归代码：

public static void mergeSortNor(int[] array) {
        int gap = 1;//一组的数据个数
        //循环一次，完成一轮合并
        while (gap < array.length) {
             //每循环一次，代表合并两个组
            for (int i = 0; i < array.length; i = i+2*gap) {
                int left = i;
                int mid = left+gap-1;
                //两个if，防止数组越界
                if(mid >= array.length) {
                    mid = array.length-1;
                }
                int right = mid+gap;
                if(right >= array.length) {
                    right = array.length-1;
                }
                merge(array,left,mid,right);
            }
            gap = gap*2;
        }
    }
private static void merge(int[] array,int left,int mid,int right) {
        int[] arrTmp = new int[right-left+1];
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        int k = 0;
        while (s1<=e1 && s2<=e2) {
            if(array[s1] > array[s2]) {
                arrTmp[k++] = array[s2++];
            }else {
                arrTmp[k++] = array[s1++];
            }
        }
        while (s1<=e1) {
            arrTmp[k++] = array[s1++];

        }
        while (s2<=e2) {
            arrTmp[k++] = array[s2++];

        }
        for (int i = 0; i < arrTmp.length; i++) {
            array[i+left] = arrTmp[i];
        }
    }

 5.使用归并排序解决海量数据

当所排序的对象巨大时，需要使用外部排序，而归并排序就是外部排序的一种典型代表。

外部排序：排序过程需要在磁盘等外部存储进行的排序（不直接借助内存）

使用场景：内存只有1G，而排序的数据却有100G

所以我们需要使用归并排序去完成：

（1）先把文件切分成 200 份，每个 512 M
（2）分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
（3）进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了（这个时候不借助内存）