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

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

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

目录

一、堆排序 

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 份有序文件做归并过程,最终结果就有序了(这个时候不借助内存)

转载请说明出处内容投诉
CSS教程_站长资源网 » 堆排序、快速排序和归并排序

发表评论

欢迎 访客 发表评论

一个令你着迷的主题!

查看演示 官网购买