90做网站,三端互通的传奇手游发布网,中建卓越建设有限公司网站首页,网络服务器可提供的常见服务哪四个目录
交换排序
冒泡排序
快速排序
插入排序
直接插入排序
选择排序
简单选择排序
堆排序
归并排序
各种排序的时间复杂度、空间复杂度、稳定性和复杂度
快排真题2016
选排真题2022 排序算法分为交换类排序、插入类排序、选择类排序、归并类排序。 交换排序
交换排…目录
交换排序
冒泡排序
快速排序
插入排序
直接插入排序
选择排序
简单选择排序
堆排序
归并排序
各种排序的时间复杂度、空间复杂度、稳定性和复杂度
快排真题2016
选排真题2022 排序算法分为交换类排序、插入类排序、选择类排序、归并类排序。 交换排序
交换排序分为冒泡排序、快速排序。
冒泡排序
#include stdio.h
#include stdlib.h
#include time.htypedef int ElemType;
typedef struct {ElemType *elem;//存储元素的起始地址int TableLen;//元素个数
} SSTable;void ST_Init(SSTable ST, int len) {ST.TableLen len;ST.elem (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);//申请一块堆空间当数组来使用int i;srand(time(NULL));//随机数生成每一次执行代码就会得到随机的10个元素for (i 0; i ST.TableLen; i) {ST.elem[i] rand() % 100;//生成的是0-99之间}
}//打印数组中的元素
void ST_print(SSTable ST) {for (int i 0; i ST.TableLen; i) {printf(%3d, ST.elem[i]);}printf(\n);
}//往往都是用两层循环
//优先去写内层循环再写外层循环
void BubbleSort(ElemType *A, int n) {int i, j;bool flag;for (i 0; i n - 1; i)//控制的是有序数的数目{flag false;for (j 0; j n - 1 - i; j)//内层控制比较和交换{if (A[j] A[j 1]) {//交换两个元素A[j] A[j] ^ A[j 1];A[j 1] A[j 1] ^ A[j];A[j] A[j 1] ^ A[j];flag true;}}if (false flag)//如果一趟比较没有发生任何交换说明数组有序提前结束排序{return;}}
}int main() {SSTable ST;ST_Init(ST, 10);ST_print(ST);//随机后的结果打印BubbleSort(ST.elem, 10);ST_print(ST);//排序后再次打印return 0;
}快速排序 #include stdio.h
#include stdlib.h
#include time.h
#include string.htypedef int ElemType;
typedef struct {ElemType *elem;//存储元素的起始地址int TableLen;//元素个数
} SSTable;void ST_Init(SSTable ST, int len) {ST.TableLen len;ST.elem (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);//申请一块堆空间当数组来使用int i;srand(time(NULL));//随机数生成每一次执行代码就会得到随机的10个元素for (i 0; i ST.TableLen; i) {ST.elem[i] rand() % 100;//生成的是0-99之间}
}//打印数组中的元素
void ST_print(SSTable ST) {for (int i 0; i ST.TableLen; i) {printf(%3d, ST.elem[i]);}printf(\n);
}//快排的核心函数
//挖坑法
int partition(ElemType *A, int low, int high) {ElemType pivot A[low];//拿最左边的作为分割值并存储下来while (low high) {while (low high A[high] pivot)//从后往前遍历找到一个比分割值小的high--;A[low] A[high];//把比分隔值小的那个元素放到A[low]while (low high A[low] pivot)//从前往后遍历找到一个比分割值大的low;A[high] A[low];//把比分隔值大的那个元素放到A[high],因为刚才high位置的元素已经放到了low位置}A[low] pivot;//把分割值放到中间位置因为左边刚好都比它小右边都比它大return low;//返回分隔值所在的下标
}void QuickSort(ElemType *A, int low, int high) {if (low high) {int pivot_pos partition(A, low, high);//pivot用来存分割值的位置QuickSort(A, low, pivot_pos - 1);//前一半继续递归排好QuickSort(A, pivot_pos 1, high);}
}int main() {SSTable ST;ST_Init(ST, 10);//初始化ST_print(ST);QuickSort(ST.elem, 0, 9);//注意这个位置是n-1,也就是9因为函数里取了high位置的值ST_print(ST);return 0;
}插入排序
插入排序分为直接插入排序、折半插入排序、希尔排序。
直接插入排序
#include stdio.h
#include stdlib.h
#include time.htypedef int ElemType;
typedef struct {ElemType *elem;//整型指针int TableLen;
} SSTable;void ST_Init(SSTable ST, int len) {ST.TableLen len;//申请10个元素的空间ST.elem (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);int i;srand(time(NULL));for (i 0; i ST.TableLen; i) {ST.elem[i] rand() % 100;//随机了10个数}
}void ST_print(SSTable ST) {for (int i 0; i ST.TableLen; i) {printf(%3d, ST.elem[i]);}printf(\n);
}void InsertSort(ElemType *A, int n) {int i, j, insertVal;for (i 1; i n; i)//外层控制要插入的数{insertVal A[i];//保存要插入的数//内层控制比较,j要大于等于0同时arr[j]大于insertval时arr[j]位置元素往后覆盖for (j i - 1; j 0 A[j] insertVal; j--) {A[j 1] A[j];}A[j 1] insertVal;//把要插入的元素放到对应的位置}
}int main() {SSTable ST;ST_Init(ST, 10);//申请10个元素空间ST_print(ST);//排序前打印InsertSort(ST.elem, 10);ST_print(ST);//排序后再次打印return 0;
}选择排序
选择排序分为简单选择排序、堆排序。
简单选择排序
#include stdio.h
#include stdlib.h
#include time.h
#include string.h
typedef int ElemType;
typedef struct{ElemType *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)
{for(int i0;iST.TableLen;i){printf(%3d,ST.elem[i]);}printf(\n);
}
void swap(ElemType a,ElemType b)
{ElemType tmp;tmpa;ab;btmp;
}void SelectSort(ElemType* A,int n)
{int i,j,min;//min记录最小的元素的下标for(i0;in-1;i){mini;//我们认为i号元素最小for(ji1;jn;j)//找到从i开始到最后的序列的最小值的下标{if(A[j]A[min])//当某个元素A[j]小于了最小元素{minj;//将下标j赋值给minmin就记录下来了最小值的下标}}if(min!i){//遍历完毕找到最小值的位置后与A[i]交换这样最小值被放到了最前面swap(A[i],A[min]);}}
}int main() {SSTable ST;ST_Init(ST,10);//初始化ST_print(ST);SelectSort(ST.elem,10);ST_print(ST);return 0;
}堆排序 #include stdio.h
#include stdlib.h
#include time.h
#include string.htypedef int ElemType;
typedef struct {ElemType *elem;int TableLen;
} SSTable;void ST_Init(SSTable ST, int len)//申请空间并进行随机数生成
{ST.TableLen len;ST.elem (ElemType *) malloc(sizeof(ElemType) * ST.TableLen);int i;srand(time(NULL));for (i 0; i ST.TableLen; i) {ST.elem[i] rand() % 100;}
}void ST_print(SSTable ST) {for (int i 0; i ST.TableLen; i) {printf(%3d, ST.elem[i]);}printf(\n);
}void swap(ElemType a, ElemType b) {ElemType tmp;tmp a;a b;b tmp;
}//调整某个父亲节点王道书上的
void AdjustDown(ElemType A[], int k, int len) {int i;A[0] A[k];for (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(ElemType A[], int len) {for (int i len / 2; i 0; i--) {AdjustDown(A, i, len);}
}//王道书上的
void HeapSort(ElemType A[], int len) {int i;BuildMaxHeap(A, len);//建立大顶堆for (i len; i 1; i--) {swap(A[i], A[1]);AdjustDown(A, 1, i - 1);}
}//把某个子树调整为大根堆
void AdjustDown1(ElemType A[], int k, int len) {int dad k;//父亲的下标int son 2 * dad 1;//左孩子的下标while (son len) {//son可能也是最后一个元素在下面if中判断if (son 1 len A[son] A[son 1])//如果左孩子小于右孩子{son;//拿右孩子}if (A[son] A[dad])//如果孩子大于父亲{swap(A[son], A[dad]);//交换dad son;//son从新作为dad去判断下面的子树是否符合大根堆son 2 * dad 1;} else {break;}}
}void HeapSort1(ElemType A[], int len) {int i;//就是把堆调整为大根堆for (i len / 2 - 1; i 0; i--) {AdjustDown1(A, i, len);}swap(A[0], A[len - 1]);//交换根部元素和最后一个元素for (i len - 1; i 1; i--)//i代表的是剩余的无序数的数组的长度{AdjustDown1(A, 0, i);//调整剩余元素变为大根堆swap(A[0], A[i - 1]);//交换根部元素和无序数的数组的最后一个元素}
}int main() {SSTable ST;ST_Init(ST, 10);//初始化ElemType A[10] {3, 87, 2, 93, 78, 56, 61, 38, 12, 40};memcpy(ST.elem, A, sizeof(A));ST_print(ST);//HeapSort(ST.elem, 9);//王道书零号元素不参与排序考研考的都是零号元素要参与排序HeapSort1(ST.elem, 10);//所有元素参与排序ST_print(ST);return 0;return 0;
}归并排序 #include stdio.h
#include stdlib.h#define N 7
typedef int ElemType;
//合并两个有序数组
void Merge(ElemType A[],int low,int mid,int high)
{static ElemType B[N];//加static的目的是无论递归调用多少次都只有一个B[N]int i,j,k;for(ilow;ihigh;i)//把A[i]里的元素都给B[i]{B[i]A[i];}klow;//kij-mid-1for(ilow,jmid1;imidjhigh;)//合并两个有序数组{if(B[i]B[j]){A[k]B[i];i;k;}else{A[k]B[j];j;k;}}//把某一个有序数组中剩余的元素放进来while(imid)//前一半的有剩余的放入{A[k]B[i];i;k;}while(jhigh)//后一半的有剩余的放入{A[k]B[j];j;k;}
}//归并排序不限制是两两归并还是多个归并考研都是考两两归并
void MergeSort(ElemType A[],int low,int high)//递归分割
{if(lowhigh){int mid(lowhigh)/2;MergeSort(A,low,mid);//排序好前一半MergeSort(A,mid1,high);//排序好后一半Merge(A,low,mid,high);//讲两个排序好的数组合并}
}void print(int* a)
{for(int i0;iN;i){printf(%3d,a[i]);}printf(\n);
}
//归并排序
int main() {int A[N]{49,38,65,97,76,13,27};//数组7个元素MergeSort(A,0,6);print(A);return 0;
}各种排序的时间复杂度、空间复杂度、稳定性和复杂度 快排真题2016 #include stdio.h//考研初试只需要完成setPartition即可
int setPartition(int a[], int n) {int pivotkey, low 0, low0 0, high n - 1, high0 n - 1, flag 1, k n / 2, i;int s1 0, s2 0;while (flag)//当low等于k-1也就是n/2-1时分割结束{pivotkey a[low]; //选择枢轴while (low high) { //基于枢轴对数据进行划分while (low high a[high] pivotkey)--high;if (low ! high)a[low] a[high];while (low high a[low] pivotkey)low;if (low ! high)a[high] a[low];} //end of while(lowhigh)a[low] pivotkey;//把分割值放到对应的位置if (low k - 1)//如果枢轴是第 n/2 小元素划分成功{flag 0;} else {//是否继续划分if (low k - 1) {low0 low;//low0只是做暂存为下次使用准备这里我们low后low比分割值大1high high0;//把上次暂存的high0拿过来} else {low low0;//把上次暂存的low0拿过来high0 --high;//high0只是做暂存为下次使用准备}}}for (i 0; i k; i) {s1 a[i];}for (i k; i n; i) {s2 a[i];}return s2 - s1;
}int main() {int A[10] {4, 1, 12, 18, 7, 13, 18, 16, 2, 15};int difference;difference setPartition(A, 10);//考研初试只需要完成setPartition即可无需编写这个main函数printf(%d\n, difference);return 0;
}选排真题2022 #include stdio.h
#include stdlib.h
#include time.htypedef int ElemType;
typedef struct{ElemType *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();}
}
void ST_print(SSTable ST)
{for(int i0;i10;i){printf(%3d\n,ST.elem[i]);}printf(\n);
}
void swap(ElemType a,ElemType b)
{ElemType tmp;tmpa;ab;btmp;
}//调整子树
void AdjustDown(ElemType A[], int k, int len)
{int dad k;int son 2 * dad 1; //左孩子下标while (sonlen){if (son 1 len A[son] A[son 1])//看下有没有右孩子比较左右孩子选大的{son;}if (A[son] A[dad])//比较孩子和父亲如果孩子大于父亲那么进行交换{swap(A[son], A[dad]);dad son;//孩子重新作为父亲判断下一颗子树是否符合大根堆son 2 * dad 1;}else {break;}}
}
void HeapSort(ElemType A[], int len)
{int i;//先对前10个元素建立大根堆for (i len/2; i 0; i--){AdjustDown(A, i, len);}//比较剩余的A[10]到A[99999]元素小于堆顶就放入A[0],继续调整10个元素为大根堆for (i 10; i 100000; i){if (A[i] A[0]){A[0] A[i];AdjustDown(A, 0, 9);//继续调整为大根堆}}
}int main()
{SSTable ST;ST_Init(ST,100000);//初始化HeapSort(ST.elem,9);ST_print(ST);return 0;
}
