堆排序

 

【算法】
是这样实现的：因为n/2之后的结点已经是堆，只要从这点开始向前调节，将它与它的左右孩子中最大（小）的比较，如果比它还大（小）则不用往后移，这点即是它的位置，否则将它和那个孩子子交换，依次下去，直到这个结点确定了位置，然后再向前调整，直到根部。

void HeapAdjust(SqList &H,int s,int m)
{
//已知H.elemword[s..m]中除H.elemword[s]之外均满足堆的定义,本函数调整H.elemword[s]
//使H.elemword[s..m]成为一个大顶堆
int j,rc;
rc=H.elemword[s];
for(j=2*s;j<=m;j*=2) //沿关键字叫大的结点向下筛选
{
if(j为关键字较大的记录的下标
if(rc>=H.elemword[j]) break; //rc应插入在位置s上
H.elemword[s]=H.elemword[j];
s=j;
}
H.elemword[s]=rc; //插入
}
void HeapSort(SqList &L)
{
//对顺序表L做堆排序。
int i,j,t;
for(i=L.length/2;i>0;--i) //把L.elemword[1..L.length]建成大顶堆
HeapAdjust(L,i,L.length);
for(i=L.length;i>1;--i)
{
Swap(L.elemword[1],L.elemword[i]); //将堆顶记录和当前未经排序子序列L.elemword[1..i] 中的最后一个记录相互交换
HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大顶堆
}
}

 

 

【交换排序】
是一种主要以交换的方式对序列进行排序的方法。

其实排序的基本方法或手段主要就是比较和交换，像选择法等都借助了交换的手段，但都不是主要以交换为手段，在直接选择排序的时候，一轮比较就能确定最大元素的位置，然后再进行交换，也就是说这样的交换是“稳定”的。

【冒泡排序法】
也叫起泡排序法，过程跟气泡从水里冒出来类似。一轮交换对相邻元素进行比较，如果逆序则交换，作用只能使一个元素到达最终位置，而其它的交换是多余的，如果只进行比较而不交换的话，就跟直接选择排序法一样，不同的是，它是不稳定的。

void bubblesort(int n,list r)
{
for (i=1;i=n-1,i++)
{
flag=1;//标记是否有交换
for (j=1;j=n-1;j++)
if (r[j].key>r[j+1].key)
{
flag=0;
swap(r[j],r[j+1]);//交换相邻元素
}
if(flag)return;//如果一轮比较没有元素交换则说明整体有序，直接退出
}
}

【快速排序法】
也是一种交换排序法，实际上它是冒泡法的改进。

【算法】
思想是：一次划分使整个元素部分有序，即从序列中任选一个元素，然后对其它元素进行这样的划分，使得所有比它小（大）的元素在左侧而所有比它大（小）的元素在右侧，然后用分治的思想对左右侧的序列同样的处理，直到只有一个元素为止。

一次划分的算法如下：
int quickpass(list r,int low,int high)
{
int i=low; j=high; x=r[i]; //置初值，i指最左端，j指最右端，选第i个元素为划分比较元素x
while (i{
while ((r[j].key>=x.key)&&(i//自尾端进行比较，因为i处为空
if (i{
r[i]=r[j]; i++;//填入i处
while ((r[i].key<=x.key&&(i//自首端进行比较，j处已空
if (i}
}
r[i]=x;//一趟快速排序结束，将x移至正确位置
return i;//返回划分比较元素的位置
}

整个快速排序的过程用递归算法设计，思想当然是分治的思想：
void quicksort(list r,int low,int high)
//对r[low]，r[low+1],...r[high]进行快速排序
{
if(low{
int k;
k=quickpass(r,low,high);//一次划分
quicksort(r,low,k-1);//对左侧元素以同样的方法对待
quicksort(r,k+1,high);//对右侧元素以同样的方法对待
}
}