(五)选择排序:简单选择排序,堆排序
所谓选择嘛就是从待排序的元素中先选个最大的或最小的出来放一边,然后重复同样的操作.
简单选择排序就是遍历那些未排序的元素,而堆排序则是利用大堆或小堆从中选择最大或最小值,因为大堆堆顶值就是最大值(小堆堆顶是最小值).
简单选择排序:
void SimpleSelectSort(int* arr, int len)
{
int tmp;
int maxValIndex;
for(int i = len - 1; i >0; i--)
{
maxValIndex = i;
for(int j = 0; j < i; j++)
{
if(arr[j] > arr[maxValIndex])
maxValIndex = j;
}
tmp = arr[maxValIndex];
arr[maxValIndex] = arr[i];
arr[i] = tmp;
}
}
简单选择排序实际上跟冒泡排序蛮像,每遍历一次选出个最大的来,只不过选择排序不用去交换相邻的元素,直到找到了最大值,交换那一个元素就行.
堆排序
堆是一棵完全二叉树,如果父结点大于等于子结点则叫大堆,父结点小于等于子结点叫小堆.这里我们使用大堆来进行堆排序(用小堆也是可以的).
堆的逻辑结构虽然是树结构,但物理结构可以是一个数组.各结点索引间的关系是:假如父结点索引为index,则左孩子索引为index*2 + 1;右孩子索引为index*2 + 2;
根结点自然是第一个,索引为0.
首先把待排序的数组建成一个大堆,则索引为0的元素是最大值,然后把它与最后一个元素交换.使数组缩短1,然后重新建堆,则索引为0的元素又是最大值.所以堆排序的思想跟简单选择排序是一样的,就是从未排序的元素中挑出最大的,只不这里是利用建立一个大堆来得到最大值.
//调整堆,假如堆中只有一个元素变动,则通过调整又生成一个堆
//通过父结点与孩子结点比较如果小于子结点则交换位置.这里说的调整实际上指的是调整父结点
void LargeHeapAdjust(int* arr, int index, int len)
{
int lChild = index*2 + 1;
int rChild = index*2 + 1;
int fatherIndex = index;
int tmp;
//如果索引大于len/2 - 1则必是孩子结点了.因为假如有这样的父结点(len/2)的话.则它的左孩子是len + 1.已经超出了数组范围
if(index <= len/2 - 1) {
if(lChild < len && arr[lChild] > arr[max])
fatherIndex= lChild;
if(rChild < len && arr[rChild] > arr[max])
fatherIndex= rChild;
if(fatherIndex!= index)
{
tmp = arr[index];
arr[index] = arr[max];
arr[max] = tmp;
LargeHeapAdjust(arr, max, len);
}
}
}
//创建大堆
void CreateLargeHeap(int* arr, int len)
{
for(int i = len/2 - 1; i >= 0; i--)
LargeHeapAdjust(arr, i, len); //针对每一个非叶子结点做一次调整
}
void HeapSort(int* arr, int len)
{
int i;
int tmp;
CreateLargeHeap(arr, len); //排序前最建立一个大堆
for( i = len - 1; i >= 1; i --) //这里跟简单选择排序一样,从后往前遍历,找个最大值出来.堆根结点arr[0]就是最大值
{
tmp = arr[i];
arr[i] = arr[0];
arr[0] = tmp;
LargeHeapAdjust(arr, 0, i); //索引为0的根结点变动了,需要调整重建堆.
}
}