简单选择排序（直接选择排序）：
基本思路：
第一次从A[0..n-1]中选取最小值，与A[0]交换；
第二次从A[1..n-1]中选取最小值，与A[1]交换；
第i次从A[i-1..n-1]中选取最小值，与A[i-1]交换，
......
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
实现代码：(C#)
static void SelectSort(int[] array)
{
int pos; //用于记录的下标
for (int i = 0; i < array.Length - 1; i++)
{
pos = i;
for (int j = i + 1; j < array.Length; j++)//从第二个下标开始，遍历后面所有的数
{
//比pos小，则记录下标，直到遍历完，找到最小值
if (array[j] < array[pos]) pos = j;
}
if (pos != i) //交换操作
{
int temp = array[i];
array[i] = array[pos];
array[pos] = temp;
}
}
}
总结：
1、若初始对象是有序的，则对象移动次数为0，达到最小；但比较次数还是多，且与初始对象排列无关；时间效率：O(n²)
堆排序：
什么是堆：
一个k[0]到k[n-1]的序列满足以下条件称为堆
将该序列顺次排成一棵完全二叉树，则此树的特点是：
树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。
如何建堆：
步骤：从最后一个非终端结点开始往前逐步调整，让每个双亲大于（或小于）子女，直到根结点为止。（终端节点即叶子，没有任何子女）；
根据性质，最后非终端节点下标必为 (n-1)/2 。
例：关键字序列T= (21，25，49，25*，16，08），请建大根堆。
解：为便于理解，先将原始序列画成完全二叉树的形式：
这样可以很清晰地从 (n-1)/2 开始调整。
怎样进行堆排序：
方法：将当前顶点与堆尾记录交换，然后仿建堆动作重新调整，如此反复直至排序结束。
例：对刚建好的大根堆进行排序：
动画演示
代码实现：(C#)
创建堆：
//创建堆
//n为需要建堆的元素个数，root_index为传入的非叶结点下标
public static void CreateHeap(int[] nums, int n, int root_index)
{
int i, j;
int temp;
i = root_index;
j = 2 * i + 1; //左子结点下标
temp = nums[i];
while (j < n)
{
if (j < n - 1 && nums[j] < nums[j + 1]) j++; //获取左右叶结点中最大的一个
//因为初始化是从下往上创建，下面已经满足堆的状态，
//所以遇到父节点大于叶结点直接退出循环即可
if (temp > nums[j])
{
break;
}
else
{
//继续往下比较
nums[i] = nums[j];
i = j;
j = 2 * j + 1;
}
}
nums[i] = temp;
}
初始化堆：
public static void InitHeap(int[] nums)
{
//从最后一个非叶结点开始往前，一直到根节点
for (int i = (nums.Length - 1) / 2; i >= 0; i--)
{
CreateHeap(nums, nums.Length, i);
}
}
堆排序实现：
public static void HeapSort(int[] nums)
{
int temp;
InitHeap(nums);
for (int i = nums.Length - 1; i > 0; i--)
{
//根节点与最后一个叶结点交换
temp = nums[0];
nums[0] = nums[i];
nums[i] = temp;
CreateHeap(nums, i, 0);
}
}
总结：
1、时间效率： O(nlog2n)。因为整个排序过程中需要调用n-1次堆顶点的调整，而每次堆排序算法本身耗时为log2n
2、优点：对小文件效果不明显，但对大文件有效。
网友评论