王道考研 数据结构之排序
排序知识点思维导图
排序代码实现
一、插入排序
1. 直接插入排序
//从小到大排序
void InsertSort(ElemType A[],int n){
//直接插入排序
int i,j;
for(i=2;i<=n;i++){ //默认第一个元素排好序，从第二个元素开始一次往后排序
//如果为递增序列直接后移看下一个元素；如果不为，则进行调整
if(A[i]<A[i-1]){
//将此元素复制为哨兵
A[0]=A[i];
//前面为已拍好序序列，从后往前查找待插入位置，边查边向后挪位，
for(j=i-1;A[0]<A[j];--j)
A[j+1]=A[j]; //边查边挪
//直到待查元素小于有序列中的元素，即将待查元素插入查找到的位置
A[j+1]=A[0];
}
}
2. 折半插入排序
//从小到大排序
void InsertSort(ElemType A[],int n){
//折半插入排序
int i,j,low,high,mid;
for(i=2;i<=n;i++){ //依次将A[2]~A[n]插入到前面已拍好序序列
A[0]=A[i]; //将A[i]暂存到A[0]
low = 1;high = i-1; //折半查找范围
while(low<=high){
mid = (low+high)/2; //取中间点
if(A[mid] > A[0])
high = mid-1; //查左子表
else
low = mid+1; //查右子表
}
//折半查找停止后在low所指位置插入元素，即high+1
for(j=i-1;j>=high+1;--j)
A[j+1]=A[j]; //统一后移元素，空出插入位置
A[high+1]=A[0]; //插入操作
}
}
3. 希尔排序
void ShellSort(ElemType A[],int n){
//希尔排序，对顺序表做希尔排序，比直接插入排序有如下修改
//1.前后记录的增量是dk，不是1
//2.A[0]只是暂存单元，不是哨兵，当j<=0时，就是插入位置
int i,j,dk; //dk为步长
for(dk = n/2;dk>=1;dk/2){ //步长变化
for(i = dk+1;i<=n;++i){
if(A[i]<A[i-dk]){ //需要将A[i]插入有序增量子表
A[0] = A[i]; //暂存A[0]
for(j = i-dk;j >0 && A[0]<A[j];j-=dk)
A[j+dk]=A[j]; //记录后移，查找插入元素的位置
A[j+dk]=A[0]; //插入元素
}//if
}
}
}
二、交换排序
1. 冒泡排序
//交换
void swap(&a,&b){
int temp = a;
a = b;
b = temp;
}
//从小到大排序 冒泡排序
void BubbleSort(ElemType A[],int n){
for(i=0;i<n-1;i++){
bool flag = false; //本趟冒泡排序是够发生交换标志
for(int j = n-1;j>i;j--) //一趟冒泡过程
if(A[j-1]>A[j]){ //逆序
swap(A[j-1],A[j]); //交换
flag = true; //本趟发生交换
}
if(flag == true)
return; //本趟遍历后没有发生交换说明表已经有序
}
}
2. 快速排序
void QuickSort(ElemType A[],int low,int high){
//快速排序
if(low<high){ //递归跳出条件
//Partition()就是划分操作，将表A[low...high]划分为满足上述条件的两个子表
int pivotpos = Partition(A,low,high); //划分
QuickSort(A,low,pivotpos-1);
QuickSort(A,pivotpos+1,high);
}
}
int Partition(ElemType A[],int low,int high){
//一趟排序过程（划分算法）
ElemType pivot = A[low]; //将当前表中第一个元素设为枢轴值，对表进行划分
while(low < high){ //循环跳出条件
while(low < high && A[high] >= pivot)
--hihg;
A[low] = A[high]; //将比枢轴值小的元素移动到左端
while(low < high && A[low] <= pivot)
++low;
A[high]=A[low]; //将比枢轴值大的元素移动到右端
}
A[low] = pivot; //将枢轴元素存放到最终位置
return low; //返回存放枢轴元素的位置
}
三、选择排序
1. 简单选择排序
void SelectSort(ElemType A[],int n){
//简单选择排序，从0开始存放元素
for(int i = 0; i <n-1; i++){//一共进行n-1趟
int min = i; //记录最小元素
for(int j = i+1 ;j < n;j++) //选择最小元素
if(A[j]<A[min])
min = j; //更新最小元素位置
if(min != i)
swap(A[i],A[min]); //与第i个位置互换
}
}
2. 堆排序
//建立大根堆
void BuildMaxHeap(ElemType A[],int len){ //从i = [n/2]~1,反复调整堆
for(i = len/2 ; i>0;i--)
AdjustDown(A,i,len);
}
void AdjustDown(ElemType A[],int k,int len){
//函数AdjustDown将元素k向下进行调整
A[0] = A[k]; //A[0]暂存
for(i = 2*k ;i<=len; i *=2){ //沿k较大的子节点向下筛选
if(i<len && A[i]<A[i+1])
i++; //取k较大的子节点的下标
if(A[0] >= A[i])
break; //筛选结束
else{
A[k] = A[i]; //将A[i]调整到双亲节点上
k = i; //修改k值，以便继续向下筛选
}
}//for
A[k] = A[0]; //被筛选结点的值放入最终位置
}
//堆排序算法
void HeapSort(ElemType A[], int len) {
//堆排序
BuildMaxHeap(A, len); //建立初始堆
for(int i = len; i > 1; i--){ //n-1趟的交换和建堆过程
swap(A[i],A[1]);//输出堆顶的元素(和堆底元素交换)
AdjustDown(A, 1, i - 1);//整理，把剩余的i-1个元素整理成堆
}
}
//向上调整堆的算法
void AdjustUp(ElemType A[],int k){//参数k为向上调整的结点，也为堆的元素个数
A[0] = A[k];
int i = k / 2; //若结点值大于双亲结点,则将双亲结点下调，并继续向上比较
while (i > 0 && A[i] < A[0]) {//循环退出条件
A[k] = A[i]; //双亲结点下调
k = i;
i = k / 2; //继续向上比较
}//while
A[k] = A[o]; //复制到最终位置
}
四、归并排序
ElemType *B = (ElemType *)malloc(n+1)*sizeof(ElemType));
//辅助函数B
void Merge(ElemType A[],int low,int mid,int high){
//表的两端A[low...mid],A[mid+1...high]各自有序，将它们合并成一个有序表
for(int k = low; k <= high; k++)
B[k] = A[k]; //将A中所有元素复制到B中
for(i = low,j = mid+1,k=i;i<=mid&&j<=high;k++){
if(B[i]<=B[j]) //比较B的左右两段中的元素
A[k]=B[i++]; //将较小值复制到A中
else
A[k]=B[j++];
}//for
while(i<=mid)
A[k++]=B[i++]; //若第一个表未检测完，复制
while(j<=high)
A[k++]=B[j++]; //若第二个表未检测完，复制
}
void MergeSort(ElemType A[],int low,int high){
if(low <high){
int mid = (low + high)/2; //从中间划分两个子序列
MergeSort(A,low,mid); //对左侧子序列进行递归排序
MergeSort(A,mid+1,high); //对右侧子序列进行递归排序
Merge(A,low,mid,high); //归并
}
}
合集：
数据结构之线性表
数据结构之栈与队列
数据结构之串
数据结构之树与二叉树
数据结构之图
数据结构之查找
数据结构之排序