冒泡排序、快排和堆排序

发表于 分类于 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 6 分钟

Data Structures Experiment #16 - 排序

在MySort.cpp中完成三个排序方法。

  • bubbleSort(int* arr, int len);
    实现冒泡排序，需要排序的数组为arr，数组长度为len
  • quickSort(int* arr, int len);
    实现快速排序
  • heapSort(int* arr, int len);
    实现堆排序

注：排序结果均为升序。

bubbleSort

冒泡排序的思路就是从头到尾进行遍历，如果某一项比下一项大，就将这两项交换，最终导致最大项移动到末尾。

注意，当某一次遍历0到i时，若整个过程中未发生任何交换，即0到i的每一项均小于它的下一项，说明此时数组已经排好序（i+1到len-1已经为升序），此时即可跳出循环，算法结束。

按照以上思路设计算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void MySort::bubbleSort(int* arr, int len){
    int i = 0;
    bool exchange = true;
    while (i < len && exchange) {
        exchange = false;
        for (int j = i + 1; j < len; j++) {
            if (arr[j - 1] > arr[j]) {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
                exchange = true;
            }
        }
        i++;
    }
}

此时运行发现并不能得出正确的排序结果。仔细观察排序结果可以发现，前若干项的顺序依旧很混乱，而末尾几项却是正确的升序。

经过几次的调整，发现当第6行的for循环改为这样就可以正确排序：

1
for (int j = len - 1; j > i; j--)

只不过是把正序遍历改为了逆序遍历，而且都在i+1和len-1之间，这两种形式有何不同？

回到我们的思路。

我们需要遍历若干次，将每次的最大项移动到区间的末尾。

  • for (int j = len - 1; j > i; j--)的过程是从后向前遍历，如果某一项比前一项小，就交换。最终把区间内的最小项移动到区间的开头。

    由于i是从0到len-1的，所以整体来看，就是第一次遍历（len-1到0）把最小项移动到数组第0位；第二次遍历（len-1到1）把剩下的最小项移动到第1位……以此类推。

  • 而for (int j = i + 1; j < len; j++)却出现了错误。它第一次遍历（0到len-1）把最大项移动到了末尾；第二次遍历（1到len-1）却把1～len-1部分的最大项移动到了倒数第二位，忽略了第0项；第三次遍历（2到len-1）忽略了前两项；第四次遍历（3到len-1）忽略了前三项……

    正确的遍历是从0开始，即从0遍历到len-1时，数组中的最大项移动到了末尾，下一次只需从0遍历到len-2，即可从前len-1项中找到整个数组的次大项，移动到倒数第二位……以此类推。

    所以正确的写法应该是for (int j = 0; j < len - i; j++)。

修改后的算法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void MySort::bubbleSort(int* arr, int len){
    int i = 0;
    bool exchange = true;
    while (i < len && exchange) {
        exchange = false;
        for (int j = 0; j < len - i; j++) {
     // for (int j = len - 1; j > i; j--) {
            if (arr[j - 1] > arr[j]) {
                int temp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = temp;
                exchange = true;
            }
        }
        i++;
    }
}

quickSort

快速排序的思路就是一种分治的思想，在数组中取一个基准，将所有不超过它的元素移动到它的左侧，并将所有不小于它的元素移动到它的右侧，再对划分出的两个子序列重复以上操作。

假设取每次区间的第一个元素（值为key）为基准，从右向左找到第一个比它小的元素s放到最左侧，从左向右找到第一个比它大的元素放到s的位置。重复以上操作，直至基准元素的位置确定，再把它的值key放到此处。

此时再对基准元素左右两侧的子序列重复以上操作，即可将所有元素的位置确定。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void MySort::qSort(int* arr, int low, int high) {
    if (low < high) {
        int i = low;
        int j = high;
        int key = arr[low];
        while (i < j) {
            while (i < j && arr[j] >= key)
                j--;
            if (i < j)
                arr[i++] = arr[j];
            while (i < j && arr[i] <= key)
                i++;
            if (i < j)
                arr[j--] = arr[i];
        }
        arr[i] = key;
        qSort(arr, low, i - 1);
        qSort(arr, i + 1, high);
    }
}

直接调用递归函数：

1
2
3
void MySort::quickSort(int* arr, int len){
    qSort(arr, 0, len - 1);
}

heapSort

什么是堆排序？

首先要知道什么是堆。堆是一棵完全二叉树，满足：

  • 按照顺序存储方式存放于一个数组中（自顶向下、自左向右编号）；
  • 任意结点的值均不小于它的所有子结点（称为“大顶堆/最大堆”），或任意结点的值均不超过它的所有子结点（称为“小顶堆/最小堆”）。

可以发现：

  • 从堆的第一个特性可以看出：设某结点为数组中的第i个元素，则其左子结点（如果有）为数组中的第2*i+1个元素，右子结点（如果有）为数组中的第2*i+2个元素（均从0开始）。

    这样我们就不必构造一颗二叉树，只需按此规律在数组中进行模拟二叉树的操作即可。

  • 从堆的第二个特性可以看出：若堆为大顶堆，则根结点的值为整个序列的最大值；若堆为小顶堆，则根结点的值为整个序列的最小值。

    这就为我们的排序提供了一个很好的方法。按照我们进行冒泡排序的思路，只需将数组调整为大顶堆，并将其第一个元素（大顶堆的根结点，最大值）移动到最后，再将剩下的元素继续调整为大顶堆，再将其第一个元素（剩余大顶堆的根结点，剩余元素中的最大值）移动到倒数第二位……以此类推，便可得到一个升序序列。这就是堆排序（heap sort）。

根据以上思路，堆排序一共分为两部分：

  • 调整数组指定区间元素为大顶堆；
  • 将数组第一个元素与区间末尾的元素进行交换。

只需反复进行调整->交换->调整->交换->调整……即可完成排序。

首先将乱序的数组进行一次调整。由于调整针对的是非叶结点，所以从最后一个有叶子的非叶结点开始，逐个向前调整。

注：不能从前向后调整，否则会导致真正的最大值无法上移到根结点。此处的调整为逐个调整，因为开始时为乱序。

其次进行交换。根据冒泡排序的思路，将待排区间逐个前移，即每次均从0开始，结束的位置由len-1依次向前。

最后是每次交换后的调整。

注：此处的调整为从0开始的调整。因为前一步操作只是改变了第0个元素，而其他部分仍保持大顶堆结构。

1
2
3
4
5
6
7
8
9
10
void MySort::heapSort(int* arr, int len){
    for (int i = len / 2 - 1; i >= 0; i--)
        heapAdjust(arr, i, len);
    for (int i = len - 1; i >= 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapAdjust(arr, 0, i);
    }
}

关于具体调整的操作，我们设调整开始的结点值为数组的第s个元素，待排区间的长度为size。

我们应该将第s个元素temp与它的子结点的值进行比较（适当向下寻找，找到较大值），如果子结点值较大则放到s处，否则说明子结点值均小于s元素，结束调整；再将子结点的值与子结点的子结点的值进行比较……以此类推。

注：下面的叙述中，将完全二叉树的所有叶结点称为“第一层”，以此向上的每层结点为“第二层”、“第三层”等。

对于第一种的逐个调整，由于顺序是从后向前，则前若干次调整即可将第一层中的值较大者放到对应的第二层处，重复进行即可不重不漏地建立大顶堆。

对于第二种的从0调整，由于基本上保持了大顶堆的结构，所以等价于沿着值较大的子结点一直找到剩余元素中的最大值，未选择的子结点及其子树的值必全部小于所选择的子结点的值。

1
2
3
4
5
6
7
8
9
10
11
12
void MySort::heapAdjust(int* arr, int s, int size) {
    int temp = arr[s];
    for (int i = 2 * s + 1; i < size; i = 2 * i + 1) {
        if (i < size - 1 && arr[i] < arr[i + 1])
            i++;
        if (temp >= arr[i])
            break;
        arr[s] = arr[i];
        s = i;
    }
    arr[s] = temp;
}