Contents
  1. 1. 直接选择排序(不稳定)
  2. 2. 堆排序(Heapsort)
    1. 2.1. “堆”定义
    2. 2.2. 堆的高度
    3. 2.3. 堆排序思想
    4. 2.4. 特点
    5. 2.5. 堆排序与直接选择排序的区别
    6. 2.6. 算法分析

选择排序是指在每次排序时,选择最大或者最小项,将其放入适当的位置上,反复操作,直到所有数据排序完成为止。选择排序是一类比较常见的排序,现实生活中也比较常见,比如一个班级的学生排队,先将最高的学生排到队首,然后在其他学生中再挑出最高的一个,排在第二的位置,以此类推,直到全部排完。

选择排序的交换操作介于 0 和 ( n - 1 ) 次之间。选择排序的比较操作为 n ( n - 1 ) / 2 次之间。选择排序的赋值操作介于 0 和 3 ( n - 1 ) 次之间。 比较次数O( n^2 ),比较次数与关键字的初始状态无关,总的比较次数N=(n-1)+(n-2)+…+1=n*(n-1)/2。 交换次数O(n),最好情况是,已经有序,交换0次;最坏情况是,逆序,交换n-1次。 交换次数比冒泡排序少多了,由于交换所需CPU时间比比较所需的CPU时间多,n值较小时,选择排序比冒泡排序快。

直接选择排序(不稳定)

直接选择排序
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void SelectSort(elemtype R[], int n)
{
int i, j, m;
elemtype t;
for(i=0; i<n-1; i++)
{
m = i;
for(j = i+1; j < n; j++)
{
if(R[j] < R[m])
m = j;
}
if(m != i)
{
t = R[i];
R[i] = R[m];
R[m] = t;
}
}
}

堆排序(Heapsort)

“堆”定义

树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

堆的高度

堆可以被看成是一棵树,结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目;定义堆的高度为树根的高度。我们将看到,堆结构上的一些基本操作的运行时间至多是与树的高度成正比,为O(lgn)。

堆排序思想

堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
(1)用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。
……

直到无序区只有一个元素为止。
(2)大根堆排序算法的基本操作:
① 初始化操作:将R[1..n]构造为初始堆;
② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
注意:
①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。 ②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。

特点

堆排序(HeapSort)是一树形选择排序。堆排序的特点是:在排序过程中,将R[l..n]看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构),在当前无序区中选择关键字最大(或最小)的记录

堆排序与直接选择排序的区别

直接选择排序中,为了从R[1..n]中选出关键字最小的记录,必须进行n-1次比较,然后在R[2..n]中选出关键字最小的记录,又需要做n-2次比较。事实上,后面的n-2次比较中,有许多比较可能在前面的n-1次比较中已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果,可减少比较次数。

算法分析

堆排序的时间,主要由建立初始堆和反复重建堆这两部分的时间开销构成,它们均是通过调用Heapify实现的。堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多,所以堆排序不适宜于记录数较少的文件。堆排序是就地排序,辅助空间为O(1),它是不稳定的排序方法。

堆排序c语言实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//C语言描述
// array是待调整的堆数组,i是待调整的数组元素的位置,nlength是数组的长度
void HeapAdjust(int array[],int i,int nLength)//本函数功能是:根据数组array构建大根堆
{
int nChild;
int nTemp;
for (nTemp = array[i]; 2 * i + 1 < nLength; i = nChild)
{
// 子结点的位置=2*(父结点位置)+ 1
nChild = 2 * i + 1;
// 得到子结点中较大的结点
if (nChild < nLength - 1 && array[nChild + 1] > array[nChild])
++nChild;
// 如果较大的子结点大于父结点那么把较大的子结点往上移动,替换它的父结点
if (nTemp < array[nChild])
{
array[i]= array[nChild];
}
else // 否则退出循环
{
break;
}
// 最后把需要调整的元素值放到合适的位置
array[nChild]= nTemp;
}
}
// 堆排序算法
void HeapSort(int array[],int length)
{
// 调整序列的前半部分元素,调整完之后第一个元素是序列的最大的元素
for (int i = length / 2 - 1; i >= 0; --i)
{
HeapAdjust(array,i,length);
}
// 从最后一个元素开始对序列进行调整,不断的缩小调整的范围直到第一个元素
for (int i = length - 1; i > 0; --i)
{
// 把第一个元素和当前的最后一个元素交换,
// 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
Swap(&array[0],&array[i]);
// 不断缩小调整heap的范围,每一次调整完毕保证第一个元素是当前序列的最大值
HeapAdjust(array,0,i);
}
}
堆排序算法(c++描述)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
//堆排序算法(C++描述)
#define MAX 100//数据元素的最大个数
typedef struct
{
int r[MAX];
int length;
}SqList;//定义一个线性表用于存放数据元素
void HeapAdjust(SqList &L,int s,int m)
{
//已知L.r[s...m]中记录除L.r[s]外均满足堆的定义,本函数用于使L.r[s...m]成为一个大顶堆
int j;
int e=L.r[s];
for(j=2*s;j<=m;j*=2)
{
if(j<M&&L.R[J]<L.R[J+1]) ++j;
if(e>=L.r[j]) break;
L.r[s]=L.r[j];
s=j;
}
L.r[s]=e;
}
void HeapSort(SqList &L)
{
//对顺序表L进行堆排序
int i,e;
for(i=L.length/2;i>0;i--)
HeapAdjust(L,i,L.length);
for(i=L.length;i>1;i--)
{
//将大顶堆的顶记录和最后一个记录相互交换
e=L.r[1];
L.r[1]=L.r[i];
L.r[i]=e;
HeapAdjust(L,1,i-1);
}
}

下一节更新基数排序。

Contents
  1. 1. 直接选择排序(不稳定)
  2. 2. 堆排序(Heapsort)
    1. 2.1. “堆”定义
    2. 2.2. 堆的高度
    3. 2.3. 堆排序思想
    4. 2.4. 特点
    5. 2.5. 堆排序与直接选择排序的区别
    6. 2.6. 算法分析