//SelectionSort.h
#ifndef _SELECTIONSORT_H_ #define _SELECTIONSORT_H_ #include <stdlib.h> #include <stdio.h> #include <time.h> #define SIZE 15 typedef int Element; typedef Element ListType[SIZE]; void CreateRandom(ListType List, int n); void print(ListType List, int n); //简单选择排序 void SimpleSort(ListType List, int n); //堆排序 void HeapSort(ListType List, int n); #endif //_SELECTIONSORT_H_ //SelectionSort.c #include "SelectionSort.h" void CreateRandom(ListType List, int n) { int i = 0; srand((unsigned)time(NULL)); for(i = 0; i < n; ++i) { List[i] = rand() % 0x7F; } } void print(ListType List, int n) { int i = 0; for(i = 0; i < n; ++i) { printf("%d\t", List[i]); } printf("\n"); } static void Swap(Element *a, Element *b) { Element Temp = *b; *b = *a; *a = Temp; } /********************************************************* 首先选定一个位置作为最小元素的下标位置，从此位置以外寻找比此位置 存在更小元素的位置，一趟下来最小的元素的位置就位于了数组的最左端， 第二趟下来，第二小的就在了数组的左端第二个位置............. 全部n-1趟下来排序完成 *********************************************************/ void SimpleSort(ListType List, int n) { int i = 0, j = 0, MiniPos = 0; for(i = 0; i < n-1; ++i) { MiniPos = i; //选定i为最小值 for(j = i+1; j < n; ++j) //寻找最小元素所在的位置 { if (List[MiniPos] > List[j]) { MiniPos = j; } } if( i != MiniPos ) //找到了更小元素所在位置 Swap(&List[i], &List[MiniPos]); } } /*************************************************************** 堆排序是利用堆的特点:堆顶元素一定是极值(极大值或是极小值)的特点， 每次取堆顶元素，然后再将剩下的元素再一次组成一个堆，再次取堆顶元 素，如此循环直到堆顶无元素则排序完成。 堆的定义:将堆看作一颗完全二叉树，并且用一个一位数组存储这个完全 二叉树，则有完全二叉树上任意一个非叶子节点的值均不大于(或不小于) 其左、右孩子的值 大项堆:完全二叉树上任意一个非叶子节点的值不小于其左、右孩子的值 小项堆:完全二叉树上任意一个非叶子节点的值不大于其左、右孩子的值 升序排序:使用大项堆(因为每次取得的极值是数组中最末一个元素，且 最末元素是由堆顶的极值交换而来) 降序排序:使用小项堆 ***************************************************************/ static void Adjust(ListType List, int pos, int n) //调整为大项堆 { int Child = 0, Parent = 0; Element Temp = List[pos]; //保存待调整节点值，以备交换 Parent = pos; Child = 2 * Parent + 1; //使Child指向Parent的左孩子 while (Child < n) //存在左孩子则循环向下调整,值大的节点向上移动，值小的节点下沉，以满足堆定义 { if( Child + 1 < n && List[Child + 1] > List[Child] ) //存在右孩子且右孩子的值更大 Child++; //使Child指向右孩子 if( Temp >= List[Child] ) //父节点已经大于存在的孩子节点(注意不能是List[Parent] > List[Child],除非使用的是方式是直接交换父子节点) break; //能到此处说明父节点必然小于存在的孩子节点 List[Parent] = List[Child]; //用孩子节点替换父节点，使这个非叶子节点不小于其存在的孩子 Parent = Child; //继续向下调整 Child = 2 * Parent + 1; } List[Parent] = Temp; //在叶子节点上恢复 } void HeapSort(ListType List, int n) { int pos = 0, i = 0; Element Temp; if( n <= 1 ) return ; pos = (n - 1) / 2; //从最后一个非叶子节点开始向上调整 while (pos >= 0) //创建堆 { Adjust(List, pos, n); pos--; } for(i = 0; i < n; ++i) //循环取堆顶元素到数组无序部分末位置，以对数组进行排序 { Temp = List[0]; //保存堆顶元素 List[0] = List[n - i -1]; //使用当前次的末尾元素覆盖堆顶元素 List[n - i - 1] = Temp; //将堆顶元素放在末尾 Adjust(List, 0, n - i - 1); //使用剩下的元素再次组成堆 } }main.c #include "SelectionSort.h" int main(int argc, char **argv) { ListType List ={ 0 }; int n = sizeof(List) / sizeof(Element); CreateRandom(List, n); printf("排序前\n"); print(List, n); //SimpleSort(List, n); HeapSort(List, n); printf("排序后\n"); print(List, n); system("pause"); return 0; }
