经典排序算法二（选择排序、堆排序）
2017-09-01 本文已影响0人
头像是我老婆
过年的时候大家聚在一起打扑克，从两副混合扑克中挑选出完整的一副。一般我会按照一定的顺序来找。
- ♣，从A到K。
- ♥，从A到K。
- ♦，从A到K。
- ♠，从A到K。
- 再找到大小王就算一副找全了。
这其实也可以说是选择排序了，每次挑选出某种花色最小的一个，然后第二小的。。。一直找到K。
正文
选择排序(Selection sort）
- 算法描述
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
初始值： {49 27 65 97 76 12 38}
第一趟：12 {27 65 97 76 49 38}
第二趟：12 27 {65 97 76 49 38}
第三趟：12 27 38 {97 76 49 65}
第四趟：12 27 38 49 {76 97 65}
第五趟：12 27 38 49 65 {97 76}
第六趟：12 27 38 49 65 76 97 {}
- 算法实现
void selectSort(int *a ,int num) {
for (int i = 0; i < num - 1; i++) {
int index = i;
for (int j = i + 1; j < num; j++) {
if (a[j] < a[index]){
index = j; // 记录位置
}
}
if (index != i) { //如果最小数位置变化则交换
int temp = a[index];
a[index] = a[i];
a[i] = temp;
}
}
}
堆排序（Heap Sort）
- 堆
在接触“堆”这个概念之前，看到“堆”首先想到的就是“堆内存”的“堆”。。。
根据堆-百度百科的资料，堆必须同时具备两个特性:
1．堆总是一棵完全二叉树。
2．堆中某个节点的值总是不大于或不小于其父节点的值。
由于其它几种堆（二项式堆，斐波纳契堆等）用的较少，一般将二叉堆就简称为堆。 - 堆排序
以如下无序数组A为例
| 4 | 5 | 3 | 2 | 6 | 1 |
|---|
-
将该数组按顺序排列为完全二叉树（堆特性1）
数组的二叉树表示
A[i]的左节点为A[2i+1],右节点为A[2i+2]，父节点为A[i/2]。从数组索引的角度描述了数字与数字在二叉树中的位置关系。
-
一个数组想用堆排序，首先要把数组堆化（堆特性2）
20160917105502853.gif
