高级排序算法

一.归并排序

概述：

归并排序是一种经典的分治算法，其原理可以简要描述为以下几步：

  1. 分解：将待排序的数组（或列表）逐步分解为更小的子数组，直到每个子数组只有一个元素为止。这一步是通过递归实现的，即将数组不断地拆分成两个更小的部分。

  2. 合并：将分解得到的子数组逐步合并，合并过程中将两个已经有序的子数组合并成一个有序的数组。这一步是递归地将两个有序子数组合并成一个更大的有序数组，直到整个数组被合并为一个有序数组为止。

  3. 合并操作：合并过程是归并排序的核心，它包括比较两个有序子数组的元素，并按照顺序将它们合并到一个新的有序数组中。合并操作通常会用到额外的空间来存储临时结果。

  4. 递归：以上两步在递归调用中完成，直到每个子问题规模足够小，可以直接求解为止。

总体来说，归并排序通过递归地将数组分解成更小的部分，并通过合并操作将这些部分逐步合并成一个有序数组，从而实现排序。其时间复杂度为 O(n log n)，是一种稳定的排序算法。

原理图示：

归并排序原理图

代码实现

老师实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include "my_merge_sort.h"
#include <stdlib.h>
#include <stdio.h>

// 打印数组的函数
void print_arr(int arr[], int left, int right) {
  for (int i = left; i <= right; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

/*
* 合并的思路:
* 1.把左右子数组中元素按照顺序合并到临时数组中,过程类似"穿针引线"
* 2.将排好序的临时数组元素按照下标赋值给原数组
* 注：临时数组和原数组共有一套下标
* 传入函数逻辑上的左右子数组是有序的,相当于合并两个有序的左右子数组
*/
static void merge(int arr[], int left, int mid, int right, int* tmp) {
  /*
  * tmp_idx: 用于存放合并结果的临时数组的开始下标
  * left_idx: 左子数组的开始下标
  * right_idx: 右子数组的开始下标
  */
  int tmp_idx = left, left_idx = left, right_idx = mid + 1;

  // 只要左右子数组同时还有元素
  while (left_idx <= mid && right_idx <= right) {
    // 捉对比较左右子数组的元素,按照从小到大放入临时数组
    // <=判断不会改变相同元素的相对位置,是稳定算法。反之则不是稳定算法
    if (arr[left_idx] <= arr[right_idx]) {
      tmp[tmp_idx++] = arr[left_idx++];
    }
    else {
      tmp[tmp_idx++] = arr[right_idx++];
    }
  } 
  // while结束时，左右子数组必然有一个没有元素了,此时另一个数组必然还有元素
  // 也就是说只会有一个数组是空的
  // 但我们无法确定是哪个数组没有元素了
  // 所以我们都判断一下将左右子数组还剩余的元素取出来
  while (left_idx <= mid) {
    // 说明左数组还有元素
    tmp[tmp_idx++] = arr[left_idx++];
  }
  while (right_idx <= right) {
    // 说明右数组还有元素
    tmp[tmp_idx++] = arr[right_idx++];
  }

  // 将临时数组中已排序好的元素复制到原始数组中
  for (int i = left; i <= right; i++) {
    arr[i] = tmp[i];
  }
  // 打印此一轮归并排序的元素
  print_arr(arr, left, right);
}

/*
* 辅助函数,实现对[left, right]范围内的数组递归分解合并
* left表示递归分解的区间起点,right表示递归分解区间的终点,是一个闭区间
* 递归分解的思路是:
* 对[left, right]区间元素的排序,可以分解成:
* [left, mid]区间,和[mid + 1, right]区间的排序合并
* 递归的出口是:
* 如果区间仅有一个元素或没有元素,递归结束
*/
static void divide_merge(int arr[], int left, int right, int* tmp) {
  // 递归的出口
  if (left >= right) {
    return;
  }

  // 递归体
  // 计算中间索引
  int mid = left + (right - left >> 1);
  // 分解,规定左数组是[left, mid]
  // 右数组是[mid + 1, right]
  divide_merge(arr, left, mid, tmp);
  divide_merge(arr, mid + 1, right, tmp);

  /*
  * 归并，归并排序的核心操作
  * 需要一个临时数组完成此操作
  * 这个临时数组至少要和原先的数组一般大
  * 有两种方案：
  * 1.用全局变量数组或局部变量,该方式简洁易实现,无需考虑内存回收
  * 但缺点是
  * a.必须编译时期确定数组长度,无法运行时期动态分配
  * b.栈区和数据段都无法创建长数组,在大数据集下容易产生溢出错误
  * 为了解决这两个缺点,我们可以在堆上动态分配数组
  * 但同样也有缺点:
  * a.内存管理风险
  * b.动态分配数组会带来额外性能开销
  */
  merge(arr, left, mid, right, tmp);

}

void merge_sort(int arr[], int len) {
  // 临时数组
  int* tmp = calloc(len, sizeof(int));
  if (tmp == NULL){
    printf("calloc failed in merge_sort.\n");
    return;
  }

  // 将整个数组进行递归分解合并,即完成归并排序
  divide_merge(arr, 0, len - 1, tmp);

  // 不要忘记free释放资源
  free(tmp);
}

// 测试归并排序
int main() {
  int arr[] = { 8, 3, 2, 6, 9, 7, 1, 0, 4, 5 };
  int arr_size = sizeof(arr) / sizeof(arr[0]);

  merge_sort(arr, arr_size);
  return 0;
}

自己实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

#define ARR_LEN(num) (sizeof(num)/sizeof(num[0]))
#define SWAP(num,a,b){\
int tmp = num[a];\
num[a] = num[b];\
num[b] = tmp;\
}

//归并排序
static void merge(int* num, int left, int mid, int right, int* tmp_num) {

	int tmp_left = left;
	int tmp_right = mid + 1;
	int tmp = left;

	while (tmp_left <= mid && tmp_right <= right) {
		if (num[tmp_left] <= num[tmp_right]) {
			tmp_num[tmp++] = num[tmp_left++];
		}
		else {
			tmp_num[tmp++] = num[tmp_right++];
		}
	}
	while (tmp_left <= mid) {
		tmp_num[tmp++] = num[tmp_left++];
	}
	while (tmp_right <= right) {
		tmp_num[tmp++] = num[tmp_right++];
	}

	tmp = left;
	while (tmp <= right) {
		num[tmp] = tmp_num[tmp];//不要写成num[tmp++] = tmp_num[tmp++]这样tmp就加了两次
		tmp++;
	}

}



static void divide(int *num,int left,int right,int *tmp_num) {
	if (left >= right) {
		return;
	}
	int mid = left + (right - left >> 1);//找到数组中间的节点 划分数组
	divide(num, left, mid,tmp_num);//左闭右闭区间
	divide(num, mid+1, right, tmp_num);

	merge(num, left, mid,right, tmp_num);
}


void merge_sort(int *num,int len) {
	int* tmp = calloc(len, sizeof(int));
	divide(num, 0, len - 1, tmp);
	free(tmp);
}
void printf_num(int *num,int len){
	for (size_t i = 0; i < len; ++i) {
		printf("%d  ", num[i]);
	}
	printf("\n");
}

void test() {
	int num[] = { 3,546,31,354,3,13,468,43,13,16,4,1 };
	merge_sort(num, ARR_LEN(num));
	printf_num(num,ARR_LEN(num));
}


int main(void) {
//	printf("helloworld!");
	test();

	return 0;
}

二.快速排序

1.单向快速排序

概述

单向快速排序（也称为快速排序）是一种高效的排序算法，其原理可以简要描述如下：

  1. 选择基准值（Pivot）：从待排序数组中选择一个元素作为基准值。通常选择第一个元素、最后一个元素或者随机选择一个元素作为基准值。

  2. 分区（Partition）：将数组中的其他元素按照与基准值的大小关系划分为两个子数组，小于等于基准值的元素放在基准值的左边，大于基准值的元素放在右边。这个过程称为分区操作。

  3. 递归排序：对分区后得到的两个子数组，分别递归地应用上述步骤，直到子数组的大小为 0 或 1，此时子数组已经有序。

  4. 合并：由于快速排序是原地排序算法，因此不需要显式地合并子数组。整个排序过程通过对原数组的就地交换和移动来完成。

单向快速排序的关键在于分区操作，其时间复杂度为O(nlogn)，其中n为待排序数组的长度。这种排序算法的优势在于其原地排序性质和平均情况下较高的性能表现。

原理图：

单项快速排序原理图

代码实现

老师实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <time.h>
#include <stdlib.h>

#define SWAP(arr, i, j) { \
  int tmp = arr[i];   \
  arr[i] = arr[j];    \
  arr[j] = tmp;     \
}

 // 打印数组的函数
void print_arr(int arr[], int left, int right) {
  for (int i = left; i <= right; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

 // 分区核心操作实现,返回一轮快排选择的pivot的下标
int partition(int arr[], int left, int right) {
  // 1.随机选择一个基准值,然后把它先放到数组末尾
  int pivot_idx = left + rand() % (right - left + 1); // 得到一个[left, right]范围内的随机索引
  int pivot = arr[pivot_idx];
  SWAP(arr, pivot_idx, right);

  // 2.设置一个partition_idx索引,指示小于pivot的元素应该插入的位置
  // 同时该索引最终表示分区的界限索引,所以命名为partition_idx
  int partition_idx = left;

  // 3.遍历整个数组,当元素小于pivot时,将它和idx位置元素交换,idx加1
  for (int i = left; i < right; i++) {
    if (arr[i] < pivot) {
      SWAP(arr, i, partition_idx);
      partition_idx++;
    }
  }
  // 4.遍历结束后,将pivot元素(最后一个元素)交换到idx位置
  SWAP(arr, right, partition_idx);

  printf("此一轮分区操作,选择的pivot是: %d\n分区结束后的数组是: ", pivot);
  print_arr(arr, left, right);

  // 5.返回基准值的位置索引
  return partition_idx;
}

/*
* 辅助函数
* 用于对对[left, right]区间中的元素进行递归分区操作
*/
void partition_recursion(int arr[], int left, int right) {
  // 递归出口
  if (left >= right) {
    return;
  }
  // 递归体
  int idx = partition(arr, left, right);  // 分区操作,找到pivot元素的下标位置
  partition_recursion(arr, left, idx - 1);
  partition_recursion(arr, idx + 1, right);
}

void quick_sort_one_way(int arr[], int len) {
  // 初始化随机数生成器,time(NULL)获取当前时间戳
  // 用于生成随机索引
  srand(time(NULL));
  // 调用辅助函数进行递归分解
  partition_recursion(arr, 0, len - 1);
}

int main(void) {
  // 测试单向分区快速排序
  int arr[] = { 8,3,2,6,9,5 };
  quick_sort_one_way(arr, 6);

  return 0;
}

自己实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define SWAP(num,a,b){\
int tmp = num[a];\
num[a] = num[b];\
num[b] = tmp;\
}
#define ARR_LEN(num) (sizeof(num)/sizeof(num[0]))

void print_num(int* num, int len) {
	for (int i = 0; i < len; ++i) {
		printf("%d  ", num[i]);
	}
	printf("\n");
}

static int partition(int num[], int left, int right) {
	//单向 需要进行交换
	//假设选择每次的第一个元素作为枢纽值
	//将枢纽值交换到当前分割数组的末尾，每次同数组末尾的元素进行比较
	//如果比枢纽值小的就和idx（pirovt的下标）交换
	int pirovt = num[left];
	SWAP(num, left, right);

	int pirovt_idx = left;


	for (int i = left; i < right; ++i) {
		if (num[i] < pirovt) {
			SWAP(num, i, pirovt_idx);
			pirovt_idx++;
		}
	}
	//找到当前枢纽的最终坐标位置
	SWAP(num, pirovt_idx, right);
	//print_num(num, 6);
	printf("piovt = %d  \n", pirovt);
	print_num(num, 6);
	return pirovt_idx;
}

//递归分区
static void partition_recursion(int num[], int left, int right) {
	if (left >= right) {
		return;
	}
	int indx = partition(num, left, right);
	partition_recursion(num, left, indx - 1);
	partition_recursion(num, indx + 1, right);
}

void one_way_quick_sort(int num[], int len) {
	partition_recursion(num, 0, len - 1);
}


int main(void) {
	//printf("helloworld!");

	// num[] = { 8,3,2,6,9,5 };
	int num[] = { 8,3,2,6 ,9,5 };
	print_num(num, 6);

	one_way_quick_sort(num, 6);
	return 0;
}

注意在partition_cursion的时候不要调用错递归函数！

2.双向快速排序

双向快速排序是对经典快速排序的改进，它在分区过程中采用了双向扫描的方法，以提高效率。其原理如下：

  1. 选择基准值（Pivot）：与经典快速排序相同，从待排序数组中选择一个元素作为基准值。通常选择第一个元素、最后一个元素或者随机选择一个元素作为基准值。

  2. 双向分区（Bidirectional Partitioning）：将数组中的其他元素按照与基准值的大小关系划分为两个子数组，但与单向快速排序不同的是，双向快速排序采用了两个指针（左指针和右指针）同时从数组的两端向中间扫描。左指针寻找大于等于基准值的元素，右指针寻找小于等于基准值的元素，然后交换它们的位置，直到两个指针相遇。

  3. 递归排序：对分区后得到的两个子数组，分别递归地应用上述步骤，直到子数组的大小为 0 或 1，此时子数组已经有序。

  4. 合并：由于双向快速排序同样是原地排序算法，因此不需要显式地合并子数组。整个排序过程通过对原数组的就地交换和移动来完成。

双向快速排序在分区时减少了比较和交换的次数，因为双向扫描可以同时进行，而不是单向扫描一次完成。这样可以有效地减少排序的时间复杂度。双向快速排序的时间复杂度与经典快速排序相同，为O(nlogn)，其中n为待排序数组的长度。

原理图

双向快速排序原理图

代码实现

老师实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

// 打印数组的函数
void print_arr(int arr[], int left, int right) {
  for (int i = left; i <= right; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

// 双向分区操作函数用于快速排序
int partition(int arr[], int left, int right) {
    // 选择左端元素作为基准值
    int pivot = arr[left];

    // 初始化指针：low 指向数组起始，high 指向数组末尾
    int low = left;
    int high = right;

    // 当 low 和 high 未重合时，执行分区操作
    while (low < high) {
        // 从右向左找到第一个小于基准值的元素
        while (low < high && arr[high] >= pivot) {
            high--;
        }
        // 找到后，将其放到 low 的位置
        arr[low] = arr[high]; // 这里不需要判断 low < high，因为外层循环已保证

        // 从左向右找到第一个大于等于基准值的元素
        while (low < high && arr[low] < pivot) {
            low++;
        }
        // 找到后，将其放到 high 的位置
        arr[high] = arr[low]; // 同样，这里不需要再次判断 low < high
    }

    // 当 low 和 high 重合，确定了基准元素的最终位置，将基准值放回数组中
    arr[low] = pivot;

    // 打印本轮分区后的数组状态，仅为了演示和调试
    printf("此轮分区操作，选择的基准是: %d\n分区结束后的数组是: ", pivot);
    print_arr(arr, left, right); // 假设 print_arr 正确实现

    // 返回基准值的最终位置
    return low;
}

// 对[left, right]区间进行递归分区操作
void partition_recursion(int arr[], int left, int right) {
  // 递归出口
  if (left >= right) {
    return;
  }
  // 递归体
  int idx = partition(arr, left, right);  // 分区操作,找到pivot下标位置
  partition_recursion(arr, left, idx - 1);
  partition_recursion(arr, idx + 1, right);
}

void quick_sort_two_way(int arr[], int len) {
  partition_recursion(arr, 0, len - 1);
}

int main(void) {
  int arr[] = { 8,3,2,6,9,5 };

  // 测试双向分区-快速排序
  quick_sort_two_way(arr, 6);
  return 0;
}

自己实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define SWAP(num,a,b){\
int tmp = num[a];\
num[a] = num[b];\
num[b] = tmp;\
}
#define ARR_LEN(num) (sizeof(num)/sizeof(num[0]))


int partition(int *num,int left,int right) {
	int pirvot = num[left];
	int low = left;
	int high = right;
	while (low < high) {
		while (low < high && num[high] > pirvot) high--;
		num[low] = num[high];
		while (low < high && num[low] < pirvot) low++;
		num[high] = num[low];
	}
	num[low] = pirvot;
	
	return low;
}

void partition_cursion(int *num,int left,int right) {
	if (left >= right) {
		return;
	}
	int idx = partition(num,left,right);
	partition_cursion(num, left, idx - 1);
	partition_cursion(num, idx + 1, right);
}



void quick_sort(int *num,int len) {
	partition_cursion(num, 0, len - 1);
}

void print_num(int* num, int len) {
	for (int i = 0; i < len; ++i) {
		printf("%d  ", num[i]);
	}
	printf("\n");
}



int main(void) {
	//printf("helloworld!");
	int num[] = { 8,3,2,6,9,5 };

	quick_sort(num, ARR_LEN(num));
	print_num(num, ARR_LEN(num));


	return 0;
}

三.堆排序

概述

堆排序是一种基于完全二叉树的排序算法，其原理如下：

  1. 构建最大堆（Max Heap）：将待排序的数组视作一个完全二叉树，并从最后一个非叶子节点开始，从右至左，从下至上地调整每个节点的位置，使得每个节点都满足最大堆的性质——父节点的值大于或等于其子节点的值。这一步称为构建最大堆。

  2. 交换与调整：交换根节点（即数组的第一个元素）与最后一个元素，然后将剩余元素重新调整为最大堆。这样，最大的元素就被放置在数组的末尾位置。接着，重复这一步骤，但是每次将堆的大小减小一，直到整个数组都被排序。

  3. 排序：经过上述步骤，数组中的元素已经按照从小到大的顺序排列。最终的数组即为排序后的结果。

堆排序的关键在于构建最大堆和调整堆的过程。通过构建最大堆，最大的元素被置于根节点，然后将根节点与数组末尾的元素交换，再通过调整堆的方式，将次大的元素置于根节点，如此反复进行，直到整个数组被排序完毕。堆排序的时间复杂度为O(nlogn)，其中n为待排序数组的长度。其优势在于具有稳定的时间复杂度和原地排序的特性。

原理图

堆排序原理图

代码实现

老师实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

#define ARR_SIZE(a) (sizeof(a)/sizeof(a[0]))
#define SWAP(arr, i, j) { \
  int tmp = arr[i];   \
  arr[i] = arr[j];    \
  arr[j] = tmp;     \
}

void print_arr(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

// idx是可能违反大顶堆规则的父结点的下标
// 在一开始idx结点的左右子树必然都是大顶堆
static void heapify(int arr[], int heap_len, int idx) {
  while (1) {
    // 找出idx结点的左右子树,比较,确定最大结点,如果最大结点不是idx那就进行交换操作
    int max_idx = idx;  // 假设父节点就是最大结点
    int lchild_idx = (idx << 1) + 1;  // 左子树的索引
    int rchild_idx = (idx << 1) + 2;  // 右子树的索引

    // 如果左子树存在并且大于最大值
    if (lchild_idx < heap_len && arr[lchild_idx] > arr[max_idx]) {
      max_idx = lchild_idx;
    }

    // 如果右子树存在并且大于最大值
    if (rchild_idx < heap_len && arr[rchild_idx] > arr[max_idx]) {
      max_idx = rchild_idx;
    }

    // 代码运行到这里,就找到了父节点和左右子树结点的最大值
    if (max_idx != idx) {
      // 父节点不是最大值，交换元素
      SWAP(arr, idx, max_idx);
      // max_idx此时发生了元素交换,此结点可能会违反大顶堆的规则
      // 更新idx，继续循环这一过程，直到不再出现元素交换。堆化才全部完成
      idx = max_idx;
    }
    else {
      // 父节点就是最大结点，此时堆化过程全部结束
      break;
    }
  }
}

void build_heap(int arr[], int len) {
  /*
  * 从数组最后一个非叶子结点开始，对每个非叶子结点做堆化处理
  * (最后一个非叶子结点向前遍历到数组首元素，过程中的结点都是非叶子结点)
  * 也就是自下而上处理所有的非叶子结点, 使得所有非叶子结点都符合大顶堆的规则
  * 这样整个数组就会构建成为一个大顶堆
  *
  * 那么最后一个非叶子结点的元素下标是多少呢?
  * 假设最后一个非叶子结点,它的索引是i
  * 那么它至少有一颗左子树,左子树的索引是2i + 1
  * 数组索引的取值范围是[0, len - 1]
  * 2i + 1 <= len - 1
  * i <= (len - 2) / 2
  * 所以数组中最后一个非叶子结点的下标就是(len - 2) / 2
  */
  int last_idx = len - 2 >> 1;
  for (int i = last_idx; i >= 0; i--) {
    heapify(arr, len, i);
  }
  print_arr(arr, len);
}

void heap_sort(int arr[], int len) {
  // 1.将原数组构建成一个大顶堆
  build_heap(arr, len);

  // 2.反复移除堆顶元素, 并重建大顶堆
  int heap_len = len; // 堆的逻辑大小,一开始将整个数组当成一个大顶堆
  // 只要堆的逻辑大小大于1, 就需要重复堆排序的过程
  while (heap_len > 1) {
    // 交换堆逻辑上的首尾元素
    SWAP(arr, 0, heap_len - 1);
    heap_len--;   // 堆逻辑大小减1
    // 重构大顶堆
    /*
    * 此函数的三个参数：
    * 1.arr是作为大顶堆的数组
    * 2.heap_len决定数组中哪部分元素作为大顶堆处理
    * 3.0是堆逻辑上的根结点,由于每次堆顶元素都会交换改变
    * 所以在堆排序的过程中，只有此元素的存在可能会违反大顶堆的规则
    * 也就是说该索引是堆化过程中可能需要处理的结点的索引
    */
    heapify(arr, heap_len, 0);
    print_arr(arr, len);
  } // while结束时,heap_len = 1,堆排序结束
}

int main(void) {
  int arr[] = { 4, 10, 3, 5, 1 };
  int len = ARR_SIZE(arr);
  print_arr(arr, len);

  heap_sort(arr, len);
  return 0;
}

自己实现

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SWAP(num,a,b){\
int tmp = num[a];\
num[a] = num[b];\
num[b] = tmp;\
}
#define ARR_LEN(num) (sizeof(num)/sizeof(num[0]))

void print_num(int* num, int len) {
	for (int i = 0; i < len; ++i) {
		printf("%d  ", num[i]);
	}
	printf("\n");
}

void heapify(int *num,int heap_len,int idx) {
	while (1) {
		int i = idx;
		int left_child = (i << 1) + 1;
		int right_child = (i << 1) + 2;
		//找到左右子树

		//开始建堆
		//假设父节点是值最大的节点
		if (left_child < heap_len && num[i] < num[left_child]) {
			i = left_child;
		}
		if (right_child < heap_len && num[i] < num[right_child]) {
			i = right_child;
		}
		if (i != idx) {
			SWAP(num, i, idx);
			idx = i;
		}
		else {
			break;
		}
	}
}


void build_heap(int *num,int len) {
	int i = len - 2 >> 1;//第一个不是叶子节点的节点
	while (i >= 0) {
		heapify(num, len, i);
		i--;
	}
}


void heap_sort(int *num,int len) {
	build_heap(num,len);

	int heap_len = len-1;
	while (heap_len>0) {
		heapify(num, heap_len, 0);//每次只有堆顶元素变了，所以从堆顶开始堆化
		SWAP(num, 0, heap_len);
		heap_len--;
	}
}


int main(void) {
	//printf("helloworld!");
	int arr[] = { 4, 10, 3, 5, 1 };
	int len = ARR_LEN(arr);
	print_num(arr, len);

	heap_sort(arr, len);
	print_num(arr, len);



	return 0;
}

注意在heap_sort函数中，调用heapift函数的时候，每次传入的是堆顶的元素，因为每次都是堆顶与堆最后一个元素交换，所以每轮循环需要调正的就是堆顶的元素