快速排序和堆排序

发表于： 分类于：
字数： 1659 阅读：≈ 4分钟

🍖 快速排序和堆排序

本文主要介绍数组中的快速排序和堆排序的执行流程，介绍这两个算法的原理，针对快速排序来说，就是每一趟确定一个元素的位置，针对堆排序来说，就是每一次调整都找到一个最值元素

電腦科學概論：演算法入門概要

快速排序

原理

快速排序的核心就是在于每一次的排序都要找到一个合适的位置，将当前元素插入这个位置之后，左边的元素不大于当前元素，右边的元素不小于当前元素，然后当前元素的位置固定了，左右两边的元素位置还需要继续划分，直到所有的元素都找到了自己的为止就完成了排序，由于每一次排序都是一半元素，所以时间复杂度为O(nlogn)

每一趟快速排序都找到一个元素的最终位置，类似于不停地填坑，小的元素往前放，大的元素向后放，然后填完了最后一个坑就放置标志元素，然后两边的元素继续应用快速排序的算法，直到序列无法划分，针对升序还是降序的问题，主要是看大于标志位的元素往前放还是往后放，大于标志位的元素往前放就是降序，往后放就是升序

核心就是每一趟找到一个标志元素的最终位置，大的往后放，小的往前放，并且序列长度大于1才能进行划分

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public static void quickSort(int[] nums, int left, int right) {
    int temp = nums[right];
    int i = left, j = right;
    //当序列长度大于1才能划分
    if (left < right) {
        while (i < j) {
            //从前面找一个大于temp的数放到后面
            while (i < j && nums[i] <= temp)
                ++i;
            if (i < j)
                //将当前这个大于temp的元素向后放，并且j移动
                nums[j--] = nums[i];
            while (i < j && nums[j] > temp)
                --j;
            if (i < j)
                //将当前这个小于temp的元素向前方，并且i移动
                nums[i++] = nums[j];
        }
        //找到了当前标志元素的最终位置
        nums[i] = temp;
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }
}

堆排序

原理

堆排序的原理就是每次从堆的根节点删除一个节点加入有序序列，然后将剩下的节点继续调整成一个堆，经过n-1次调整之后，就形成了一个有序序列，针对每一个非叶结点来说，需要不断的向下调整，直到找到自己的合法位置，对于大根堆来说，当前节点的值不能小于两个孩子节点，对于小根堆来说，当前节点的值不能大于两个孩子节点的值

整体的原理就是不断的删除堆的根节点，然后重新调整堆的结构，需要注意的几个关键索引，一个是len/2，这个索引代表第一个从下到上，从右到左的第一个非叶结点的位置，j=i*2代表j是i的左边孩子节点

主要流程如下：

  1. 构造一个初始的堆，也就是从第一个非叶结点开始构造调整
  2. 然后经历n-1次删除，每删除一次都要重新调整

经历上面两步就可以形成一个有序序列，核心的代码就是调整，从当前节点出发，对于两个孩子节点谁大谁小，选择一个最值放到当前的根节点上，如果当前根节点已经是最值了，那么就不用再调整了

如果想要升序，那么就需要形成大根堆，此时根节点应该是最大值，如果想要降序，那么就需要形成小根堆，此时根节点应该是最小值

img

上面的分析适用于大根堆和小根堆，调整的过程中需要注意，根节点的值是从根节点以及两个孩子节点中取的一个最值，调整的时候是不断向下调整的过程，为了能够更好的计算父子节点的下标，数组的下标建议从1开始

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public static void heapSort(int[] nums, int len) {
    int i, temp;
    for (i = len / 2; i > 0; --i) {
        Sift(nums, i, len);
    }

    //开始进行堆排序
    for (i = len; i >= 2; --i) {
        temp = nums[1];
        nums[1] = nums[i];
        nums[i] = temp;
        Sift(nums, 1, i - 1);
    }
}

//从当前位置出发向下调整当前节点的位置
//大根堆还是小根堆取决于小元素做根节点还是大元素做根节点
private static void Sift(int[] nums, int low, int high) {
    int i = low, j = i * 2;
    int temp = nums[low];
    while (j <= high) {
        //能够找到并且右边的兄弟节点更小
        if (j < high && nums[j] < nums[j + 1])
            ++j;
        if (temp < nums[j]) {
            nums[i] = nums[j];
            i = j;
            j = i * 2;
        } else {
            break;
        }
    }
    //找到当前节点的最终位置
    nums[i] = temp;
}

总结

针对上面分析的快速排序和堆排序，要明白两种排序算法的灵魂所在，快速排序主要是在每一趟确定一个标志元素的最终位置，堆排序主要在于每次删除一个根节点，然后将剩下的继续调整成一个堆，这样每次删除一个节点，最终可以形成一个有序序列。快速排序的重点在于每一趟将大于和小于标志元素的值分布在标志元素两边，堆排序的核心在于将非叶子结点调整到合适的位置，使得叶子结点要么小于两个孩子节点，要么大于两个孩子节点，只要不满足条件就不停地向下调整