//堆排序
/*堆排序原理及分析
“堆”定义
n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：
(1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），当然，这是小根堆，大根堆则换成>=号。
k(i）相当于二叉树的非叶结点，K(2i）则是左孩子，k(2i+1）是右孩子
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。*/
/* 堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）
关键字的记录变得简单。 （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]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。 */
/* 堆排序与直接选择排序的区别
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，
又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时
未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。 堆排序可通过树形结构保存部分比较结果，
可减少比较次数。
算法分析
堆[排序的时间，主要由建立初始]堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现
的。 堆排序的最坏时间复杂度为O(nlogn)。堆序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。 堆排序是就地排序，辅助空间为O(1），
它是不稳定的排序方法。 */
// 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);
}
}
//冒泡排序
/*
冒泡排序，是指计算机的一种排序方法，它的时间复杂度为O（n^2），虽然不及堆排序、快速排序的O（nlogn，底数为2），
但是有两个优点：1.“编程复杂度”很低，很容易写出代码；2.具有稳定性，这里的稳定性是指原序列中相同元素的
相对顺序仍然保持到排序后的序列，而堆排序、快速排序均不具有稳定性。不过，一路、二路归并排序、不平衡二叉树排序
的速度均比冒泡排序快，且具有稳定性，但速度不及堆排序、快速排序。冒泡排序是经过n-1趟子排序完成的，第i趟子排序
从第1个数至第n-i个数，若第i个数比后一个数大（则升序，小则降序）则交换两数
*/
/*冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：
首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，
直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较
（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个
数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大
的数）。如此下去，重复以上过程，直至最终完成排序。
*/
/*性能分析
若记录序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；
反之，若记录序列的初始状态为"逆序"，则需进行n(n-1）/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。
*/
void bubble_sort(int *x,int n)
{
int j,k,h,t;
// for (h=n-1,h=k; h>0; h--) /*循环到没有比较范围*/
for (h=n-1; h>0; h--) /*循环到没有比较范围*/
{
for (j=0; j
{
if (*(x+j) > *(x+j+1）) /*大的放在后面，小的放到前面*/
{
t = *(x+j);
*(x+j) = *(x+j+1）;
*(x+j+1） = t; /*完成交换*/
// k = j; /*保存最后下沉的位置。这样k后面的都是排序排好了的。*/
}
}
}
}
//快速排序算法
/*它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据
都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它小的数
都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序
算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。
一趟快速排序的算法是：
1）设置两个变量I、J，排序开始的时候：I=0，J=N-1；
2）以第一个数组元素作为关键数据，赋值给key，即 key=A[0]；
3）从J开始向前搜索，即由后开始向前搜索（J=J-1），找到第一个小于key的值A[J]，并与key交换；
4）从I开始向后搜索，即由前开始向后搜索（I=I+1），找到第一个大于key的A[I]，与key交换；
5）重复第3、4、5步，直到 I=J； (3,4步是在程序中没找到时候j=j-1，i=i+1，直至找到为止。找到并交换的时候i， j指针
位置不变。另外当i=j这过程一定正好是i+或j-完成的最后另循环结束。）
*/
//调用：quicksort-->qsort-->partitions
int partitions(int a[],int low,int high)
{
int pivotkey=a[low]; //a[0]=a[low];
while(low
{
while(low=pivotkey)
--high;
a[low]=a[high];
while(low
++low;
a[high]=a[low];
} //a[low]=a[0];
a[low]=pivotkey;
return low;
}
void qsort(int a[],int low,int high)
{
int pivottag;
if(low
{ //递归调用
pivottag=partitions(a,low,high);
qsort(a,low,pivottag-1);
qsort(a,pivottag+1,high);
}
}
void quicksort(int a[],int n)
{
qsort(a,0,n);
}
//直接插入排序
/*直接插入排序(straight insertion sort)的作法是： 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，
使有序表仍然有序。 第一趟比较前两个数,然后把第二个数按大小插入到有序表中; 第二趟把第三个数据与前两个数从前
向后扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。 直接插
入排序属于稳定的排序，时间复杂性为o(n^2)，空间复杂度为O(1)。 直接插入排序是由两层嵌套循环组成的。外层循环
标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比
较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并
将待比较数值置入其后一位置，结束该次循环。 值得注意的是，我们必需用一个存储空间来保存当前待比较的数值，因为
当一趟比较完成时，我们要将待比较数值置入比它小的数值的后一位 插入排序类似玩牌时整理手中纸牌的过程。插入排序的基
本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。
*/
//C/C++代码实现直接插入排序：
void InsertSort(int a[],int length)
{
int i,j,tmp;
for(i=1;i
{
tmp = a[i];
if(tmp < a[i-1])
{
for(j = i-1;j >=0;j--)
{
if(tmp < a[j])
a[j+1] = a[j];
else
break;
}
a[j+1] = tmp;
}
}
}
//归并排序
/*
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序
列是有序的。然后再把有序子序列合并为整体有序序列。
算法描述
归并操作的工作原理如下： 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 设定
两个指针，最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素，选择相对小的元素放入到合并空
间，并移动指针到下一位置 重复步骤3直到某一指针达到序列尾 将另一序列剩下的所有元素直接复制到合并序列尾
复杂度
时间O(nlogn) 空间O(n)
*/
/*归并排序 归并排序具体工作原理如下（假设序列共有n个元素）： 将序列每相邻两个数字进行归并操作
（merge)，形成floor(n/2)个序列，排序后每个序列包含两个元素 将上述序列再次归并，形成floor(n/4)个序列，
每个序列包含四个元素 重复步骤2，直到所有元素排序完毕 示例代码
*/
//输入参数中，需要排序的数组为array[],起始索引为first，终止索引为last。调用完成后，array[]中从first到last处于
//升序排列。
void Merge(int r[],int r1[],int s,int m,int t)
{
int i=s;
int j=m+1;
int k=s;
while(i<=m&&j<=t)
{
if(r[i]<=r[j])
{
r1[k++]=r[i++];
}
else
{
r1[k++]=r[j++];
}
}
if(i<=m)
{
while(i<=m)
{
r1[k++]=r[i++];
}
}
else while(j<=t)
{
r1[k++]=r[j++];
}
for(int l=0;l
{
r[l]=r1[l];
}
}
void MergeSort(int r[],int r1[],int s,int t)
{
if(s==t)
{
r1[s]=r[s];
}
else
{
int m=(s+t)/2;
MergeSort(r,r1,s,m);
MergeSort(r,r1,m+1,t);
Merge(r1,r,s,m,t);
}
}
void main()
{
int r[8]={10,3,5,1,9,34,54,565},r1[8];
MergeSort(r,r1,0,7);
for(int q=0;q<8;q++)
cout<<" "<
}
//选择排序
/*
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据
元素排完。 选择排序是不稳定的排序方法。
基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：
①初始状态：无序区为R[1..n]，有序区为空。
②第1趟排序 在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]
分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 ……
③第i趟排序 第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出
关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数
减少1个的新无序区。 这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
常见的选择排序细分为简单选择排序、树形选择排序（锦标赛排序）、堆排序。上述算法仅是简单选择排序的步骤。
复杂度分析
排序算法复杂度对比
选择排序的交换操作介于 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值较小时，选择排序比冒泡
排序快。
*/
//直接选择排序的具体算法如下：
void SelectSort(SeqList R)
{
int i，j，k;
for(i=1;i
{ //做第i趟排序(1≤i≤n-1)
k=i;
for(j=i+1;j<=n;j++) //在当前无序区R[i..n]中选key最小的记录R[k]
if(R[j].key
k=j; //k记下目前找到的最小关键字所在的位置
if(k!=i)
{ //交换R[i]和R[k]
R[0]=R[i];
R[i]=R[k];
R[k]=R[0];//R[0]作暂存单元
} //endif
} //endfor
} //SeleetSort
//希尔排序
/*希尔排序(Shell Sort)是插入排序的一种。是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL．Shell于1959年提出而得名。
希尔排序基本思想：
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。
先在各组内进行直接插入排序；然后，取第二个增量d2
即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
优劣
不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个
新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)， 没有快速排序算法快 O(N*(logN))，因此中等大小规模表
现良好，对规模非常大的数据排序不是 最优选择。但是比O(N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码
短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏 的情况下执行的
效率会非常差。 专家们提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排
序这样更高级的排序算法. 本质上讲，希尔排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当N值很大
时数据项每一趟排序需要的个数很少，但数据项的距离很长。 当N值减小时每一趟需要和动的数据增多，此时已经接近于它们
排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。
时间性能
1．增量序列的选择 Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征： ① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量的实验，给出了目前较好的结果：当n较大时，比较和移动的次数约在nl.25到1.6n1.25之间。
2．Shell排序的时间性能优于直接插入排序 希尔排序的时间性能优于直接插入排序的原因：
①当文件初态基本有序时直接插入排序所需的比较和移动次数均较少。 ②当n值较小时，n和n2的差别也较小，即直接插入
排序的最好时间复杂度O(n)和最坏时间复杂度0(n2)差别不大。
③在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量di逐渐缩小，分组数逐渐减
少，而各组的记录数目逐渐增多，但由于已经按di-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较
快。 因此，希尔排序在效率上较直接插人排序有较大的改进。
*/
// 希尔排序的C实现
k=n/2;
while(k>0)
{
for(i=k;i<=n;i++)
{
t=a[i];
j=i-k;
while(j>=1 && t
{
a[j+k]=a[j];
j=j-k;
}
a[j+k]=t;
}
k/=2;
}
//希尔排序C的四种实现：
void shellsort(int *a,int n)
{
int k = n/2;
while(k>0)
{
for(int i = k;i< N;i++)
{
int t = a[i];
#if 0 //算法1
int j = i - k;
while(j >= 0 && t < a[j])
{
a[j + k] = a[j];
j = j - k;
}
#endif
#if 0 //算法2
int j;
for(j = i - k;j>=0 && t < a[j];j -= k)
a[j + k] = a[j];
a[j + k] = t;
#endif
#if 0 //算法3
int j;
for(j = i;j >= k && t < a[j - k];j -= k)
a[j] = a[j - k];
a[j] = t;
#endif
//算法4
int j = i;
while(j >= k && t < a[j - k])
{
a[j] = a[j-k];
j = j-k;
}
a[j] = t;
}
k /= 2;
}
}
int main()
{
int a[N]= {8,10,3,5,7,4,6,1,9,2};
shellsort(a,sizeof(a)/sizeof(a[0]));
for(int k = 0;k < N;k++)
printf("a[%d] = %d\n",k,a[k]);
return 0;
}
//折半查找
/*
折半查找的算法思想是将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置
为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查
找区间缩小一半。 折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条
件是查找表中的数据元素必须有序。
算法步骤描述
step1. 首先确定整个查找区间的中间位置 mid = （ left + right ）/ 2
step2. 用待查关键字值与中间位置的关键字值进行比较； 若相等，则查找成功 若大于，则在后（右）半个
区域继续进行折半查找 若小于，则在前（左）半个区域继续进行折半查找
Step3. 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。 折
半查找的存储结构采用一维数组存放。
*/
int BinarySearch(Type a[],const Type& x,int n)
{
int left=0;
int right=n-1;
while(left<=right)
{
int middle=(left+right)/2;
if (x==a[middle])
return middle;
if (x>a[middle])
left=middle+1;
else
right=middle-1;
}
return -1;
}
//递归实现
int binary_search( Record * r, const int & low, const int & high, const Key & k )
{
int mid = (low + high)/2;
if( low < high )
{
if( k <= r[mid] )
binary_search( r, low, mid, k );
else
binary_search( r, mid+1, high, k );
}
else if( low == high )
{
if( k == r[mid] )
return low;
else
return -1;
}
else
return -1;
}
//迭代实现
int binary_search( Record * r, const int & size, const Key & k )
{
int low=0, high=size-1, mid;
while( low < high )
{
mid = (low + high) / 2;
if( k > r[mid] )
low = mid + 1;
else
high = mid;
}
if( low > high )
return -1;
else
{
if( k == r[low] )
return low;
else
return -1;
}
}
阅读(2163) | 评论(0) | 转发(4) |
