堆排序思路:在筛选Sift的过程中,我们不必每一个结点都要筛选,而是从最后一个非叶子结点(n/2向上取整)到根结点(1)进行调整生成一个最大堆。
筛选就是从一个结点a出发,先比较这个结点a的左右孩子b c,如果有比其大的结点,交换假设结点c大,那么将a结点的值调整为c结点的值,接着以c为结点,继续向下比较,逐层递推下去,最多可能一直调整到树叶。
筛选的最后一步就是你调整完结点值后,将原结点的值赋给最后一次调换时的子结点,这样就完成了一次筛选动作。
可以比喻成:过筛子,较小的数就筛下去,而较大的数就一层层地选择上来
ASCII码的转换:int 和 char 是可以互相转换的 ,输入int型保存在char型中,输出的就是int型ASCII码对应的char型,反之亦然
本题思路:将char型字符串保存至int型数组中,并且进行最小堆排序,最后保存在char型数组中输出。
筛选代码方法一:
void siftdown(int i) {int t, flag = 0;//标记 =1时表示结点已经遍历过while (i * 2 <= n && flag == 0) {if (h[i] < h[i * 2])t = i * 2;elset = i;if (i * 2 + 1 <= n) {if (h[t] < h[i * 2 + 1])t = i * 2 + 1;}if (t != i) {swap(t, i);//交换i = t;}elseflag = 1;}return;}
本题代码(筛选代码方法二):
#include<iostream>using namespace std;const int maxsize = 100;typedef int datatype;typedef struct {datatype key;}rectype;typedef rectype list[maxsize + 1];void HeadSort(list R, int n);int main() {int num = 0, i=0;char c;char d[101];list R;while (scanf("%c", &c) != EOF && c != '\n') {num++;i++;R[i].key = c;}HeadSort(R, num);for (int i = 1; i <= num ; i++) {d[i] = R[i].key;}for (int i = 1; i <= num; i++) {cout << d[i];}}void Sift(list R, int p, int q) {int i, j;R[0] = R[p];i = p;j = 2 * i;//指向i的左孩子while (j <= q) {if (j < q && R[j].key < R[j + 1].key) j++;if (R[0].key >= R[j].key) break;R[i] = R[j];i = j;j = 2 * i;R[i] = R[0];}}void HeadSort(list R, int n) {int i;for (i = n / 2; i >= 1; i--)Sift(R, i, n);//初始化堆for (i = n; i >= 2; i--) {R[0] = R[1]; R[1] = R[i]; R[i] = R[0];//交换一次确定一个数Sift(R, 1, i - 1);}}
