选择排序法
选择排序法
选择排序的基本思想是：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i 个记录。我们主要介绍简单选择排序、树型选择排序和堆排序。
简单选择排序的基本思想：第i 趟简单选择排序是指通过n-i 次关键字的比较，从n-i+1个记录中选出关键字最小的记录，并和第i 个记录进行交换。共需进行i-1趟比较，直到所有记录排序完成为止。例如：进行第i 趟选择时，从当前候选记录中选出关键字最小的k 号记录，并和第i 个记录进行交换。图9.5给出了一个简单选择排序示例，说明了前三趟选择后的结果。图中大括号内为当前候选记录，大括号外为当前已经排好序的记录。
｛ 48 62 35 77 55 14 35 98 ｝ ↑ ↑ i k 14 ｛ 62 35 77 55 48 35 98 ｝ ↑ ↑
i k 14 35 ｛ 62 77 55 48 35 98 ｝ ↑ ↑ i k 14 35 35 ｛ 77 55 48 62 98 ｝ ↑ ↑ i k 选择排序示例 简单选择排序的算法具体描述如下：
void SelectSort(RecordType r[], int length) /* 对记录数组r 做简单选择排序，length 为数组的长度 */ { n=length; for ( i=1 ; i
{ k=i； for ( j=i+1 ; j
编辑本段[编辑本段]算法
简单选择排序算法分析：在简单选择排序过程中，所需移动记录的次数比较少。最好情况下，即待排序记录初始状态就已经是正序排列了，则不需要移动记录。最坏情况下，即待排序记录初始状态是按逆序排列的，则需要移动记录的次数最多为3（n-1）。简单选择排序过程中需要进行的比较次数与初始状态下待排序的记录序列的排列情况无关。当i=1时，需进行n-1次比较；当i=2时，需进行n-2次比较；依次类推，共需要进行的比较次数是∑ =(n-1)+(n-2)+…+2+1=n(n-1)/2，即进行比较操作的时间复杂度为O(n2)。
选择排序法 是对 定位比较交换法 的一种改进。在讲选择排序法之前我们先来了解一下定位比较交换法。为了便于理解，设有10个数分别存在数组元素a[0]～a[9]中。定位比较交换法是由大到小依次定位a[0]～a[9]中恰当的值（和武林大会中的比武差不多），a[9]中放的自然是最小的数。
如定位a[0],先假定a[0]中当前值是最大数，a[0]与后面的元素一一比较，如果a[4]更大，则将a[0]、a[4]交换，a[0]已更新再与后面的a[5]～a[9]比较，如果a[8]还要大，则将a[0]、a[8]交换，a[0]又是新数，再与a[9]比较。一轮比完以后，a[0]就是最大的数了，本次比武的武状元诞生了，接下来从a[1]开始，因为状元要休息了，再来一轮a[1]就是次大的数，也就是榜眼，然后从a[2]开始，比出探花，真成比武大会了，当比到a[8]以后，排序就完成了。
下面给大家一个例子：
main()
{
int a[10];
int i,j,t;
for ( i = 0; i
for ( i = 0; i
for ( j = i + 1; j
if ( a[ i ]
for( i = 0; i
}
好啦，啰嗦了半天总算把定位比较排序法讲完了，这个方法不错，容易理解，就是有点麻烦，一把椅子换来换去，哎～
所以就有了下面的选择排序法，开始的时候椅子谁也不给，放在一边让大家看着，找个人k 记录比赛结果，然后发椅子。具体来讲呢就是，改进定位比较排序法，但是这个改进只是一部分，比较的次数没变，该怎么打还是怎么打，就是不用换椅子了。每次外循环先将定位元素的小标i 值记录到K ，认为a[k]是最大元素其实k=i还是a[ i ]最大，a[k]与后面的元素一一比较，该交换的也是也不换，就是把K 的值改变一下就完了，最后在把a[k]与a[ i ]交换，这样a 就是最大的元素了。然后进入下一轮的比较。选择排序法与定位比较排序法相比较，比的次数没变，交换的次数减少了。
简单插入排序法:
1 5 7 3 1 6
把表分成两部分，前半部分已排序，后半部分未排序，我用|分开
初始为 5 | 1 7 3 1 6
一次插入排序，把第一个1插入前边已排序部分，得
1 5 | 7 3 1 6
后边依次是
1 5 7 | 3 1 6
1 3 5 7 | 1 6
1 1 3 5 7 | 6
1 1 3 5 6 7 |
希尔排序基本思想：
先取一个小于n 的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2
该方法实质上是一种分组插入方法。
给定实例的shell 排序的排序过程
假设待排序文件有10个记录，其关键字分别是：
49，38，65，97，76，13，27，49，55，04。
增量序列的取值依次为：
5，3，1
编辑本段介绍
希尔排序(缩小增量法)
属于插入类排序, 是将整个无序列分割成若干小的子序列分别进行插入排序 排序过程：先取一个正整数d1
初始：d ＝5
49 38 65 97 76 13 27 49* 55 04
49 13
|-------------------|
38 27
|-------------------|
65 49*
|-------------------|
97 55
|-------------------|
76 04
|-------------------|
一趟结果
13 27 49* 55 04 49 38 65 97 76
d=3
13 27 49* 55 04 49 38 65 97 76
13 55 38 76
|------------|------------|------------|
27 04 65
|------------|------------|
49* 49 97
|------------|------------|
二趟结果
13 04 49* 38 27 49 55 65 97 76
d=1
13 04 49* 38 27 49 55 65 97 76
|----|----|----|----|----|----|----|----|----|
三趟结果
04 13 27 38 49* 49 55 65 76 97
--------------------------------------------------------------------------------------------
例如对503,17,512,908,170,897,275,653,462，154，509，612，677，765，703，94排序的C 语言算法
================================================
功能：希尔排序
输入：数组名称（也就是数组首地址）、数组中元素个数
================================================
*/
/*
====================================================
算法思想简单描述：
在直接插入排序算法中，每次插入一个数，使有序序列只增加1个节点， 并且对插入下一个数没有提供任何帮助。如果比较相隔较远距离（称为 增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除 多个元素交换。D.L.shell 于1959年在以他名字命名的排序算法中实现 了这一思想。算法先将要排序的一组数按某个增量d 分成若干组，每组中 记录的下标相差d. 对每组中全部元素进行排序，然后再用一个较小的增量 对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成
一组，排序完成。
下面的函数是一个希尔排序算法的一个实现，初次取序列的一半为增量， 以后每次减半，直到增量为1。
希尔排序是不稳定的。
Shell 排序
Shell 排序的算法实现:
1． 不设监视哨的算法描述
void ShellPass(SeqList R，int d)
{//希尔排序中的一趟排序，d 为当前增量
for(i=d+1;i
if(R[ i ].key
R[0]=R;j=i-d； //R[0]只是暂存单元，不是哨兵
do {//查找R 的插入位置
R[j+d]=R[j]； //后移记录
j=j-d； //查找前一记录
}while(j>0&&R[0].key
R[j+d]=R[0]； //插入R 到正确的位置上
} //endif
编辑本段算法分析
1．增量序列的选择
Shell 排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值) 互为倍数的情况。
有人通过大量的实验，给出了目前较好的结果：当n 较大时，比较和移动的次数约在nl.25到1.6n1.25之间。
2．Shell 排序的时间性能优于直接插入排序
希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。
②当n 值较小时，n 和n2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di 逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。
因此，希尔排序在效率上较直接插人排序有较大的改进。
编辑本段稳定性
希尔排序是不稳定的。
选择排序
选择排序的基本思想是：
对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，...... ，第i 遍处理是将L 中最小者与L 交换位置。这样，经过i 遍处理之后，前i 个记录的位置就已经按从小到大的顺序排列好了。
例1:输入序列数据按非减顺序输出.
程序1(pascal)如下:
program xzpx_1;
var
a:array[1..10000]of longint;
i,j,n,t:longint;
begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-1 do
for j:=i+1 to n do
if a[i]>a[j]then begin t:=a[i];a[i]:=a[j];a[j]:=t;end;
for i:=1 to n do write(a[i],' ');
end.
程序2(pascal)如下:
program xzpx_2;
var
a:array[1..10000]of longint;
i,j,n,t,min:longint;
begin
readln(n);
for i:=1 to n do read(a[i]);
for i:=1 to n-1 do
begin
min:=i;
for j:=i+1 to n do
if a[min]>a[j]then min:=j;
if mini then begin t:=a[min];a[min]:=a[i];a[i]:=t;end;
end;
for i:=1 to n do write(a[i],' ');
end.
编辑本段希尔排序的JAVA 实现
public class Test {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // 预设数据数组
public static void main(String args[]) {
int i; // 循环计数变量
int Index = a.length;// 数据索引变量
System.out.print("排序前: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
ShellSort(Index - 1); // 选择排序
// 排序后结果
System.out.print("排序后: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a);
System.out.println("");
}
public static void ShellSort(int Index) {
int i, j, k; // 循环计数变量
int Temp; // 暂存变量
boolean Change; // 数据是否改变
int DataLength; // 分割集合的间隔长度
int Pointer; // 进行处理的位置
DataLength = (int) Index / 2; // 初始集合间隔长度
while (DataLength != 0) // 数列仍可进行分割
{
// 对各个集合进行处理
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = a[j]; // 暂存Data[j]的值, 待交换值时用
Pointer = j - DataLength; // 计算进行处理的位置
// 进行集合内数值的比较与交换值
while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
a[Pointer + DataLength] = a[Pointer];
// 计算下一个欲进行处理的位置
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
// 与最后的数值交换
a[Pointer + DataLength] = Temp;
if (Change) {
// 打印目前排序结果
System.out.print("排序中: ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; // 计算下次分割的间隔长度
}
}
}
编辑本段希尔排序的C#实现
using System;
public class ShellSorter
{
public void Sort(int[] list)
{
int inc;
for (inc = 1; inc
for (; inc > 0; inc /= 3)
{
for (int i = inc + 1; i
{
int t = list[i - 1];
int j = i;
while ((j > inc) && (list[j - inc - 1] > t))
{
list[j - 1] = list[j - inc - 1];
j -= inc;
}
list[j - 1] = t;
}
}
}
}
public class MainClass
{
public static void Main()
{
int[] iArrary = new int[] { 1, 5, 3, 6, 10, 55, 9, 2, 87, 12, 34, 75, 33, 47 };
ShellSorter sh = new ShellSorter();
sh.Sort(iArrary);
for (int m = 0; m
Console.WriteLine("{0}", iArrary[m]);
Console.ReadKey();
}
}
堆”定义
n 个关键字序列Kl ，K2，…，Kn 称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质) ：
(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ n) //ki相当于二叉树的非叶结点，K2i 则是左孩子，k2i+1是右孩子
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
树中任一非叶结点的关键字均不大于(或不小于) 其左右孩子(若存在) 结点的关键字。
【例】关键字序列(10，15，56，25，30，70) 和(70，56，30，25，15，10) 分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。
大根堆和小根堆：根结点(亦称为堆顶) 的关键字是堆里所有结点关键字中最小者的堆称为小根堆，又称最小堆。根结点(亦称为堆顶) 的关键字是堆里所有结点关键字中最大者，称为大根堆，又称最大堆。注意：①堆中任一子树亦是堆。②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k 叉堆。
堆的高度
堆可以被看成是一棵树，结点在堆中的高度可以被定义为从本结点到叶子结点的最长简单下降路径上边的数目；定义堆的高度为树根的高度。我们将看到，堆结构上的一些基本操作的运行时间至多是与树的高度成正比，为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]交换，由此得到新的无序区
……
直到无序区只有一个元素为止。
（2）大根堆排序算法的基本操作：
① 初始化操作：将R[1..n]构造为初始堆；
② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆) 。
注意： R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2+.keys≤R*n-1..n].keys，同样要将R[1..n-2]调整为堆。
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。 ②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止
特点
堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系(参见二叉树的顺序存储结构) ，在当前无序区中选择关键字最大(或最小) 的记录
堆排序与直接选择排序的区别
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
算法分析
堆[排序的时间，主要由建立初始]堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify 实现的。
堆排序的最坏时间复杂度为O(nlog2n)。堆序的平均性能较接近于最坏性能。 由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。
编辑本段算法描述
堆排序算法(C描述)
// array是待调整的堆数组,i 是待调整的数组元素的位置,nlength 是数组的长度 void HeapAdjust(int array[], int i, int nLength)//本函数功能是：根据数组array 构建大根堆
{
int nChild;
int nTemp;
for (nTemp = array[i]; 2 * i + 1
{
// 子结点的位置＝２*(父结点位置）+ 1
nChild = 2 * i + 1;
// 得到子结点中较大的结点
if (nChild array[nChild])
++nChild;
// 如果较大的子结点大于父结点那么把较大的子结点往上移动, 替换它的父结点 if (nTemp
{
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++描述)
#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
{
if(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);
}
}
因为构造初始堆必须使用到调整堆的操作，先讨论Heapify 的实现，再讨论如何构造初始堆(即BuildHeap 的实现)Heapify 函数思想方法
每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R 交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树
均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。 " 筛选法" 调整堆
R[low]的左、右子树(若存在) 均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆[性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在) 仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为" 筛选法" 。 BuildHeap 的实现
要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。
显然只有一个结点的树是堆，而在完全二叉树中，所有序号大于n/2的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为n/2，…，1的结点作为根的子树都调整为堆即可。
Heapify 函数算法实例
#include
#include
inline int LEFT(int i);
inline int RIGHT(int i);
inline int PARENT(int i);
void MAX_HEAPIFY(int A[],int heap_size,int i);
void BUILD_MAX_HEAP(int A[],int heap_size);
void HEAPSORT(int A[],int heap_size);
void output(int A[],int size);
int main()
{
FILE *fin;
int m,size,i;
fin = fopen("arrayin","r");
int* a;
fscanf(fin," %d",&size);
a = (int *)malloc(size + 1);
a[0]=size;
for(i = 1;i
{
fscanf(fin," %d",&m);
a= m;
}
HEAPSORT(a,a[0]);
printf("$$$$$$$$$$The Result$$$$$$$$\n");
output(a,a[0]);
free(a);
return 0;
}
inline int LEFT(int i)
{
return 2 * i;
}
inline int RIGHT(int i)
{
return 2 * i + 1;
}
inline int PARENT(int i)
{
return i / 2;
}
void MAX_HEAPIFY(int A[],int heap_size,int i)
{
int temp,largest,l,r;
largest = i;
l = LEFT(i);
r = RIGHT(i);
if ((l A[largest])) largest = l; if ((r A[largest])) largest = r; if (largest != i)
{
temp = A[largest];
A[largest] = A;
A= temp;
MAX_HEAPIFY(A[],heap_size,largest);
}
}
void BUILD_MAX_HEAP(int A[],int heap_size)
{
int i;
for (i = heap_size / 2;i >= 1;i--) MAX_HEAPIFY(A,heap_size,i); }
void HEAPSORT(int A[],int heap_size)
{
int i;
BUILD_MAX_HEAP(A,heap_size);
for (i = heap_size;i >= 2; i--)
{
int temp;
temp = A[1];
A[1] = A;
A= temp;
MAX_HEAPIFY(A,i-1,1);
}
}
void output(int A[],int size)
{
int i = 1;
FILE *out = fopen("resultin","w+");
for (; i
{
printf("%d ",A);
fprintf(out,"%d ",A);
}
printf("\n");
}