茶叶怎么做网站销售,科技霸主从新能源车开始,邯郸医院网站建设,在线做名片做海报网站1.冒泡排序
思路#xff1a;比较相邻的两个数字#xff0c;如果前一个数字大#xff0c;那么就交换两个数字#xff0c;直到有序。
时间复杂度#xff1a;O(n^2)#xff0c;稳定性#xff1a;这是一种稳定的算法。 代码实现#xff1a;
void bubble_sort(int arr[],…1.冒泡排序
思路比较相邻的两个数字如果前一个数字大那么就交换两个数字直到有序。
时间复杂度O(n^2)稳定性这是一种稳定的算法。 代码实现
void bubble_sort(int arr[],size_t len){size_t i,j;for(i0;ilen;i){ bool hasSwap false; //优化判断数组是否已经有序如果有序可以提前退出循环for(j1;jlen-i;j){ //这里jlen-i是因为最后面的肯定都是最大的不需要多进行比较if(arr[j-1]arr[j]){ //如果前一个比后一个大swap(arr[j-1],arr[j]); //交换两个数据hasSwap true;} }if(!hasSwap){break; }}
}2.插入排序
思路把一个数字插入一个有序的序列中使之仍然保持有序如对于需要我们进行排序的数组我们可以使它的前i个数字有序然后再插入i1个数字插入到合适的位置使之仍然保持有序直到所有的数字有序。
时间复杂度O(n^2)稳定性稳定的算法 代码实现
void insert_sort(int arr[],int len)
{int i,j;for(i1;ilen;i){int key arr[i]; //记录当前需要插入的数据for(j i-1;i0arr[j]key;j--){ //找到插入的位置arr[j1] arr[j]; //把需要插入的元素后面的元素往后移}arr[j1] key; //插入该元素}
}3.折半插入排序
思路本质上是插入排序但是通过半分查找法找到插入的位置让效率稍微快一点。
时间复杂度O(n^2)稳定性稳定的算法。 代码实现
void half_insert_sort(int arr[],int len)
{int i,j;for(i1;ilen;i){int key arr[i];int left 0;int right i-1;while(leftright){ //半分查找找到插入的位置int mid (leftright)/2;if(keyarr[mid]){right mid-1; }else{left mid1; } }for(ji-1;jleft;j--){ //把后面的元素往后移arr[j1]arr[j]; }arr[j1] key; //插入元素}
}4.希尔排序
思路先取一个正整数d1n把所有序号相隔d1的数组元素放一组组内进行直接插入排序然后取d2d1重复上述分组和排序操作直至di1即所有记录放进一个组中排序为止。
时间复杂度O(n^1.3) ,算法效率上大大提高 。稳定性不稳定的算法。代码实现
void shell_sort(int arr[],int len)
{ //本质上也是一种插入排序避免了大量数据的移动在每一组排序过后每个数据已经到了大致的位置。int i,j;int step0;for(step len/2;step1;stepstep/2){ //分组 分为step组,对每组的元素进行插入排序for(istep;ilen;i){int key arr[i];for(ji-step;j0arr[j]key;jj-step){arr[jstep] arr[j]; } arr[jstep] key;}}
}5.选择排序
思路通过循环找到最大值所在的位置然后把最大值和最后一个元素进行交换通过循环直到所有的数据有序。
时间复杂度O(n^2)稳定性不稳定的算法 代码实现
void select_sort(int arr[],size_t len)
{size_t i,j;for(i0;ilen-1;i){int max 0; //最大值下标for(j1;jlen-i;j){if(arr[max]arr[j]){ //找到最大值的下标max j; } }if(max!j-1){ swap(arr[max],arr[j-1]); //把最后一个元素和最大值进行交换}}
}6.鸡尾酒排序
思路选择排序的一种改进一次循环直接找到最大值和最小值的位置把最大值和最后一个元素进行交换最小值和最前一个元素进行交换所以最外层的循环只需要执行len/2次即可
时间复杂度O(n^2)稳定性不稳定的算法 代码实现
void cocktail_sort(int arr[],size_t len)
{size_t i,j;for(i0;ilen/2;i){int max i; //最大值下标int min i; //最小值下标for(ji1;jlen-i;j){if(arr[max]arr[j]){ //找到最大值下标max j; } if(arr[min]arr[j]){ //找到最小值下标min j; }}if(max!j-1){swap(arr[max],arr[j-1]); //交换最大值和未进行排序的最后一个元素}if(min j-1){ //如果最小值在未进行排序的最后一个位置那么经过最大值的交换已经交换到了最大值所在的位置min max; //把最小值的坐标进行改变}if(min!i){swap(arr[i],arr[min]); //交换最小值和未进行排序的最前的元素}}
}7.堆排序
思路把数据进行大堆化然后依次交换堆顶(最大值)和最后一个元素,在使堆顶重新大堆化最后循环过后数组便有序。 最大堆调整Max Heapify将堆的末端子节点作调整使得子节点永远小于父节点 创建最大堆Build Max Heap将堆中的所有数据重新排序 堆排序HeapSort移除位在第一个数据的根节点并做最大堆调整的递归运算
时间复杂度O(nlgn)稳定性不稳定的算法 代码实现
void re_heap(int arr[],size_t index,size_t len)
{size_t child 2*index1; //左节点坐标int key arr[index]; //当前节点值while(childlen){if(child1lenarr[child]arr[child1]){ //如果右节点存在且右节点的值比左节点大那就child记录较大字节点的坐标child; } if(arr[child]key){ //如果子节点的值比根节点的值大arr[index] arr[child]; //改变根节点的值}else{break; }index child;child 2*index1;}arr[index] key; //插入记录好的值
}
void heap_sort(int arr[],size_t len)
{int i;for(ilen/2;i0;i--){re_heap(arr,i,len); //对第i个根节点进行大堆化}for(ilen-1;i0;i--){swap(arr[0],arr[i]); //交换第一个和最后一个元素re_heap(arr,0,i); //对第一个元素进行大堆化}
}8.快速排序
思路通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列。 过程
(1)首先设定一个分界值通过该分界值将数组分成左右两部分
(2)将大于或等于分界值的数据集中到数组右边小于分界值的数据集中到数组的左边。此时左边部分中各元素都小于或等于分界值而右边部分中各元素都大于或等于分界值。
(3)然后左边和右边的数据可以独立排序。对于左侧的数组数据又可以取一个分界值将该部分数据分成左右两部分同样在左边放置较小值右边放置较大值。右侧的数组数据也可以做类似处理。
(4)重复上述过程可以看出这是一个递归定义。通过递归将左侧部分排好序后再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后整个数组的排序也就完成了。
时间复杂度O(nlog2n)稳定性不稳定的算法代码实现
void quick_sort(int arr[],size_t left,size_t right)
{if(leftright){ //如果只有一个元素那就是有序的返回return; }int i left;int j right;int key arr[left]; //基准值while(ij){ //找到基准值的位置使得基准值右边的元素都比基准值大左边的元素都比基准值小while(ijarr[j]key){ //从右边找一个比基准值小的数--j;}arr[i] arr[j];//把这个值放到基准值的位置处while(ijarr[i]key){ //从左边找一个比基准值大的数i; }arr[j] arr[i]; //把这个元素放到j的位置}arr[i] key;if(i-left1) //元素个数至少两个才进行递归调用这样可以少一次递归quick_sort(arr,left,i-1); //对基准值左边的元素进行排序if(right-i1)quick_sort(arr,i1,right); //对基准值右边的元素进行排序
}9.归并排序
思路对于两个有序的子序列可以把它们合并在一起变成一个新的完全有序的序列因此归并排序和快排差不多都是递归的进行。
时间复杂度O(nlog2n)稳定性稳定的算法 代码实现
void merge(int arr[],int left,int right)
{int i,j,k;int mid (leftright)/2;int len mid-left1;int *temp malloc(sizeof(arr[0])*len);for(i0;ilen;i){temp[i] arr[ileft]; //把这个数组的所有元素都复制到临时数组中}i0,jmid1,kleft;while(ilenjright){if(temp[i]arr[j]){ //把临时数组的元素和 [mid1,right]这部分的元素一个一个的进行比较如果谁小那么arr里就存放谁的元素arr[k] temp[i]; }else{arr[k] arr[j]; }}while(ilen){ //如果temp这个数组的元素还没有全部遍历完那就把temp后面的元素都复制到arr里面去//因为arr[mid1,right] 这部分的元素本来就是arr后面部分的有序的元素所以如果arr[mid1,right]这部分没有遍历完也没关系的arr[k] temp[i]; }free(temp);
}
void merge_sort(int arr[],int left,int right)
{if(leftright){ //如果只有一个元素说明这个序列有序那就返回return; } int mid (leftright)/2; //对两个有序的数组进行排序merge_sort(arr,left,mid); //对[left,mid]这个区间的元素进行排序merge_sort(arr,mid1,right); //对[mid1,right]这个区间内的元素进行排序merge(arr,left,right); //这个序列的[left,mid]为有序的序列 [mid1,right]也为有序的序列
}10.计数排序
思路这是一种基于比较的算法我们用一个大数组来存放这些数据这些数据在这个大数组中的表现形式是以这个大数组的下标存在的比如57,60,42这三个数字进行排序那么用一个大数组这个大数组的arr[57] 1,arr[60] 1,arr[42] 1然后遍历这个大数组就行了。
时间复杂度O(nk),其中这个k为数据的范围所以计数排序最适合数据比较集中的数组排序。稳定性稳定的算法代码实现
void count_sort(int arr[],size_t len)
{int max arr[0]; //最大值int min arr[0]; //最小值size_t i;for(i0;ilen;i){if(maxarr[i]){ //找到最大值max arr[i]; }if(min arr[i]){ //找到最小值min arr[i]; }}int cnt max-min1; //范围int *prr malloc(cnt*sizeof(int)); //申请临时空间for(i0;icnt;i){ //这个临时数组全部置0prr[i] 0; }for(i0;ilen;i){ //对需要进行排序的序列进行遍历prr[arr[i]-min]; //让下标为(arr[i]-min)的临时大数组的值1}size_t j0;for(i0;icnt;i){ //遍历这个临时数组while(prr[i]){ //如果这个数组下标为i的值不等于0arr[j] imin; //那就让需要进行排序的数组的值为imin;--prr[i];} }free(prr); //释放掉申请的动态内存
}11.桶排序
思路工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序。桶排序是鸽巢排序的一种归纳结果。 这是一种以消耗大量空间来换取高效率的排序方式
时间复杂度O(NC)其中CN*(logN-logM)M为桶的数量。所以对于桶排序桶的数量越多其排序效率越高。稳定性稳定的算法
代码实现 首先定义桶这个类型
typedef struct Bucket
{int vect[100]; //其实这里使用链表更好但是我比较懒就懒得用链表了int cnt; //当前桶内存放数据的个数
}Bucket;void bucket_sort(int arr[],size_t len)
{int min arr[0];int max arr[0];size_t i;for(i0;ilen;i){if(minarr[i]){ //找到最小值min arr[i]; }if(maxarr[i]){ //找到最大值max arr[i]; }}int size max-min1;Bucket bucket[5] {}; //其实桶可以动态规划但为了方便我这里直接分为5个桶for(i0;ilen;i){ //遍历待排序的数组把每个元素放到相应的桶当中//比如[0,200]之间的元素放到下标为0的桶中[201,400]之间的元素放到下标为1的桶中..//以此类推直到放完所有的数据int index (arr[i]-min)/(size/5); //用来判断当前元素arr[i]需要放到哪个桶当中bucket[index].vect[bucket[index].cnt] arr[i];}size_t j0,k0;for(i0;i5;i){ //对这五个桶进行遍历count_sort(bucket[i].vect,bucket[i].cnt); //首先对这个桶内的元素进行排序//这里可以调用其他排序方法也可以递归调用当前排序方法但是为了节省内存我选择调用其他排序方法for(j0;jbucket[i].cnt;j){arr[k] bucket[i].vect[j]; //对排序好的桶进行遍历并且把里面的元素复制到arr中去 }}
}12.基数排序
基数排序radix sort属于“分配式排序”distribution sort又称“桶子法”bucket sort或bin sort顾名思义它是透过键值的部份资讯将要排序的元素分配至某些“桶”中藉以达到排序的作用基数排序法是属于稳定性的排序其时间复杂度为O (nlog®m)其中r为所采取的基数而m为堆数在某些时候基数排序法的效率高于其它的稳定性排序法。
解法
1.首先根据个位数的数值在走访数值时将它们分配至编号0到9的桶子中
2.接下来将这些桶子中的数值重新串接起来接着再进行一次分配这次是根据十位数来分配
3.接下来将这些桶子中的数值重新串接起来持续进行以上的动作直至最高位数为止。
时间复杂度设待排序列为n个记录d个关键码关键码的取值范围为radix则进行链式基数排序的时间复杂度为O(d(nradix))其中一趟分配时间复杂度为O(n)一趟收集时间复杂度为O(radix)共进行d趟分配和收集。稳定性稳定的算法
代码实现 还是定义桶的类型
typedef struct Bucket{int vect[100]; //同样的可以用链表int cnt;
}Bucket;void base_sort(int arr[],size_t len)
{size_t i;Bucket bucket[10] {}; //十个桶int max arr[0];for(i0;ilen;i){ //寻找最大值就可以判断最大值的位数if(arr[i]max){max arr[i]; } }size_t j,k;int num 1; //用来获得相应位数上的数字的关键参数//比如要获得个位上的参数时num 1;//获得十位上的数字时num 10;//以此类推do{for(i0;ilen;i){ //遍历待排序的数组把每个元素放入相应的桶中//比如251当获得个位上的数字时251放到下标为1的桶当中//当获得十位上的数字时,251放到下标为5的桶当中//当获得百位上的数字时,251放到下标为2的桶当中//当获得千位上的数字时,251放到下标为0的桶当中//以此类推int index arr[i]/num%10; //获得相应位数上的数字bucket[index].vect[bucket[index].cnt] arr[i]; //把这个数字放到相应的桶中}k0;for(i0;i10;i){for(j0;jbucket[i].cnt;j){arr[k] bucket[i].vect[j]; //把这些桶按顺序依次遍历//把桶中的元素重新放回arr当中} bucket[i].cnt 0; //记得让桶中的cnt变为0,方便下一次存放}num*10; //num*10}while(max/10);//循环条件
}以上内容来自用C语言完整实现12种排序方法_c语言快速排序解决排序问题-CSDN博客
