快速排序
快速排序算法是基于分治策略的一种排序算法，它的基本思想是：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的值均比另一部分记录的值小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
基本步骤：对于输入的子数组a[low：high]，按以下三个步骤进行排序。
(1)分解(Divide)：以a[low]为基准元素将a[low：high]划分为3段a[low：q-1]，a[q]和a[q+1：high]，使a[low：q-1]中任何一个元素小于等于a[q]，而a[q+1：high]中任何一个元素大于等于a[q]。下标q在划分的过程中确定。
(2)递归求解(Conquer)：通过递归调用快速排序算法分别对a[low：q-1]和a[q+1：high]进行排序。
(3)合并(Merge)：由于对a[low：q-1]和a[q+1：high]的排序是就地进行的，所以在a[low：q-1]和a[q+1：high]都已排好的序后，不需要执行任何计算，a[low,high]就已排好序。
C++代码：
template <class Type>
void QuickSort(Type a[],int low,int high)
{ if(low < high){
int q = Partition(a,low,high);
QuickSort(a,low,q-1); //对左半段排序
QuickSort(a,q+1,high); //对右半段排序
}
}
template <class Type)
int Partition(Type a[],int low,int high)
{
int i = p,j = high+1;
Type x = a[p];
while(true)
{
while(a[++i]<x&&i<high);
while(a[--j]>x);
if(i>=j) break;
Type temp = a[j];
a[j] = a[i];
a[i] = temp;
}
a[p] = a[j];
a[j] = x;
return j;
}
归并排序
归并排序算法也是用分治策略实现对n个元素进行排序的算法，其基本思想是：将待排序元素分成大小大致相同的两个集合，分别对两个子集合进行排序，最终将排好序的子集合合并成所要求的排好序的集合。
C++代码：
template <class Type>
void MergeSort(Type a[],int n)
{
Type *b = new Type[n];
int s = 1;
while(s<n)
{
MergePass(a,b,s,n); //合并到数组b
s += s;
MergePass(b,a,s,n); //合并到数组a
s += s;
}
}
template <class Type>
void MergePass(Type x[],Type y[],int s,int n)
{ //合并大小为s的相邻子数组
int i = 0;
while(i<=n-2*s)
{ //合并大小为s的相邻2段子数组
Merge(x,y,i,i+s-1,i+2*s-1);
i = i+2*s;
}
//剩下的元素个数少于 2s
if(i+s<n) Merge(x,y,i,i+s-1,n-1);
else for(int j=i;j<=n-1;) y[j]=x[j];
}
template <class Type>
void Merge(Type c[],Type d[],int t,int m,int r)
{ //合并c[t:m]和c[m+1:r]到d[t:r]
int i=t,j=m+1,k=t;
while((i<=m)&&(j<=r))
{
if(c[i]<=c[j]) d[k++]=c[i++];
else d[k++] = c[j++];
}
if(i>m) for(int q=j;q<=r;q++) d[k++]=c[q];
else for(int q=i;q<=m;q++) d[k++] = c[q];
}
冒泡排序
冒泡排序的过程很简单，其基本思想是：首先将第一个记录的值和第二个记录的值进行比较，若为逆序，则将两个记录交换之，然后比较第二个记录和第三个记录的值。以此类推，直至第n-1个记录和第n个记录的值进行比较过。这个过程叫做第一趟冒泡排序，其结果是使得记录值最大的记录被安置到最后一个记录的位置上。然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是使前n-1个记录中最大的记录被安置到第n-1个记录的位置上。如此类推至剩下一个记录则结束排序。
C++代码：
template <class Type>
void BubbleSort(Type a[], int n)
{
int i, j;
for (i = 0; i < n; i++)
for (j = 1; j < n - i; j++)
if (a[j - 1] > a[j])
{
Type temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
直接插入排序
直接插入排序是一种最简单的排序方法，它的基本思想是将一个记录插入到已排好序的有序序列中，从而得到一个新的、记录数增1的有序序列。第i趟直接插入排序的操作为：在含有i-1个记录的有序子序列r[1....i-1]中插入一个记录r[i]后，变成含有i个记录的有序子序列人r[1...i]；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r[0]处设置监视哨。
C++代码：
template <class Type>
void InsertSort(Type a[],int n)
{
for(int i =2;i<=n;i++)
{
if(a[i]<a[i-1]）
{
a[0] = a[i];
a[i] = a[i-1];
for(int j = i-2;a[j]<a[0];j--)
a[j+1] = a[j];
a[j+1] = a[0];
}
}
折半插入排序
上述的直接插入排序算法简单，且容易实现，当待排序记录的数量n很小时，这是一种很好的排序方法。但通常待排序序列中的记录数量n很大，则不宜采用直接插入排序。则得到改进的办法折半插入排序。
折半插入排序的基本思想是：在一个有序序列中进行查找和插入，这个查找可以利用“折半查找”来实现。
C++代码：
template <class Type>
void BInsertSort(Type a[],int n)
{
for(int i=2;i<=n;i++)
{
a[0] = a[i];
int low = 1,high = i-1;
while(low <= high)
{
int m = (low+high)/2;
if(a[0]<a[m]) high = m-1;
else low = m+1;
}
for(int j = i-1;j>=high+1;j--) a[j+1]=a[j];
a[high+1] = a[0];
}
}
希尔排序
希尔排序又称“缩小增量排序”，它也是一种属于插入排序类的方法，但在时间效率上有较大的改进。
- 它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
- 排序过程：先取一个正整数d1<n，把所有序号相隔d1的数组元素放一组，组内进行直接插入排序；然后取d2<d1，重复上述分组和排序操作；直至di=1，即所有记录放进一个组中排序为止。
- 增量序列的选择
Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
C++代码：
int dkHibbard(int t,int k)
{ //计算增量
return int(pow(2,t-k+1)-1);
}
template <class Type>
void ShellInsert(Type a[],int n;int dk)
{ //根据当前增量进行插入排序
for(int i=dk+1;i<=n;i++) //分别向每组的有序区域插入
{
if(a[i]<a[i-dk])
a[0] = a[i];
for(int j=i-dk;j>0&&a[0]<a[j];j-=dk) //比较与记录后移同时进行
a[j+dk]=a[j];
a[j+dk]=a[0]; //插入
}
}
template <class Type>
void ShellSort(Type a[],int n;int t)
{ //希尔排序
for(int k=1;k<=t;k++)
ShellInsert(a,n,dkHibbard(t,k);
}
网友评论