冒泡排序、快排和堆排序

Data Structures Experiment #16 - 排序

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

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

注:排序结果均为升序。

bubbleSort

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

注意,当某一次遍历0i时,若整个过程中未发生任何交换,即0i的每一项均小于它的下一项,说明此时数组已经排好序(i+1len-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+1len-1之间,这两种形式有何不同?


回到我们的思路。

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

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

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

  • for (int j = i + 1; j < len; j++)却出现了错误。它第一次遍历(0len-1)把最大项移动到了末尾;第二次遍历(1len-1)却把1len-1部分的最大项移动到了倒数第二位,忽略了第0项;第三次遍历(2len-1)忽略了前两项;第四次遍历(3len-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;
}