王道C语言C++版排序算法总结

2021-08-05 14:09:08

  1. 直接插入排序
    直接插入排序
    //直接插入排序
#include <stdio.h>
#include<stdlib.h>//malloc
#include <stdbool.h>
//直接插入排序
void InsertSort(int 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];
        }
    }

}
int main(){
int a[11],i,key,k;    
//定义数组及变量为基木整甩
printf("请输入10个数据：\n");
for (i =1;i<=10;i++)
    scanf("%d",&a[i]);    
//接收从键盘输入的10个数据到数组a中
printf("原始顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]);    
//将未排序前的顺序输出
InsertSort(a,10);//调用直接插入函数 printf("\n 插入数据排序后顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]); //将排序后的数组输出
printf("\n");
}
  1. 折半插入排序
    折半插入排序
    //折半插入排序
#include <stdio.h>
#include<stdlib.h>//malloc
#include <stdbool.h>
//折半插入排序
void InsertSortByHalf(int A[],int n) {
    int i,j,low,high,mid;
    for(i=2;i<=n;i++){
        A[0]=A[i];
        low=1;high=i-1;
        while(low<=high){
            mid =(low+high)/2;
            if(A[mid]>A[0]){
                high=mid-1;
            }
            else low=mid+1; }
        for(j=i-1;j>=high+1;j--)
        {
            A[j+1]=A[j];
        }
          A[high+1]=A[0];
    }
}
int main(){
int a[11],i,key,k;    
printf("请输入10个数据：\n");
for (i =1;i<=10;i++)
    scanf("%d",&a[i]);    
printf("原始顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]);    
//将未排序前的顺序输出
InsertSortByHalf(a,10);//调用折半查找函数 InsertSortByHalf
 printf("\n 插入数据排序后顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]); //将排序后的数组输出
printf("\n");
}
  1. 希尔排序
    希尔排序
    //希尔排序
#include <stdio.h>
#include<stdlib.h>//malloc
#include <stdbool.h>
void ShellSort(int A[],int n){
    int dk,i,j;
    for(dk=n/2;dk>=1;dk=dk/2){
        for(i=dk+1;i<=n;i++){
            if(A[i]<A[i-dk]){
                A[0]=A[i];
                for(j=i-dk;j>0&&A[0]<A[j];j-=dk){
                    A[j+dk]=A[j];
                }
                A[j+dk]=A[0];
            }
        }
    }
}
int main(){
int a[11],i,key,k;    
printf("请输入10个数据：\n");
for (i =1;i<=10;i++)
    scanf("%d",&a[i]);    
printf("原始顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]);    
//将未排序前的顺序输出
ShellSort(a,10);  //调用希尔排序ShellSort
 printf("\n 插入数据排序后顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]); //将排序后的数组输出
printf("\n");
}
  1. 冒泡排序
    冒泡排序
    //冒泡排序
#include <stdio.h>
#include<stdlib.h>//malloc
#include <stdbool.h>
//从左边向右冒泡
void BubbleSort (int a[],int n){
    int i,j,temp;
    for( i=0;i<n-1;i++){
        for(j=0;j<n-1-i;j++){
            if(a[j]>a[j+1]){
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }

        }
    }
}
//从右边向左边冒泡
void BubbleSort2(int a[],int n){
    int i,j,temp;
    for(i=0;i<n-1;i++){
        bool flag =false;
        for(j=n-1;j>i;j--){
            if(a[j-1]>a[j]){
                temp=a[j];
                a[j]=a[j-1];
                a[j-1]=temp;
                flag = true;
            }
        }
        if(flag==false){
            return;
        }
    }
}
int main(){
//测试冒泡
    int A[]={3,1,4,5,2};
    int n=sizeof(A)/sizeof(int);
      BubbleSort(A,n);
      BubbleSort2(A,n);
    for(int i=0;i<n;i++){
        printf("%d",A[i]);
    }
}
  1. 快速排序
    快速排序
    //快速排序     
#include <stdio.h>
#include<stdlib.h>//malloc
#include <stdbool.h>
int Partition (int A[],int low,int high){
    int pivot=A[low];
    while(low<high){
        while(low<high&&A[high]>=pivot){
            --high;
        }
        A[low]=A[high];
        while(low<high&&A[low]<=pivot){
            ++low;
        }
        A[high]=A[low];
    }
    A[low]=pivot;
    return low;
}
void QuickSort(int A[],int low,int high){
    if(low<high){
        int pivotpos=Partition(A,low,high);
        QuickSort(A,low,pivotpos-1);
        QuickSort(A,pivotpos+1,high);
    }
}
两种main

int main(){
//测试选择
    int A[]={3,1,4,5,2};
    int n=sizeof(A)/sizeof(int);
QuickSort(A,0,4);
     for(int i=0;i<n;i++){
        printf("%d",A[i]);
    }
}

int main(){
int a[11],i,key,k;    
printf("请输入10个数据：\n");
for (i =1;i<=10;i++)
    scanf("%d",&a[i]);    
printf("原始顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]);    
//将未排序前的顺序输出
QuickSort(a,1,10);
 printf("\n 插入数据排序后顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]); //将排序后的数组输出
printf("\n");
}
  1. 简单选择排序
    简单选择排序
    //简单选择排序 
#include <stdio.h>
#include<stdlib.h>//malloc
#include <stdbool.h>
//简单选择排序
void SelectSort(int A[],int n){
    int i,j,min,temp;
    for(i=0;i<n-1;i++){
        min=i;
        for(j=i+1;j<n;j++)
        {if(A[j]<A[min]) min=j;}
        if(min!=j){
            temp=A[i];
            A[i]=A[min];
            A[min]=temp;
        }

    }
}
int main(){
//测试选择
    int A[]={3,1,4,5,2};
    int n=sizeof(A)/sizeof(int);
SelectSort(A,n);
    for(int i=0;i<n;i++){
        printf("%d",A[i]);
    }
}

8.堆排序
堆排序
//堆排序

#include <stdio.h>
#include<stdlib.h>//malloc
#include <stdbool.h>
void AdjustDown(int A[],int k,int len){
 A[0]=A[k];
    for(int i=2*k;i<=len;i*=2){
        if(i<len&&A[i]<A[i+1]){
            i++;
        }
        if(A[0]>=A[i])
        {break;}
        else{
            A[k]=A[i];
            k=i;
        }
    }
    A[k]=A[0];
}
void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--){
        AdjustDown(A,i,len);
    }
}
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);
    for(int i=len;i>1;i--){
//空出第一个位置来做交换
        int temp=A[i];
        A[i]=A[1];
        A[1]=temp;
        AdjustDown(A,1,i-1);
    }
}

int main(){
int a[11],i,key,k;    
printf("请输入10个数据：\n");
for (i =1;i<=10;i++)
    scanf("%d",&a[i]);    
printf("原始顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]);    
//将未排序前的顺序输出
HeapSort(a,10);
 printf("\n 插入数据排序后顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]); //将排序后的数组输出
printf("\n");
}

9.归并排序
归并排序
//归并排序

//int a[10] 和 int *a = malloc(10 * sizeof(int)) 的效果是一样的。
//都是在内存中申请10个连续的、每个大小为sizeof(int)的内存

int B[];
//int *B=(int *)malloc((n+1)* sizeof(int));
void Merge(int A[],int low,int mid,int high){
    int i,j,k;
    //int n=sizeof(A)/sizeof(int);
    //int B[n];
    for( k=low;k<=high;k++){
        B[k]=A[k];
    }
    for( i=low,j=mid+1,k=i;i<=mid&&j<=high;k++){
        if(B[i]<=B[j])
            A[k]=B[i++];
        else
            A[k]=B[j++];
    }
    while(i<=mid) A[k++]=B[i++];
    while(j<=high) A[k++]=B[j++];
}
void MergeSort(int 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);
    }
}
int main(){
int a[11],i,key,k;    
printf("请输入10个数据：\n");
for (i =1;i<=10;i++)
    scanf("%d",&a[i]);    
printf("原始顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]);    
//将未排序前的顺序输出
MergeSort(a,1,10);//调用归并排序MergeSort
 printf("\n 插入数据排序后顺序：\n");
for(i=1;i<11;i++)
    printf("%5d",a[i]); //将排序后的数组输出
printf("\n");
}
上一篇：【全程NOIP计划】图论算法


下一篇：Java笔试题做题笔记（一）