排序算法

排序算法

堆排序

#include<stdio.h>

const int NN=100010;
int heap[NN],n;

void adjust_heap(int low,int high){
    int i=low,j=i*2;
    while(j<=high){
        if(j+1<=high&&heap[j+1]>heap[j]) j=j+1;
        if(heap[j]>heap[i]){
            int t=heap[i];heap[i]=heap[j];heap[j]=t;
            i=j;
            j=j*2;
        }
        else break;
    }
}

void create_heap(){
    for(int i=n/2;i>=1;i--){
        adjust_heap(i,n);
    }
}

void swap_heap(int last){
    int t=heap[1];
    heap[1]=heap[last];
    heap[last]=t;
    adjust_heap(1,last-1);
}

void heap_sort(){
    create_heap();
    printf("初始大根堆：\n");
    for(int i=1;i<=n;i++) printf("%d ",heap[i]);
    printf("\n每趟调整后的序列：\n");
    for(int i=n;i>1;i--){
        swap_heap(i);
        for(int i=1;i<=n;i++) printf("%d ",heap[i]);
        printf("\n");
    }
    printf("最后的有序序列：\n");    
    for(int i=1;i<=n;i++) printf("%d ",heap[i]);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&heap[i]);
    heap_sort();
}

快速排序

#include<stdio.h>

const int NN=100010;
int a[NN],n;

int partition(int left,int right){
    int flag=a[left];
    while(left<right){
        while(left<right&&a[right]>flag) right--;
        a[left]=a[right];
        while(left<right&&a[left]<=flag) left++;
        a[right]=a[left];
    }
    a[left]=flag;
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    printf("\n");
    return left;
}

void quick_sort(int left,int right){
    if(left<right){
        int op=partition(left,right);
        quick_sort(left,op-1);
        quick_sort(op+1,right);
    }
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    printf("每趟排序后结果：\n");
    quick_sort(1,n);
    printf("最终结果：\n");
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}

希尔排序

#include<stdio.h>

const int NN=100010;
int a[NN],d[NN],n,t;

void shell_insert(int d){
    int i,j;
    for(i=1+d;i<=n;i++){
        if(a[i-d]>a[i]){
            int temp=a[i];
            for(j=i-d;j>0&&temp<a[j];j-=d){
                a[j+d]=a[j];
            }
            a[j+d]=temp;
        }
    }
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
    printf("\n");
}

void shell_sort(){
    for(int i=0;i<t;i++){
        shell_insert(d[i]);
    }
}

int main(){
    printf("请输入关键字数量：\n");
    scanf("%d",&n);
    printf("请输入关键字序列：\n");
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    printf("请输入所选取增量的数量：\n");
    scanf("%d",&t);
    printf("请输入选取的增量：\n");
    for(int i=0;i<t;i++) scanf("%d",&d[i]);
    printf("每趟排序后结果：\n");
    shell_sort();
    printf("最终结果：\n");
    for(int i=1;i<=n;i++) printf("%d ",a[i]);
}