C语言实现各种排序

时间:2024-04-29 11:17:07

文章目录

  • C语言实现各种排序
    • 1、冒泡排序
    • 2、简单选择排序
    • 3、直接插入排序
    • 4、希尔排序
    • 5、快速排序
    • 6、堆排序

C语言实现各种排序

1、冒泡排序

冒大泡(将大的数往后放)

void bubble_sort(int *p,int len){
    for(int i=0;i<len-1;i++){
        for(int j=0;j<len-1-i;j++){
            if(*(p+j)>*(p+j+1)){
                //使用异或运算交换两个的值
                *(p+j)=*(p+j)^*(p+j+1);
                *(p+j+1)=*(p+j)^*(p+j+1);
                *(p+j)=*(p+j)^*(p+j+1);
            }
        }
    }
    return;
}

2、简单选择排序

每次选择一个数组中最大的数或者最小的数与最最后面或最前面的数进行交换

void simple_select_sort(int *p,int len){
int i=0,j=0,k=0;
for(;i<len-1;i++){
    k=i;//k记录起始值
    for(j=i+1;j<len;j++){
        if(*(p+k)>*(p+j)){
            k=j;
        }
    }
    if (k!=i)
    {//交换值
      exchange(p+k,p+i);
    }
    

}
}

3、直接插入排序

void insert_sort(int *p,int len){
int i=0,j=0,temp=0;

for(i=1;i<len;i++){
        temp=*(p+i);
        for (j = i-1; j>=0&&*(p+j)>=temp; j--)
        {
            *(p+j+1)=*(p+j);
        }
         *(p+j+1)=temp;
   
}

}

4、希尔排序

void shell_sort(int *p,int len){
int temp;
int i,j,k;
//k表示分组
for(k=len/2;k>=1;k=k/2){
  for(i=k+1;i<len;i++){
      temp=*(p+i);
      for(j=i-k;j>=0&&*(p+j)>temp;j=j-k){
       *(p+j+k)=*(p+j);
    }
      *(p+j+k)=temp;
    }

}


}

5、快速排序

void quick_sort(int *p,int low,int height){
    int i=low,j=height;
    int key=p[low];
    while(i<j){
        while(i<j&&p[j]>=key){
            j--;
        }
        if (i<j)
        {
            p[i]=p[j];
        }
        while(i<j&&p[i]<=key){
            i++;
        }
        if(i<j){
            p[j]=p[i];
        }        
    }
    p[i]=key;
    if (low<j-1)
    { quick_sort(p, low, j-1);
    }
    if (height>i+1)
    {
     quick_sort(p, i+1,height);
    }
    
    return;



}

6、堆排序

第一个非叶子结点的编号为len/2-1

void heap_sort(int *p,int len){
    int i=0;
    for(i=len/2-1;i>=0;i--){
        heap_adjust(p,i,len-1);
    }
    //将第一个与最后一个交换
    for (i=len-1;i>0;i--)
    {
        exchange(&p[0],&p[i]);//交换值
        heap_adjust(p,0,i-1);
    }
    
}
void heap_adjust(int *p,int start,int end){
    int father_node=start;
    int son_node=father_node*2+1;
    while (son_node<=end)
    {
        //选出子节点最大的那一个
        if (son_node+1<=end&&p[son_node+1]>p[son_node])
        {son_node++;
        }
        if (p[father_node]>p[son_node])
        {
            return;
        }
        else{
            exchange(&p[father_node],&p[son_node]);
            father_node=son_node;
            son_node=father_node*2+1;
        }
        
        
    }
    

}