严蔚敏 数据结构第十章 内部排序的具体代码(c++,附测试数据)

这是可以直接编译并运行的cpp文件,供您下载之后,慢慢揣摩。

/*测试数据：生成exe文件后，直接把测试数据粘贴到dos窗口上即可！
10
5 7 1 6 8 4 0 9 3 2
11 87 65 32 45 78 20 36 28 94
5 7 1 6 8 4 0 9 3 2
11 87 65 32 45 78 20 36 28 94
11 87 65 32 45 78 20 36 28 94
10
5 7 1 6 8 4 0 9 3 2
11 87 65 32 45 78 20 36 28 94
36
*/

#include<iostream>

#define MAXSIZE 20 //顺序表长度
#define LT(a, b) (a < b)
#define EQ(a, b) (a == b)
#define LQ(a, b) (a <= b)
using namespace std;

typedef int KeyType; //本章中关键字都为整数类型
typedef char* InfoType;
typedef struct {
KeyType key;
InfoType otherinfo;
}RedType; //记录类型
typedef struct {
RedType r[MAXSIZE+1]; //0号单元用作哨兵
intlength;
}SqList; //顺序表类型

//*******************************************
//直接插入排序
void InsertSort ( SqList &L ) {
//按非递减顺序对表进行排序,从后向前顺序比较
int i,j;
for ( i = 2; i <= L.length; ++ i)
if LT(L.r[i].key,L.r[i-1].key){
L.r[0]=L.r[i];
for ( j = i-1; LT(L.r[0].key,L.r[j].key); --j )
L.r[j+1]=L.r[j];
L.r[j+1]=L.r[0];
}//if
}

//***********************
//折半插入排序
void BInsertSort (SqList &L){
int i,j;
int high,low,m;
for (i=2;i<=L.length;++i){
L.r[0]=L.r[i];
low=1;high=i-1; //查找范围由1到i-1
while(low<=high){
m=(low+high)/2;
if LT(L.r[0].key,L.r[m].key) high=m-1;
else low=m+1;//要查找的数L.r[0].key >=L.r[m].key,这是与折半查找的区别。也是下面为什么取high+1的症结所在
}//while 折半查找
for (j=i-1;j>=high+1;--j) L.r[j+1]=L.r[j];
//折半查找结束后high+1位置即为插入位置
L.r[high+1]=L.r[0];
}//for
}//BInsertSort
//*********************************
typedef int SortData;
void Swap(SortData &a, SortData &b){
SortData temp;
temp=a;
a=b;
b=temp;
}
//**************************************
//希尔排序

void ShellSort ( SortData V[ ], int n ) {
int i,j;
SortData temp; int gap = n / 2; //gap是间隔
while ( gap != 0 ) { //循环,直到gap为零
for ( i = gap; i < n; i++) {
temp = V[i]; //直接插入排序
for ( j = i; j >= gap; j = j-gap )
if ( temp < V[j-gap] )
V[j] = V[j-gap];
else break;
V[j] = temp;//如果该for执行过，直接从else里面跳出，则j 还是i；如果进过if，那么就好理解了
}
gap = ( int ) ( gap / 2 );
}
} //ShellSort
//***************************************************************
//起泡排序
void BubbleSort ( SortData V[ ], int n ) {
int i = 1;

int exchange = 1;
SortData temp;
while ( i < n && exchange ){
exchange = 0;//标志置为0,假定未交换
for ( int j = n-1; j >= i; j-- )

这是可以直接编译并运行的cpp文件,供您下载之后,慢慢揣摩。

if ( V[j-1] > V[j] ) { //逆序
Swap ( V[j-1], V[j] ); //交换
exchange = 1; //标志置为1,有交换
}
i++;
}
}
//******************************************************************
//*******************************************************************
//快速排序
int Partition (SqList &L,int low, int high){
L.r[0]=L.r[low]; //子表的第一个记录作基准对象，作为枢轴记录
KeyType pivotkey=L.r[low].key; //基准对象关键字
while (low<high){
while (low<high && L.r[high].key>=pivotkey) --high;
L.r[low]=L.r[high]; //小于基准对象的移到区间的左侧
while (low<high && L.r[low].key<=pivotkey) ++low;
L.r[high]=L.r[low]; //大于基准对象的移到区间的右侧
}
L.r[low]=L.r[0];
return low;
}//Partition
void QSort ( SqList &L, int low, int high ){
//在序列low?high 中递归地进行快速排序
if ( low < high) {
int pivotloc= Partition (L, low, high); //划分

QSort ( L, low, pivotloc-1); //对左序列同样处理
QSort ( L, pivotloc+1, high); //对右序列同样处理
}
}//QSort
void QuickSort (SqList &L){
QSort(L,1,L.length);
}//QuickSort
//**************************************************
//直接选择排序
void SelectSort ( SortData V[ ], int n ) {
for ( int i = 0; i < n-1; i++ ) {
int k = i; //选择具有最小排序码的对象
for ( int j = i+1; j < n; j++)
if ( V[j] < V[k] )
k = j; //当前具最小排序码的对象
if ( k != i ) //对换到第 i 个位置
Swap ( V[i], V[k] );
}
}
//********************************************
typedef SqList HeapType;
void HeapAdjust (HeapType &H, int s, int m){
//设大顶堆为H.r[s..m]，且H.r[s]需要调整
int j;
RedType rc=H.r[s];
for (j=2*s;j<=m;j*=2){
if(j<m && LT(H.r[j].key, H.r[j+1].key)) ++j;
if(!LT(rc.key,H.r[j].key)) break;
H.r[s]=H.r[j];
s=j;
}
H.r[s]=rc;
}//HeapAdjust
void HeapSort (HeapType &H){
RedType temp;int i;
for (i=H.length/2;i>0;--i) //建立堆
HeapAdjust (H,i,H.length);
for (i=H.length;i>1;--i) { //排序
//H.r[1]←→H.r[i];
temp=H.r[1];
H.r[1]=H.r[i];
H.r[i]=temp;
HeapAdjust (H,1,i-1);
}
}//HeapSort

//*************************************************
//********归并排序**************************//
void merge ( SortData InitList[ ], SortData mergedList[ ],
int left, int mid, int right ) {
int i = left, j = mid+1, k = left;
while ( i <= mid && j <= right ) //两两比较将较小的并入
if ( InitList[i] <= InitList[j] )
{ mergedList [k] = In
itList[i]; i++; k++; }
else
{ mergedList [k] = InitList[j]; j++; k++ …… 此处隐藏：3960字，全部文档内容请下载后查看。喜欢就下载吧 ……