数据结构之内排序（包括快速排序，希尔，归并排序，插入排序，选择排序等）

目录

#include /// ........................................................................................................................ 1 包含的头文件及定义结构体 ................................................................................................... 1 快速排序 //排序的记录类型定义 ........................................................................................ 1 直接插入排序 ................................................................................................................................... 2 插入排序的改版 ............................................................................................................................... 3 归并排序........................................................................................................................................... 4 希尔排序算法 ................................................................................................................................... 5 选择排序........................................................................................................................................... 5 基数排序........................................................................................................................................... 7

///这么多的排序,只有归并排序过了

#include ///

包含的头文件及定义结构体

#include //#define MaxSize 20

typedef int KeyType; //定义关键字类型 typedef char InfoType[10];

typedef struct //记录类型 { KeyType key; //关键字项 InfoType data; //其他数据项,类型为InfoType } RecType;

///快速排序 //排序的记录类型定义

void QuickSort(RecType R[],int s,int t) //对R[s]至R[t]的元素进行快速排序 { int i=s,j=t; RecType tmp; if (s

}

}

tmp=R[s]; //用区间的第1个记录作为基准 while (i!=j) //从区间两端交替向中间扫描,直至i=j为止 { while(j>i && R[j].key>tmp.key) j--; //从右向左扫描,找第1个小于tmp.key的R[j] R[i]=R[j]; //找到这样的R[j],R[i]\交换 while (i

R[i]=tmp;

QuickSort(R,s,i-1); //对左区间递归排序 QuickSort(R,i+1,t); //对右区间递归排序

///直接插入排序

void sift(RecType R[],int low,int high) {

int i=low,j=2*i; //R[j]是R[i]的左孩子 RecType temp=R[i]; while (j<=high) { if (j

R[i]=temp; //被筛选结点的值放入最终位置 }

void InsertSort(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i,j,k; RecType temp; for (i=1;i

}

temp=R[i];

j=i-1; //从右向左在有序区R[0..i-1]中找R[i]的插入位置 while (j>=0 && temp.key

R[j+1]=R[j]; //将关键字大于R[i].key的记录后移 j--; }

R[j+1]=temp; //在j+1处插入R[i] //printf(\

}

for (k=0;k

///插入排序的改版

void InsertSort1(RecType R[],int n) //对R[0..n-1]按递增有序进行直接插入排序 { int i,j,low,high,mid; RecType tmp; for (i=1;i=high+1;j--) R[j+1]=R[j]; R[high+1]=tmp; //printf(\ } for (j=0;j

}

///归并排序

void Merge(RecType R[],int low,int mid,int high) { RecType *R1;

int i=low,j=mid+1,k=0; //k是R1的下标,i、j分别为第1、2段的下标 R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); //动态分配空间 while (i<=mid && j<=high) //在第1段和第2段均未扫描完时循环 if (R[i].key<=R[j].key) //将第1段中的记录放入R1中 { R1[k]=R[i]; i++;k++; } else //将第2段中的记录放入R1中 { R1[k]=R[j]; j++;k++; } while (i<=mid) //将第1段余下部分复制到R1 { R1[k]=R[i]; i++;k++; }

//将第2段余下部分复制到R1

while (j<=high) { R1[k]=R[j]; j++;k++; }

for (k=0,i=low;i<=high;k++,i++) //将R1复制回R中 R[i]=R1[k]; }

void MergeSortDC(RecType R[],int low,int high) //对R[low..high]进行二路归并排序 { int mid; if (low

}

void MergeSort1(RecType R[],int n) { MergeSortDC(R,0,n-1); }

//自顶向下的二路归并算法

希尔排序算法

void ShellSort(RecType R[],int n) // { int i,j,gap,k; RecType tmp; gap=n/2; //增量置初值 while (gap>0) { for (i=gap;i=0 && tmp.key

选择排序

void SelectSort(RecType R[],int n) { int i,j,k,l; RecType temp; for (i=0;i

本文来源：https://www.bwwdw.com/article/4892.html