简单选择排序

算法：

Smp_Selecpass(ListType &r,int i)

{

k=i;

for(j=i+1;j<n;i++)

if (r[j].key<r[k].key)

k=j;

if (k!=i)

{ t=r[i];r[i]=r[k];r[k]=t;}

}

Smp_Sort(ListType &r)

{

for(i=1;i<n-1;i++)

Smp_Selecpass(r,i);

}

堆排序

sift(ListType &r,int k,int m)

{

i=k;j=2*i;x=r[k].key;finished=FALSE; t=r[k];

while((j<=m)&&(!finished))

{

if ((j<m)&&(r[j].key>r[j+1].key)) j++; if (x<=r[j].key)

finished:=TRUE;

else {r[i]=r[j];i=j;j=2*i;}

}

r[i]=t;

}

HeapSort(ListType &r)

{

for(i=n/2;i>0;i--) sift(r,i,n);

for(i=n;i>1;i--){

r[1]<->r[i];

sift(r,i,i-1)

}

}

归并排序

merge(ListType r,int l,int m,int n,ListType &r2) {

i=l;j=m+1;k=l-1;

while(i<=m) and(j<n) do

{

k=k+1;

if (r[i].key<=r[j].key) {r2[k]=r[i];i++;}

else {r2[i]=r[j];j++}

}

if (i<=m) r2[k+1..n]=r[i..m];

if (j<=n) r2[k+1..n]=r[j..n];

}

mergesort(ListType &r,ListType &r1,int s,int t) {

if (s==t)

r1[s]=r[s];

else

{

mergesort(r,r2,s,s+t/2);

mergesort(r,r2,s+t/2+1,t);

merge(r2,s,s+t/2,t,r1);

}

}

快速排序

int Partition (RedType R[], int low, int high) {

R[0] = R[low]; pivotkey = R[low].key; // 枢轴 while (low<high) {

while(low<high&& R[high].key>=pivotkey)

-- high; // 从右向左搜索

R[low] = R[high];

while (low<high && R[low].key<=pivotkey) ++ low; // 从左向右搜索

R[high] = R[low];

}

R[low] = R[0]; return low;

}// Partition

void QSort ( SqList &L, int low, int high ) {

//对顺序表L中的子序列r[ low…high] 作快速排序 if ( low < high) {//长度>1

pivot = Partition ( L, low, high );

//一趟快排，将r[ ]一分为二

QSort ( L, low, pivot-1);

//在左子区间进行递归快排，直到长度为1

QSort ( L, pivot+1, high );

//在右子区间进行递归快排，直到长度为1

}

}

冒泡排序

void bubble_sort(SqList *L)

{ int m,i,j,flag=1;

RecordType x;

m=n-1;

while((m>0)&&(flag==1))

{flag=0;

for(j=1;j<=m;j++)

if(L->r[j].key>L->r[j+1].key)

{ flag=1;

x=L->r[j];

L->r[j]=L->r[j+1];

L->r[j+1]=x;

}

m--;

}

}

直接插入排序

void InsertionSort ( SqList &L ) {

// 对顺序表 L 作直接插入排序。 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]; // 插入到正确位置 }

}

 

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

/*测试数据：生成exe文件后，直接把测试数据粘贴到dos窗口上即可！105 7 1 6 8 4 0 9 3 211 87 65 32 45 78 20 36 28 945 7 1 6 8 4 0 9 3 211 87 65 32 45 78 20 36 28 9411 87 65 32 45 78 20 36 28 94105 7 1 6 8 4 0 9 3 211 87 65 32 45 78 20 36 28 9436*/#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号单元用作哨兵int length;}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-1while(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-- )

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;}//Partitionvoid 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); //对右序列同样处理}}//QSortvoid 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;}//HeapAdjustvoid 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] = InitList[i]; i++; k++; }else { mergedList [k] = InitList[j]; j++; k++; }//以下两个while每次只可能执行一个。 while ( i <= mid ){ mergedList[k] =

InitList[i]; i++; k++; }//将mid前剩余的并入while ( j <= right ){ mergedList[k] = InitList[j]; j++; k++; } //将mid后剩余的并入} void MergePass ( SortData initList[ ], SortData mergedList[ ], int len,int n ) {int i = 0;while (i+2*len-1 <= n-1) {merge( initList, mergedList, i, i+len-1, i+2*len-1);i += 2 * len; //循环两两归并}//以下是在处理尾巴 if ( i+len <= n-1 )merge( initList, mergedList, i, i+len-1, n-1);else for ( int j = i; j <= n-1; j++)mergedList [j] = initList[j];} void MergeSort (SortData initList[ ], int n ) {//按对象排序码非递减的顺序对表中对象排序SortData tempList[n];int len = 1;while ( len < n ) {MergePass ( initList, tempList, len, n );len *= 2; MergePass ( tempList, initList, len, n );len *= 2;}}//*********************************************************//******二分查找的递归实现************************** int BinCheck(SortData L[], int k,int low ,int high){if(low<=high){int mid=(low+high)/2;if(L[mid]==k){return mid;}else if(k>L[mid]){return BinCheck(L,k,mid+1,high);}else{return BinCheck(L,k,low,mid-1);}}return -1;}//**********************************************************//***********************************************************int main(){int i,j;SqList L;cin>>L.length;for(i =1; i<=L.length; i++){cin>>L.r[i].key;}InsertSort(L);cout<<"直接插入排序后：";for(i =1; i<=L.length; i++){cout << L.r[i].key;}cout<<endl<<endl;//********************************for(i =1; i<=L.length; i++){cin>>L.r[i].key;}BInsertSort(L);cout<<"折半插入排序后：";for(i =1; i<=L.length; i++){cout << L.r[i].key<<" ";}cout<<endl <<endl;//*********************************SortData V[10]={5, 4, 0, 3, 7, 9, 2, 1, 8, 6};cout<<"希尔排序之前的数组：";for(i=0; i<10; i++){cout<<V[i]<<" "; }ShellSort(V,10);cout<<endl<<"希尔排序之后的数组：";for(i=0; i<10; i++){cout<<V[i]<<" "; }cout<<endl<<endl;//***************************************************for(i=0; i<10; i++){cin>>V[i];}cout<<"冒泡排序之前的数组：";for(i=0; i<10; i++){cout<<V[i]<<" "; }BubbleSort(V,10);cout<<endl<<"冒泡排序之后的数组：";for(i=0; i<10; i++){cout<<V[i]<<" "; }cout<<endl<<endl;//*****************************************for(i =1; i<=L.length; i++){cin>>L.r[i].ke

y;}QuickSort(L);cout<<"快速排序后："; for(i =1; i<=L.length; i++){cout << L.r[i].key<<" ";}cout<<endl <<endl;//***************************************************for(i=0; i<10; i++){cin>>V[i];}cout<<"直接选择排序之前的数组：";for(i=0; i<10; i++){cout<<V[i]<<" "; }SelectSort(V,10);cout<<endl<<"直接选择排序之后的数组：";for(i=0; i<10; i++){cout<<V[i]<<" "; }cout<<endl<<endl;//***********************************************************HeapType H;cin>>H.length;for(i=1; i<=H.length; i++){cin>>H.r[i].key;}HeapSort(H);cout<<endl<<"堆排序之后的数组：";for(i=1; i<=H.length; i++){cout<<H.r[i].key<<" "; }cout<<endl<<endl;//***************************************************************for(i=0; i<10; i++){cin>>V[i];}cout<<"归并排序之前的数组：";for(i=0; i<10; i++){cout<<V[i]<<" "; }MergeSort(V,10);cout<<endl<<"归并排序之后的数组：";for(i=0; i<10; i++){cout<<V[i]<<" "; }cout<<endl<<endl;//********************************************cout<<"以下为折半查找的递归实现"<<endl;int kk;cin>>kk;cout<<BinCheck(V,kk,0,9)<<endl;system("pause");return 0;}