选择排序&&堆排序
1.选择排序：
介绍：选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
步骤：假设数组array长度为N即有数组内有N个数据未排序数据
1.第一趟遍历将这N个数据中最小的数据和array[0]交换。
2.第二趟则遍历N-1个数据，将这N-1个数据中最小的和array[1]交换(第二趟中的数组是从原数组中的array[1]开始即排除第一趟中最小的数据再进行交换)。
...
程序实现：
方法1：每趟选择最小数据进行交换
void SelectSort(int* _array, size_t _arraySize)
{
assert(_array&&_arraySize);
for (size_t i = ;i < _arraySize;++i)
{
int MinIndex = i;//记录首位置下标
for (size_t j = i + ;j < _arraySize;++j)
{
if (_array[MinIndex] > _array[j])//比较首位置之后的各个元素并将最小数据的下标赋给MinIndex
MinIndex = j;
}
//if (MinIndex != i)//防止首元素即最小时进行交换,减少不必要开销
swap(_array[MinIndex], _array[i]);
}
return;
}
方法2：与方法一类似，进行了优化，每趟将最小数据置首，将最大元素置尾
void SelectSort_optimize(int* _array, int _arraySize)
{
assert(_array&&_arraySize); int left = ;
int right = _arraySize - ;
for (;left <= right;++left,--right)//每一趟找到最大值和最小值减少循环次数
{
int MinIndex = left;
int MaxIndex = right;
for (int index = left;index <= right;++index)//此时数组为闭区间，与未优化时存在差异
{
if (_array[MinIndex] > _array[index])
MinIndex = index;
if (_array[MaxIndex] < _array[index])
MaxIndex = index;
}
if (left != MinIndex)
{
swap(_array[left], _array[MinIndex]);
if (left == MaxIndex)//避免如果最大值为_array[left]时，将被上一步操作移到_array[MinIndex]后出错
MaxIndex = MinIndex;//将MaxIndex更新
}
if (right != MaxIndex)
swap(_array[right], _array[MaxIndex]);
}
return;
}
效率分析：
算法稳定性：不稳定
时间复杂度：O(n^2)
空间复杂度：O(1)
2.堆排序
介绍：堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大堆和小堆，是完全二叉树。升序排序时使用大堆，降序排序时使用小堆。
步骤：对数组_array进行升序排序,假设数组array长度为N即有数组内有N个数据未排序数据
1：将_array中的N个数据构成大堆后，此时最大值即为_array[0]，然后将_array[0]与_array[N-1]交换。
2：除_array[N-1]外，其余数据继续建立大堆后，此时最大值仍为_array[0],然后将_array[0]与_array[N-2]交换。
...
根据下面网址演示可以清楚理解堆排序的过程
http://www.tyut.edu.cn/kecheng1/site01/suanfayanshi/heap_sort.asp
程序实现：
void AdjustDown(int* _arr,size_t ParIndex,int _arrSize)//从父节点开始向下调整
{
size_t ChildIndex = ParIndex * + ;//找出父节点的左子树下标 while (ChildIndex < _arrSize)
{
if ((_arr[ChildIndex] < _arr[ChildIndex + ]) && ((ChildIndex + ) < _arrSize))//找出父节点的左右子树中的较大值的下标
ChildIndex++;
if (_arr[ParIndex] < _arr[ChildIndex])
{
swap(_arr[ParIndex], _arr[ChildIndex]);//如果父节点数据小于子节点数据则交换
ParIndex = ChildIndex; //继续调整交换后的子树，保证堆中任意子树均为大堆
ChildIndex = ParIndex * + ;
}
else//如果_arr[ParIndex] > _arr[ChildIndex]则说明其已经为大堆且子树也为大堆，跳出循环
break;
}
}
void HeapSort(int* _array, int _arraySize)
{
assert(_array&&_arraySize > );
//建堆
for (int i = _arraySize / - ;i >= ;--i)//从最后一个非叶子节点开始向下调整直到根节点调整完
AdjustDown(_array, i, _arraySize); for (int j = _arraySize - ;j > ;--j)
{
swap(_array[], _array[j]);
AdjustDown(_array, ,j);
}
return;
}
下面是当数组为{3,12,24,2,6}时的排序过程
效率分析：
算法稳定性：不稳定
时间复杂度：O(n^lg n)
空间复杂度：O(1)