南皮网站建设公司,传奇霸业官网下载,技校平面设计主要做什么,重庆网红打卡地简介#xff1a;主要根据两个数据进行比较从而交换彼此位置#xff0c;以此类推#xff0c;交换完全部。主要有冒泡和快速排序两种。
目录
一、冒泡排序
1.1简介#xff1a;
1.2代码#xff1a;
二、快速排序
1.1简介#xff1a;
1.2代码#xff1a; 一、冒泡排序… 简介主要根据两个数据进行比较从而交换彼此位置以此类推交换完全部。主要有冒泡和快速排序两种。
目录
一、冒泡排序
1.1简介
1.2代码
二、快速排序
1.1简介
1.2代码 一、冒泡排序
1.1简介 冒泡即每次给表中一个数据弄到最前面或者最后面以此类推。其主要思想为外循环是趟数内循环是比较次数两两比较一点点往后冒。从第1趟比较开始比较比较n-1次第2趟比较比较n-2次以此类推所以比较次数为
每个框框表示一趟的比较从头两两比较。后面我设置了flag验证是否还需要再跑趟次了避免做无用功如果有序了则不需要比较 空间复杂度O(1) 时间复杂度O() 稳定性两两交换很稳定。
1.2代码
#include stdio.h
void BubbleSort(int *a,int n)
{int i,j,flag;for(i0;in-1;i)//比较趟数每趟都从头到尾n-1-i进行比较遍历给一个数冒到后面冒完的下一轮就不参与比较了 {flag1;//避免做无用功有序的话就不用再接着比较了 for(j0;jn-1-i;j){int temp0;if(a[j]a[j1])//要求递增 {tempa[j1];a[j1]a[j];a[j]temp;flag0;}}if(flag1)//如果没有交换则不要调整了直接退出循环即可。 break;}}
void PrintSort(int *a,int n)
{int i;for(i0;in;i){printf(%d ,a[i]);}printf(\n);
}
int main()
{int a[6]{5,6,8,9,1,2};BubbleSort(a,6);PrintSort(a,6);return 0;}
二、快速排序
1.1简介 快速排序类似于前序遍历二叉树每次选第一个元素作为基准元素每进行一次快排找到其基准元素位置后从该位置左右划分成两部分左边比基准小右边比基准大。随后进入左边进行快排左边都结束了再去右边。是个递归操作。 快排的时候选一个基准元素定左右两个low和high标记量low标记的位置都应该比基准小于等于high标记的都应该大于等于。先是标记处非空数据逻辑上给开始基准元素处变为空。存到一个pivot基准变量中的位置进行移动判断往中间移动。如果high处大于等于基准则--hgh如果不满足则给该处值赋值给low处即a[low]a[high]。这样high处变为空了开始从low处判断. 时间复杂度O() 空间复杂度树的深度 稳定性不稳定一次移动好多数据 递归深度树的高度 递归次数树的总结点数 n个数据快速排序至少比较多少次正好平分次数最少。 如15个数据第一次有一个基准元素分成左右两块长度为7的此时比较2*714两个7随后又分成两个长度为3的四个3最后分成左右长度为1的。因此为2*72*2*34*21412834 1.2代码
#include stdio.h
void PrintSort(int *a,int n)
{int i;for(i0;in;i){printf(%d ,a[i]);}printf(\n);
}
//快速排序
//一次快排
int Partition(int *a,int low,int high)
{int pivot a[low];//定义基准元素变量 while(lowhigh)//进入比较 {while(lowhigha[high]pivot) --high; //最开始标记处为非空开始移动因此先判断右边high情况应该high标记处比基准大于等于满足往中间移动--。 a[low]a[high];//不满足high标记处大于等于基准元素则给该high处值赋值给low标记处while(lowhigha[low]pivot) low;a[high]a[low];//不满足low标记处小于等于基准元素则给该low处值赋值给high标记处}a[low]pivot;//当low和high相等时找到基准元素位置给该处赋值 return low; //返回基准元素下标
}
void QuickSort(int *a,int low,int high)
{ //类似于前序遍历一个二叉树。 if(lowhigh)//递归跳出条件 {int pivot Partition(a,low,high);//根 QuickSort(a,low,pivot-1); //左 QuickSort(a,pivot1,high); //右 }}int main()
{int a[6]{5,6,8,9,1,2};//BubbleSort(a,6);QuickSort(a,0,5); PrintSort(a,6);return 0;}
