cpp1.cpp

包含几乎所有的排序算法

/******************************************************************************
以下这些函数实现各种形式的内部排序，包括直接插入排序，折半插入排序，2－路插
入排序，希尔排序，快速排序，堆排序，归并排序等操作.
相关的存储结构定义在WORK20.H中


******************************************************************************/
#include "work20.h"
/******************************************************************************
函数：SqList *CreateSqList(void);
功能：建立待排序序列.
形式参数：
无
函数输出：
指向待排序序列的起始地址
******************************************************************************/
SqList *CreateSqList(void)
{
SqList *sq;
int i;
//分配存储空间
sq=(SqList*)malloc(sizeof(SqList));
//输入序列长度
printf("Please input sequence length:");
scanf("%d",&(sq->Length));
//给序列的每个元素分配存储空间
sq->r=(RedType*)malloc(sizeof(RedType)*(sq->Length+1));
//输入序列中的元素
for(i=1;i<=sq->Length;i++){
printf("Please input Element %d==>key:",i);
scanf("%d",&(sq->r[i].key));
}
//返回序列起始地址
return sq;
}
/******************************************************************************
函数：void InsertSort(SqList *L);
功能：直接插入排序
形式参数：
L: 指向待排序序列首址
函数输出：
无
******************************************************************************/
void InsertSort(SqList *L)
{
int i,j;
//从第二个元素开始，将后面的元素插入到前面的有序序列
for(i=2;i<=L->Length;++i){
//如果后面元素的关键字小于前面元素的关键字，则继续向前查找
if(L->r[i].key<L->r[i-1].key){
//复制为监视哨
L->r[0]=L->r[i];;
//元素后移
for(j=i-1;L->r[0].key<L->r[j].key;--j)
L->r[j+1]=L->r[j];
//实现元素插入
L->r[j+1]=L->r[0];
}
}
return;
}


/******************************************************************************
函数：void ShellSort(SqList *L,int *dlta,int t);
功能：希尔插入排序
形式参数：
L: 指向待排序序列首址
dlta: 希尔排序子序列中元素增量所在的存储空间首地址
t: 元素增量的个数
函数输出：
无
******************************************************************************/
void ShellSort(SqList *L, int *dlta, int t)
{
int k;
//根据每次增量进行希尔插入排序
for(k=0;k<t;++k)
ShellInsert(L,dlta[k]);
return;
}
/******************************************************************************
函数：void ShellInsert(SqList *L, int dk);
功能：根据dk的大小，将当前位置后dk大小的元素插入到当前位置前的子序列中
形式参数：
L: 指向待排序序列首址
dk: 子序列中每个元素之间的相对位置差
函数输出：
无
******************************************************************************/
void ShellInsert(SqList *L, int dk)
{
int i,j;
//对每个子序列中的元素都采用相同的操作：直接插入排序。每个子序列中的元素
//并不是连续的，而是相隔dk个地址空间
for(i=dk+1;i<=L->Length;++i){
//直接插入排序，只不过应该与待插入元素前dk个位置的元素进行比较
if(L->r[i].key<L->r[i-dk].key){
L->r[0]=L->r[i];
for(j=i-dk;j>0 && L->r[0].key<L->r[j].key; j=j-dk)
L->r[j+dk]=L->r[j];
L->r[j+dk]=L->r[0];
}
}
return;
}
/******************************************************************************
函数：void QuickSort(SqList *L);
功能：快速排序
形式参数：
L: 指向待排序序列首址
函数输出：
无
******************************************************************************/
void QuickSort(SqList *L)
{
QSort(L,1,L->Length);
return;
}
/******************************************************************************
函数：void QSort(SqList *L, int low,int high);
功能：对L序列中的元素（在low到high之间）进行快速排序
形式参数：
L: 指向待排序序列首址
low: 快速排序的低地址
high: 快速排序的高地址
函数输出：
无
******************************************************************************/
void QSort(SqList *L, int low,int high)
{
int pivotloc;
//但low地址小于high地址时，进行快速排序
if(low<high){
//进行一趟快速排序，并得到枢轴元素当前的位置
pivotloc=Partion(L,low,high);
//之前的元素为一个子序列，进行快速排序
QSort(L,low,pivotloc-1);
//之后的元素为一个子序列，进行快速排序
QSort(L,pivotloc+1,high);
}
return;
}
/******************************************************************************
函数：int Partion(SqList *L, int low,int high);
功能：一趟快速排序
形式参数：
L: 指向待排序序列首址
low: 一趟快速排序的低地址
high: 一趟快速排序的高地址
函数输出：
无
******************************************************************************/
int Partion(SqList *L, int low,int high)
{
int pivotkey;
//序列的第一个元素先放在0号存储单元，并不需要马上进行交换
L->r[0]=L->r[low];
//序列的第一个元素为枢轴
pivotkey=L->r[low].key;
while(low<high){
//如果high所指元素大于数组，则继续往前找
while(low<high && L->r[high].key>=pivotkey)
--high;
//反之，则将high所指的元素放在low的位置上
L->r[low]=L->r[high];
//如果low所指的元素小于枢轴，则继续往后找，直到大于枢轴
while(low<high && L->r[low].key<=pivotkey)
++low;
//反之，则将low所指元素放在high所指的位置
L->r[high]=L->r[low];
}
//最后一个元素实现枢轴元素放在适当的位置，这样其左边的元素小于枢轴，
//其右边的元素大于枢轴
L->r[low]=L->r[0];
return low;
}