[C++知识库]基础排序 自练

1.优化冒泡?

#include<stdio.h>
#include<stdlib.h>
#define MAX_size 100
typedef struct{
    int a[MAX_size];
    int length;
}SqLiszt;
void
swap(SqLiszt *L,int i,int j){
    int temp = L->a[i];
    L->a[i]= L->a[j];
    L->a[j]= temp;
}
void 
Bubble_sort(SqLiszt *L){
      int i,j,flag = 1;
       for(i=1;i<L->length && flag ;i++){
           flag = 0;
             for(j=L->length-1;j>=i;j--){ //从后往前 小的在当前j  是下一轮的j+1  
                  if(L->a[j]>L->a[j+1]){
                        swap(L,j,j+1);
                        flag =1;
                  }
             }
       }

}

int main(){
     SqLiszt L;
     L.length =0; //要初始化 为 0！！！！！
     int temp;
        for(int i =1;i<=10;i++){
              scanf("%d",&temp);
              L.a[i] = temp;
              L.length ++;
        }

         Bubble_sort(&L);
        printf("排序后的结果为：\n");
             for(int i= 1; i<=L.length;i++){
                  printf("%d ",L.a[i]);
             }

    return 0;
}

2.直接插入排序?

#include<stdio.h>
#include<stdio.h>
#define MAX_size 100
typedef struct{
    int a[MAX_size];
    int length;
}SqLiszt;
void
swap(SqLiszt *L,int i,int j){
    int temp = L->a[i];
    L->a[i]= L->a[j];
    L->a[j]= temp;
}
void 
Insert_sort(SqLiszt *L){
    int i ,j;
     for(i=2;i<=L->length;i++){ // [0] 做额为空间  【1】 相当于已经排好
            if( L->a[i-1]>L->a[i] ){
                  L->a[0] = L->a[i];
                   for(j=i-1; L->a[j]>L->a[0] ;j--){//如果大于插入的 向后移一位
                          L->a[j+1]=L->a[j];
                   }
                      L->a[j+1]= L->a[0];   //最后j-- 定位到比插入的值小的位置 
            }
          
     }
}
int main(){
     SqLiszt L;
     L.length =0; //要初始化 为 0！！！！！
     int temp;
        for(int i =1;i<=10;i++){
              scanf("%d",&temp);
              L.a[i] = temp;
              L.length ++;
        }

        Insert_sort(&L);
        printf("排序后的结果为：\n");
             for(int i= 1; i<=L.length;i++){
                  printf("%d ",L.a[i]);
             }

    return 0;
}

3.shell?

#include<stdio.h>
#include<stdio.h>
#define MAX_size 100
typedef struct{
    int a[MAX_size];
    int length;
}SqLiszt;
void 
Shell_sort(SqLiszt *L){
    int increment = L->length;
    int j,i;
      do{
           increment /=2;//初始分为五组， 增量越小 一组内元素越多
            for( i= increment+1; i<=L->length; i++){ //排一次 基本有序 
                  if( L->a[i]<L->a[i-increment] ){ // 将 a【i】 插入到自己的增量组中
                       L->a[0]= L->a[i];
                        for(j=i-increment;j>0 &&  L->a[j] > L->a[0] ;j-=increment){
                                 L->a[j+increment]= L->a[j]; //初始 j 就是上一个位置 ，所以要加步长才是原本要插入的位置  --》 增量组整体后移
                        }
                           L->a[j+increment]= L->a[0];
                  }
            }
      } while(increment >1 ); //增量为 1 才结束 表示分为一个组
}
int main(){
     SqLiszt L;
     L.length =0; //要初始化 为 0！！！！！
     int temp;
        for(int i =1;i<=10;i++){
              scanf("%d",&temp);
              L.a[i] = temp;
              L.length ++;
        }

        Shell_sort(&L);
        printf("排序后的结果为：\n");
             for(int i= 1; i<=L.length;i++){
                  printf("%d ",L.a[i]);
             }

    return 0;
}