/******************************************************************************
以下這些函數(shù)實現(xiàn)各種形式的內(nèi)部排序，包括直接插入排序，折半插入排序，2－路插
入排序，希爾排序，快速排序，堆排序，歸并排序等操作.
相關(guān)的存儲結(jié)構(gòu)定義在WORK20.H中


******************************************************************************/
#include "work20.h"
/******************************************************************************
函數(shù)：SqList *CreateSqList(void);
功能：建立待排序序列.
形式參數(shù)：
無
函數(shù)輸出：
指向待排序序列的起始地址
******************************************************************************/
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;
}
/******************************************************************************
函數(shù)：void InsertSort(SqList *L);
功能：直接插入排序
形式參數(shù)：
L: 指向待排序序列首址
函數(shù)輸出：
無
******************************************************************************/
void InsertSort(SqList *L)
{
int i,j;
//從第二個元素開始，將后面的元素插入到前面的有序序列
for(i=2;i<=L->Length;++i){
//如果后面元素的關(guān)鍵字小于前面元素的關(guān)鍵字，則繼續(xù)向前查找
if(L->r[i].key<L->r[i-1].key){
//復(fù)制為監(jiān)視哨
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];
//實現(xiàn)元素插入
L->r[j+1]=L->r[0];
}
}
return;
}


/******************************************************************************
函數(shù)：void ShellSort(SqList *L,int *dlta,int t);
功能：希爾插入排序
形式參數(shù)：
L: 指向待排序序列首址
dlta: 希爾排序子序列中元素增量所在的存儲空間首地址
t: 元素增量的個數(shù)
函數(shù)輸出：
無
******************************************************************************/
void ShellSort(SqList *L, int *dlta, int t)
{
int k;
//根據(jù)每次增量進(jìn)行希爾插入排序
for(k=0;k<t;++k)
ShellInsert(L,dlta[k]);
return;
}
/******************************************************************************
函數(shù)：void ShellInsert(SqList *L, int dk);
功能：根據(jù)dk的大小，將當(dāng)前位置后dk大小的元素插入到當(dāng)前位置前的子序列中
形式參數(shù)：
L: 指向待排序序列首址
dk: 子序列中每個元素之間的相對位置差
函數(shù)輸出：
無
******************************************************************************/
void ShellInsert(SqList *L, int dk)
{
int i,j;
//對每個子序列中的元素都采用相同的操作：直接插入排序。每個子序列中的元素
//并不是連續(xù)的，而是相隔dk個地址空間
for(i=dk+1;i<=L->Length;++i){
//直接插入排序，只不過應(yīng)該與待插入元素前dk個位置的元素進(jìn)行比較
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;
}
/******************************************************************************
函數(shù)：void QuickSort(SqList *L);
功能：快速排序
形式參數(shù)：
L: 指向待排序序列首址
函數(shù)輸出：
無
******************************************************************************/
void QuickSort(SqList *L)
{
QSort(L,1,L->Length);
return;
}
/******************************************************************************
函數(shù)：void QSort(SqList *L, int low,int high);
功能：對L序列中的元素（在low到high之間）進(jìn)行快速排序
形式參數(shù)：
L: 指向待排序序列首址
low: 快速排序的低地址
high: 快速排序的高地址
函數(shù)輸出：
無
******************************************************************************/
void QSort(SqList *L, int low,int high)
{
int pivotloc;
//但low地址小于high地址時，進(jìn)行快速排序
if(low<high){
//進(jìn)行一趟快速排序，并得到樞軸元素當(dāng)前的位置
pivotloc=Partion(L,low,high);
//之前的元素為一個子序列，進(jìn)行快速排序
QSort(L,low,pivotloc-1);
//之后的元素為一個子序列，進(jìn)行快速排序
QSort(L,pivotloc+1,high);
}
return;
}
/******************************************************************************
函數(shù)：int Partion(SqList *L, int low,int high);
功能：一趟快速排序
形式參數(shù)：
L: 指向待排序序列首址
low: 一趟快速排序的低地址
high: 一趟快速排序的高地址
函數(shù)輸出：
無
******************************************************************************/
int Partion(SqList *L, int low,int high)
{
int pivotkey;
//序列的第一個元素先放在0號存儲單元，并不需要馬上進(jìn)行交換
L->r[0]=L->r[low];
//序列的第一個元素為樞軸
pivotkey=L->r[low].key;
while(low<high){
//如果high所指元素大于數(shù)組，則繼續(xù)往前找
while(low<high && L->r[high].key>=pivotkey)
--high;
//反之，則將high所指的元素放在low的位置上
L->r[low]=L->r[high];
//如果low所指的元素小于樞軸，則繼續(xù)往后找，直到大于樞軸
while(low<high && L->r[low].key<=pivotkey)
++low;
//反之，則將low所指元素放在high所指的位置
L->r[high]=L->r[low];
}
//最后一個元素實現(xiàn)樞軸元素放在適當(dāng)?shù)奈恢茫@樣其左邊的元素小于樞軸，
//其右邊的元素大于樞軸
L->r[low]=L->r[0];
return low;
}