网址我的上网主页,seo培训中心,做食材的网站,十个知名的跨境电商公司排序算法#xff1a;交换类排序#xff0c;插入类排序、选择类排序、归并类排序
交换类排序#xff1a;冒泡排序、快速排序
一、冒泡排序 #include stdio.h
#include stdlib.h
#include time.h
typedef int ElemType;
typedef struct{ElemType *e…排序算法交换类排序插入类排序、选择类排序、归并类排序
交换类排序冒泡排序、快速排序
一、冒泡排序 #include stdio.h
#include stdlib.h
#include time.h
typedef int ElemType;
typedef struct{ElemType *elem; //整形指针,申请的堆空间的起始地址存入elem int TableLen; //存储动态数组里边元素的个数
}SSTable;void ST_Init(SSTable ST,int len){ST.TableLenlen;ST.elem(ElemType *)malloc(sizeof(ElemType)*ST.TableLen);int i;srand(time(NULL)); //随机数生成for(i0;iST.TableLen;i){ST.elem[i]rand()%100;}
}void ST_print(SSTable ST){int i;for(i0;iST.TableLen;i){printf(%3d,ST.elem[i]);}printf(\n);
}void swap(ElemType a,ElemType b){ElemType tmp;tmpa;ab;btmp;
} //两层循环
//优先写内层循环再写外层循环
void BubbleSort(ElemType A[],int n){int i,j;bool flag; for(i0;in-1;i){ //控制的是有序数的数目flagfalse; for(jn-1;ji;j--){ //内层控制比较和交换 if(A[j-1]A[j]){swap(A[j-1],A[j]);flagtrue;}}if(flagfalse){ //如果一趟没有发生任何交换说明数组有序提前结束排序return; }}
}int main(){SSTable ST;ST_Init(ST,10); ST_print(ST);BubbleSort(ST.elem,10); ST_print(ST);return 0;
} 时间复杂度内层是ji外层是从0到n-1运行的总次数是1234...n-1,即O()
空间复杂度O(1)没有使用额外空间不会因为n的变化而变化
如果数组本身有序最好的时间复杂度是O(n)
二、快速排序
核心分治思想
#include stdio.h
#include stdlib.h
#include time.h
typedef int ElemType;
typedef struct{ElemType *elem; //整形指针,申请的堆空间的起始地址存入elem int TableLen; //存储动态数组里边元素的个数
}SSTable;void ST_Init(SSTable ST,int len){ST.TableLenlen;ST.elem(ElemType *)malloc(sizeof(ElemType)*ST.TableLen);int i;srand(time(NULL)); //随机数生成for(i0;iST.TableLen;i){ST.elem[i]rand()%100;}
}void ST_print(SSTable ST){int i;for(i0;iST.TableLen;i){printf(%3d,ST.elem[i]);}printf(\n);
}void swap(ElemType a,ElemType b){ElemType tmp;tmpa;ab;btmp;
} int Partition(ElemType A[],int low,int high){ElemType pivotA[low]; //拿最左边的作为分割值并存储下来 while(lowhigh){while(lowhighA[high]pivot){ //从后往前遍历找到一个比分割值小的 --high;}A[low]A[high]; while(lowhighA[low]pivot){low;}A[high]A[low];}A[low]pivot;return low; //返回分割值所在的下标
}//递归实现
void QuickSort(ElemType A[],int low,int high){if(lowhigh){int pivotposPartition(A,low,high);QuickSort(A,low,pivotpos-1);QuickSort(A,pivotpos1,high);}
} int main(){SSTable ST;ST_Init(ST,10); ST_print(ST);QuickSort(ST.elem,0,9); ST_print(ST);return 0;
}
空间复杂度与n有关
三、插入排序
插入排序直接插入排序、折半插入排序、希尔排序
直接插入排序 #include stdio.h
#include stdlib.h
#include time.h
typedef int ElemType;
typedef struct{ElemType *elem; //整形指针,申请的堆空间的起始地址存入elem int TableLen; //存储动态数组里边元素的个数
}SSTable;void ST_Init(SSTable ST,int len){ST.TableLenlen;ST.elem(ElemType *)malloc(sizeof(ElemType)*ST.TableLen);int i;srand(time(NULL)); //随机数生成for(i0;iST.TableLen;i){ST.elem[i]rand()%100;}
}void ST_print(SSTable ST){int i;for(i0;iST.TableLen;i){printf(%3d,ST.elem[i]);}printf(\n);
}void InsertSort(ElemType *arr,int n){int i,j,insertVal;for(i1;in;i){ //控制要插入的数 insertValarr[i]; //先保存要插入的值//内层控制比较往后覆盖 for(ji-1;j0arr[j]insertVal;j--){arr[j1]arr[j];} arr[j1]insertVal;}
}int main(){SSTable ST;ST_Init(ST,10); ST_print(ST);InsertSort(ST.elem,10); ST_print(ST);return 0;
}
