php房产网站开发教程,如何做网站打广告,作为一个专业的网页制作人员,成都住建局官网平台文章目录1.插入排序2.冒泡排序3.选择排序4.希尔排序5.归并排序6.快速排序6.1.快速排序#xff08;改进#xff09;7.堆排序8.计数排序9.桶排序9.1.桶排序#xff08;改进#xff09;10.基数排序题目#xff1a;LeetCode 912. 排序数组#xff08;10种排序#xff09; 下…
文章目录1.插入排序2.冒泡排序3.选择排序4.希尔排序5.归并排序6.快速排序6.1.快速排序改进7.堆排序8.计数排序9.桶排序9.1.桶排序改进10.基数排序题目LeetCode 912. 排序数组10种排序 下面博文为早期学习写的很不简洁请参考上面题目的版本。
1.插入排序
/** 1.插入排序* 每次在末尾插入一个数字依次向前比较类似与抓扑克牌(插入排序每次左边的子序列都是有序的)*/
void insertsort(size_t dsize, int *arr) //dsize是数组arr的长度
{if(dsize 1) //预防特殊情况下后面代码失效{return;}for (size_t i 0; i ! dsize; i) {for (size_t j i; j 0 arr[j-1] arr[j]; --j)//每次的子列都是有序的判断条件可写在for(内)否则不可这么做减少运行次数//每次和有序数组最后一个比较向前搜索直到找到位置停止{swap(arr[j-1], arr[j]);}}
}/*时间复杂度分析最好情况原数列有序每次放在最后就好了复杂度为n最坏情况原数列倒序的每次都要挪到最前面12...n-1n(n-1)/2*/2.冒泡排序
/**2.冒泡排序数从前向后冒泡比较冒泡过程中数列无序状态*/
void bsort(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}bool arrisok false;for(size_t i 0; i ! dsize; i){ arrisok true;for(size_t j1;j dsize-1-i;j) //后面的数都排好了所以jdsize-1-i,不减i,也可但时间长{ if(arr[j-1] arr[j]) //比较的过程中是无序的判断条件写在for{}里//写在for()里会出现局部条件不满足就退出for循环了以至于还未排序完{swap(arr[j-1],arr[j]);arrisok false; //如果交换过则数组未完成排序}}if(arrisok true){return; //经过一轮冒泡后,数据没有发生交换则数据为有序可退出函数可减少12%时间用自己的程序}}
}/*时间复杂度分析最好情况原数列有序复杂度为n最坏情况原数列倒序的每次都要从前挪到后面n-1n-2...1n(n-1)/2*/3.选择排序
/**3.选择排序,每次找出数值最小的下标交换未排序区域第一个与最小的(与冒泡的区别只交换一次)*/
void selecsort(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}size_t mindex0;for(size_t i 0; i! dsize-1; i){ mindex i ;for(size_t ji1;j!dsize;j){ if(arr[j] arr[mindex]) //子列为无序的判断条件写在for{}里{ mindex j; //记录下最小数的下标}}swap(arr[i],arr[mindex]);}
}/*时间复杂度分析最好情况与最坏一样最坏情况每次都要从前到后比较n-1n-2...1n(n-1)/2*/4.希尔排序
/** 4.希尔排序分组插入排序相隔gap个数的都为一组从第gap个数开始*/
void shellsort(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}size_t gap 1;size_t j0;for(gapdsize/2;gap 0;gap / 2){ for(size_t i gap;i dsize;i){ for(ji;int(j-gap)0 arr[j-gap] arr[j];j - gap) //int()转换类型避免溢出相当于分组的插入排序{swap(arr[j-gap],arr[j]);}}}
}/*时间复杂度分析
[参考](https://blog.csdn.net/ginnosx/article/details/12263619)最好情况最坏情况*/5.归并排序
/**5.归并排序自顶向下递归*/
void merge(int *arr,size_t left,size_t mid,size_t right)
{int len right - left 1;int *temp new int [len]; //数组较长时请用new不然栈空间容易溢出size_t index 0;size_t i left, j mid 1;while(i mid j right){temp[index] arr[i] arr[j]? arr[i]: arr[j]; //对两边的数组从小到大放入临时空间}while(i mid) //比较完后左半边有没放进去的直接写入{temp[index] arr[i];}while(j right) //比较完后右半边有没有放进去的直接写入{temp[index] arr[j];}for(int k 0;k len;k){arr[left ] temp[k]; //把有序的临时数组写入原来数组的起始位置}delete [] temp; //释放空间temp NULL; //指针置空
}
void divide(int *arr,size_t left,size_t right)
{if(left right){ return;}size_t mid (leftright)/2; //找出区间中部的数将数组分段divide(arr,left,mid); //递归调用对左边继续分段divide(arr,mid1,right); //递归调用对右边继续分段merge(arr,left,mid,right); //对左右两半进行排序合并成一小段有序的数组
}
void mergesort(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}size_t left 0, right dsize-1;divide(arr,left,right);
}6.快速排序
/*1. 6.快速排序2. 对数组找出一个中间大小的合适哨兵把小于哨兵的放左边大于哨兵的放右边中间是等于哨兵的3. 分别对左右递归调用快排*/
size_t parr [2]; //全局变量全局变量不好长期占用内存每个函数都可访问容易被修改函数间相互干扰
void selectmedianofthree(int *arr, size_t left, size_t right) //找出中间大小的数做哨兵
{size_t mid left (right - left)/2; //中部数据的下标if(arr[mid]arr[right]) {swap(arr[mid],arr[right]);}if(arr[left]arr[right]){swap(arr[left],arr[right]);}if(arr[mid]arr[left]){swap(arr[mid],arr[left]); //把中间大小的数值放到首位}
}
void partion(int *arr, size_t left, size_t right) //数据分段
{selectmedianofthree(arr,left,right); //找出中间大小的哨兵让分段尽量均匀提高效率size_t lessPnum 0, largePnum0;int pval arr[left]; //中间大小的数赋值给哨兵int *temp new int [right-left1]; //开辟堆空间存放临时数组int tempLindex0, tempRindex right-left; //临时数组的首末位下标for(int i left1; i right; i){if(pval arr[i]) //比哨兵小的放在左边从左边首位往中间写入记录下比哨兵小的有多少个{temp[tempLindex] arr[i];lessPnum;}if(pval arr[i]) 比哨兵大的放在右边从右边末位中间写入记录下比哨兵大的有多少个{temp[tempRindex--] arr[i];largePnum;}}for( ; tempLindex tempRindex; tempLindex)//中间还未被写入的位置写入哨兵哨兵可能是多个相同的值{temp[tempLindex] pval;}for(int i left, j0; i right; i){arr[i] temp[j]; //把分好段的数组写回原数组{[小于哨兵的],[等于哨兵的],[大于哨兵的]}}delete [] temp; //释放临时数组temp NULL; //指针置空parr[0]lessPnum;parr[1]largePnum; //可以采用被调用函数的参数引用回传给主函数
}
void qsort(int *arr, size_t left, size_t right, int deep)
{if(left right){return;}else if(right-left 1) //只有两个数直接比较交换也可以设置长度小于X比如10调用其他排序如归并减少不必要的调用快排{if(arr[left]arr[right]){ swap(arr[left], arr[right]);}}else{partion(arr,left,right); //数据分段{[小于哨兵的],[等于哨兵的],[大于哨兵的]}size_t pl_index left parr[0]; //首位哨兵的下标size_t pr_index right - parr[1]; //末位哨兵的下标if(pr_index right pl_index ! left) //哨兵群位于数组最右边且左边还有数据{qsort(arr,left,pl_index-1,deep); //只对左边非哨兵数据快排}else if(pl_index left pr_index ! right) //哨兵群位于数组最左边且右边还有数据{ qsort(arr,pr_index1,right,deep); //只对右边非哨兵数据快排}else if(pl_index left pr_index right) //全部是哨兵两侧无数据退出{return;}else //两侧都有非哨兵数据对两侧调用快排{qsort(arr,left,pl_index-1,deep);qsort(arr,pr_index1,right,deep);}}
}
void quicksort(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}size_t left 0, right dsize-1;int deep 0; //可以打印显示出调用的层数qsort(arr,left,right,deep);
}6.1.快速排序改进
/** 6-1.快速排序(改进不使用全局变量传递参数)* 对数组找出一个中间大小的合适哨兵把小于哨兵的放左边大于哨兵的放右边中间是等于哨兵的* 分别对左右递归调用快排*/
void selectmedianofthree(int *arr, size_t left, size_t right) //找出中间大小的数做哨兵
{size_t mid left (right - left)/2; //中部数据的下标if(arr[mid]arr[right]) {swap(arr[mid],arr[right]);}if(arr[left]arr[right]){swap(arr[left],arr[right]);}if(arr[mid]arr[left]){swap(arr[mid],arr[left]); //把中间大小的数值放到首位}
}
void partion(int *arr, size_t left, size_t right, size_t lessPnum, size_t largePnum)//数据分段
{selectmedianofthree(arr,left,right); //找出中间大小的哨兵让分段尽量均匀提高效率int pval arr[left]; //中间大小的数赋值给哨兵int *temp new int [right-left1]; //开辟堆空间存放临时数组int tempLindex0, tempRindex right-left; //临时数组的首末位下标for(int i left1; i right; i){if(pval arr[i]) //比哨兵小的放在左边从左边首位往中间写入记录下比哨兵小的有多少个{temp[tempLindex] arr[i];lessPnum;}if(pval arr[i]) 比哨兵大的放在右边从右边末位中间写入记录下比哨兵大的有多少个{temp[tempRindex--] arr[i];largePnum;}}for( ; tempLindex tempRindex; tempLindex)//中间还未被写入的位置写入哨兵哨兵可能是多个相同的值{temp[tempLindex] pval;}for(int i left, j0; i right; i){arr[i] temp[j]; //把分好段的数组写回原数组{[小于哨兵的],[等于哨兵的],[大于哨兵的]}}delete [] temp; //释放临时数组temp NULL; //指针置空
}
void qsort(int *arr, size_t left, size_t right, int deep)
{if(left right){return;}else if(right-left 1)//只有两个数直接比较交换也可以设置长度小于X比如10调用其他排序如归并减少不必要的调用快排{if(arr[left]arr[right]){swap(arr[left], arr[right]);}}else if(right-left 1 right-left 20) //数组长度较小时调用希尔排序减少调用快排{size_t len right - left 1;shellsort(len, arr[left]); //数组首地址为arr[left]}else{size_t lessPnum 0, largePnum0;partion(arr,left,right,lessPnum,largePnum); //数据分段{[小于哨兵],[等于哨兵],[大于哨兵]}size_t pl_index left lessPnum; //首位哨兵的下标size_t pr_index right - largePnum; //末位哨兵的下标if(pr_index right pl_index ! left) //哨兵群位于数组最右边且左边还有数据{qsort(arr,left,pl_index-1,deep); //只对左边非哨兵数据快排}else if(pl_index left pr_index ! right) //哨兵群位于数组最左边且右边还有数据{ qsort(arr,pr_index1,right,deep); //只对右边非哨兵数据快排}else if(pl_index left pr_index right) //全部是哨兵两侧无数据退出{return;}else //两侧都有非哨兵数据对两侧调用快排{qsort(arr,left,pl_index-1,deep);qsort(arr,pr_index1,right,deep);}}
}
void quicksort(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}size_t left 0, right dsize-1;int deep 0; //可以打印显示出调用的层数qsort(arr,left,right,deep);
}7.堆排序
/** 7.堆排序建堆升序建大堆降序建小堆* 交换堆顶与最后一位无序数据* 调整堆递归交换调整*/
void adjust(int *arr, size_t i, size_t dsize)
{size_t LowerLeftNode i*21; //下一层左边的节点while(LowerLeftNode dsize){if(LowerLeftNode1 dsize arr[LowerLeftNode] arr[LowerLeftNode1] ){LowerLeftNode;}if(arr[i] arr[LowerLeftNode]) //如果上层节点大于小面两个子节点结束{break;}swap(arr[i], arr[LowerLeftNode]);i LowerLeftNode; //往下循环调整LowerLeftNode i*21;}
}
void makeheap(size_t dsize, int *arr)
{for(size_t i dsize/2 -1; i 0;--i) //从后往前底下第二层第一个有子节点的元素的下标{adjust(arr,i,dsize); //有子节点调整堆从i节点往下末位固定dsize-1if(i 0)break;}
}
void heapsort(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}makeheap(dsize,arr); //建立堆大堆上面父节点比子节点大size_t i 0;for(idsize-1;i0;--i) //从最后一位开始与堆顶交换调整堆尾部数据减1{swap(arr[i],arr[0]); //把最大的arr[0]与队尾交换adjust(arr,0,i); //从第0位往下开始调整末位不固定数组长度i每次减一if(i 0) //i 0退出防止--isize_t溢出break;}
}8.计数排序
/**8.计数排序找出数列中最大最小的数并记录下每一个元素的个数然后放回*/
void countsort(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}int index 0;int min, max;min max arr[0];for(int i 1; idsize;i){min(arr[i] min)? arr[i] : min;max(arr[i] max)? arr[i] : max;}//创建新的数组存放int k max -min 1;int *temp new int [k](); //初始化为0for(int i 0;i dsize;i){temp[arr[i]-min]; //记录每个数的个数存入数组}for(int i min; i max;i){for(int j 0; j temp[i-min];j) //存放元素个数不为0的才进入循环{arr[index] i; //把元素值写回数组}}delete [] temp;temp NULL;
}9.桶排序
/**9.桶排序将数据按规则分组对各小组再分别排序*/
void bucketsort(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}int maxval arr[0];int minval arr[0];for(int i 0; i ! dsize; i) //遍历数组找出最大最小元素{maxval maxval arr[i] ? maxval : arr[i];minval minval arr[i] ? minval : arr[i];}if(maxval minval) //如果最大最小数组不需要排序排除下面div0进不了位div总是为0{return;}else{int space 10000; //每个桶数元素值的最大差值区间大小int div ceil((double)(maxval-minval)/space); //桶的个数ceil取进位数(先double强转float的精度不够高避免丢失小数点)//space 太小桶个数太多会造成栈空间溢出int numsofeachbucket[div]; //开辟数组存放每个桶内的元素个数//知识点//1.桶的个数跟数据相关space是固定的但是桶的个数会根据环境变化不能确保程序在其他环境下正确运行//2.div很大时int numsofeachbucket[div]直接撑爆栈空间需要采用new 开辟堆空间//3.当(maxval-minval)是space的整数倍的时候段错误访问越界//第3个问题改成int div floor((double)(maxval-minval)/space)1;即可for(size_t i 0; i ! div; i){numsofeachbucket[i] 0; //每个桶的元素个数初始化为0}for(size_t i 0; i ! dsize; i){numsofeachbucket[(arr[i]-minval)/space]; //把元素按大小分到不同的桶并增加该桶元素个数}int **p new int* [div]; //开辟堆空间指针数组每个元素指针指向每个桶的0位int **temp new int* [div]; //临时数组保存某些指针的初始值方便deletedelete时指针必须位于初始位置int **temp_1 new int* [div]; //同上改进启发数组长度是一定的申请一次内存知道每个桶始末位置即可for(size_t i 0; i ! div; i){if(numsofeachbucket[i] ! 0) //桶内有元素没有元素就不要申请空间了如申请了指针的地址是不为NULL的会出问题{p[i] new int [numsofeachbucket[i]]; //指针数组每个元素指针指向每个桶的0位temp[i] p[i]; //记录每个桶申请的空间的初始地址后面delete temp_1[i]即可删除开辟的p[i] new出的空间temp_1[i] p[i]; //记录初始地址后面p[i],temp[i]指针也要挪动}else{p[i] NULL; //没有元素的桶不申请空间指针初始化为NULLtemp[i] NULL;temp_1[i] NULL;}}for(size_t i 0; i ! dsize; i){size_t bucketidx (arr[i]-minval)/space; //遍历数组每个元素的桶号*p[bucketidx] arr[i]; //把每个元素写入对应的桶中p[bucketidx]; //该桶指针后移一位}size_t idx 0; //之前用了static下次调用的时候idx不会被赋值 0 操作//cout static idx idx endl;for(size_t i 0; i ! div; i){if(numsofeachbucket[i] ! 0) //桶非空{if(numsofeachbucket[i]1) //桶元素个数2个或更多{quicksort(numsofeachbucket[i], temp[i]); //对动态数组进行快速排序p[i]挪动过了temp[i]指向数组首位}for(size_t j 0; j ! numsofeachbucket[i]; j){arr[idx] *temp[i]; //对排序后的数组1个元素不需排序写入原数组temp[i];//cout static idx idx endl;}}}for(size_t i 0; i ! div; i){if(numsofeachbucket[i] ! 0) //对申请出来的空间释放掉{delete [] temp_1[i]; //上面每个桶的数组初始位置指针p[i],temp[i]都动过了所以用此副本初始地址temp_1[i] NULL; //被释放的空间的相关的指针置为空temp[i] NULL;p[i] NULL;}}delete [] temp_1; //delete 与 new 配对出现释放数组指针置NULLdelete [] temp; //内存检测工具valgrind http://valgrind.org/delete [] p;temp_1 NULL;temp NULL;p NULL;}
}9.1.桶排序改进
/**9-1.桶排序将数据按规则分组对各小组再分别排序*改进*1.数组长度一定的只申请一次内存避免内存碎片化提高效率*2.给定桶的个数程序运行状况在不同环境下可控*/
void bucketsort1(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}int maxval arr[0];int minval arr[0];for(int i 0; i ! dsize; i) //遍历数组找出最大最小元素{maxval maxval arr[i] ? maxval : arr[i];minval minval arr[i] ? minval : arr[i];}if(maxval minval) //如果最大最小数组不需要排序{return;}else{int div 1000; //桶的个数int space (maxval-minval)/div1; //每个桶的数值跨度1放大一点包住int *numsofeachbucket new int [div](); //开辟数组存放每个桶内的元素个数初始化为0int *endpositionofeachbucket new int [div](); for(size_t i 0; i ! dsize; i){numsofeachbucket[(arr[i]-minval)/space]; //把元素按大小分到不同的桶并增加该桶元素个数endpositionofeachbucket[(arr[i]-minval)/space];}for(int i 1; i ! div; i){endpositionofeachbucket[i] endpositionofeachbucket[i-1]; //每个桶区间的最大下标1的值}int *temparr new int [dsize]; //开辟堆空间存放临时数组for(size_t i 0; i ! dsize; i){temparr[--endpositionofeachbucket[(arr[i]-minval)/space]] arr[i]; //遍历数组把每个元素写入对应的桶中从每个桶的后部往前写//--运行完成后endpositionofeachbucket[i]就是该桶的首位}for(size_t i 0; i ! div; i){if(numsofeachbucket[i] 1) //桶元素2个或以上才排序{quicksort(numsofeachbucket[i], temparr[endpositionofeachbucket[i]]); //对每个桶的数组进行快速排序元素个数每个桶数组首位的地址} }for(size_t i 0; i ! dsize; i){arr[i] temparr[i]; //对排序后的数组写入原数组}delete [] numsofeachbucket; //delete 与 new 配对出现释放数组指针置NULLdelete [] endpositionofeachbucket; //内存检测工具valgrind http://valgrind.org/delete [] temparr;numsofeachbucket NULL;endpositionofeachbucket NULL;temparr NULL;}
}比较优化前后的桶排序计算效率同样的环境下 优化前 运行时间149s 优化后 运行时间96s 提升35%堆的申请和释放次数也降低了
10.基数排序
/**10.基数排序*/
void radix_countsort(size_t dsize, int *arr, int exp)
{int numofeachbucket[10] {0}; //十个数位每个桶上有0个元素for(int i 0; i ! dsize; i){numofeachbucket[(arr[i]/exp)%10]; //记录该数位上相同的元素个数}for(int i 1; i 10; i){numofeachbucket[i] numofeachbucket[i-1]; //每个位数区间的最大下标1的值现在存储的是下标区间的上限1}int *output new int [dsize];for(int i dsize-1; i 0; --i){output[--numofeachbucket[(arr[i]/exp)%10]] arr[i]; //把数组放在不同的区间位置上}for(int i 0; i ! dsize; i){arr[i] output[i]; //一个数位排好后写回原数组}delete [] output;output NULL;
}
void radixsort(size_t dsize, int *arr)
{if(dsize 1){return;}int maxval arr[0];for(size_t i 0; i ! dsize; i){maxval arr[i] maxval ? arr[i] : maxval; //找出最大的数}for(int exp 1; maxval/exp 0; exp * 10) //从最低位开始对每个数位进行排序{radix_countsort(dsize, arr, exp);}
}
