厦门市建设执业资格注册管理中心网站苏州网络推广公司永阳

厦门市建设执业资格注册管理中心网站,苏州网络推广公司永阳,网站建设基本问题,wordpress 二次开发力扣-真题-排序数组没啥好说的#xff0c;排序可以说是最基础的算法题了#xff0c; 考基本功#xff0c; 经常面试的笔试题都会让手写 排序。 咱们就从最基础的冒泡排序开始讲。 冒泡排序的 排序逻辑 是 每一次遍历 都把 数组中最大的元素 放在最后。 假如 数组长度是n 那…力扣-真题-排序数组没啥好说的排序可以说是最基础的算法题了 考基本功 经常面试的笔试题都会让手写 排序。咱们就从最基础的冒泡排序开始讲。冒泡排序的 排序逻辑 是 每一次遍历 都把 数组中最大的元素 放在最后。假如 数组长度是n那么第一次遍历 就把数组区间为0~ n-1 的最大数字 放在 n-1 位 索引从0开始第二次 就把数组区间为0~ n-2 的最大数字 放在 n -2 位一直到倒数第二次遍历 把数组区间在0~ 1 的 最大的数字放在第二位此时就已经排好序了。至于 针对 每一个区间 怎么把 最大的数字 放在最后比如针对数组区间是0 ~ n -1 , 冒泡排序的方法是 从0开始遍历到 n-2 , 每一次遍历 都让 nums[i] 跟 nums[i1]对比 让 大的那个数 占据 nums[i1],到最后 n-2次遍历 自然 nums[n-2]就是最大了。publicint[]sortArray(int[]nums){intnnums.length-1;// -1是因为其实遍历n-1次就够了for(inti0;in;i){for(intj0;jn-i;j){if(nums[j]nums[j1]){swap(j,j1,nums);}}}returnnums;}publicvoidswap(intx,inty,int[]nums){inttemnums[x];nums[x]nums[y];nums[y]tem;}接着就是快速排序。冒泡排序的 无序区间 是 一点点 减少的。 在数据量有点大的时候 比如说 100 个数 可能需要 比较 接近百万次。快速排序则采用了 分而治之 的思想 取 区间 中的第一个数作为基准将 区间 划分成两个 更小的区间 所以 遍历一次 就能将 100个数字的排序问题 可能降级两个为 50个 数字 的区间 排序 然后 再遍历两次 对两个50区间遍历 可能就降级为 4 个 25个数字的 区间排序随着遍历的继续 区间数量可能变多 但是 区间的长度在 断崖式的下降 8 -》 4 -》 2 -》 1 你只要想想 100个数字 一直用冒泡排序 可能需要比较 10000次 毕竟时间复杂度是O(n^2), 但是在遍历了4次 后最多比较 400次 加上 剩下4个 25个数的区间 都用冒泡排序 一个25区间是 25的平方 225 次 4次加一起也就 900次比较 加上400也就1300次对比 10000 少了将近 9000次比较。 就可以初见端倪。 更不用说一直用 快速排序 的 分而治之 方法排序。publicint[]sortArray(int[]nums){sort(0,nums.length-1,nums);returnnums;}publicvoidsort(intleft,intright,int[]nums){if(leftright)return;// 选择最右边的元素作为基准值intpivotnums[right];intleftIndexleft;intrightIndexright-1;while(leftIndexrightIndex){// 从左往右找第一个大于等于基准数的数字while(leftIndexrightIndexnums[leftIndex]pivot){leftIndex;}// 从右往左找第一个小于基准数的数字while(leftIndexrightIndexnums[rightIndex]pivot){rightIndex--;}// 只有当左指针仍在右指针左侧时才交换if(leftIndexrightIndex){swap(leftIndex,rightIndex,nums);leftIndex;rightIndex--;}else{// 退出循环条件break;}}// 将基准值放到正确位置swap(leftIndex,right,nums);// 递归排序左右子数组sort(left,leftIndex-1,nums);sort(leftIndex1,right,nums);}publicvoidswap(intx,inty,int[]nums){inttempnums[x];nums[x]nums[y];nums[y]temp;}