算法-排序-10

力扣-真题-排序数组

没啥好说的，排序可以说是最基础的算法题了， 考基本功， 经常面试的笔试题都会让手写 排序。
咱们就从最基础的冒泡排序开始讲。
冒泡排序的 排序逻辑 是 每一次遍历 都把 数组中最大的元素 放在最后。
假如 数组长度是n
那么第一次遍历， 就把数组区间为0~ n-1 的最大数字 放在 n-1 位 （索引从0开始）
第二次 ，就把数组区间为0~ n-2 的最大数字 放在 n -2 位
一直到倒数第二次遍历， 把数组区间在0~ 1 的 最大的数字放在第二位，
此时就已经排好序了。
至于 针对 每一个区间 怎么把 最大的数字 放在最后，比如针对数组区间是0 ~ n -1 , 冒泡排序的方法是， 从0开始遍历到 n-2 , 每一次遍历 ，都让 nums[i] 跟 nums[i+1]对比， 让 大的那个数 占据 nums[i+1],到最后 n-2次遍历， 自然 nums[n-2]就是最大了。

publicint[]sortArray(int[]nums){intn=nums.length-1;// -1是因为其实遍历n-1次就够了for(inti=0;i<n;i++){for(intj=0;j<n-i;j++){if(nums[j]>nums[j+1]){swap(j,j+1,nums);}}}returnnums;}publicvoidswap(intx,inty,int[]nums){inttem=nums[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(left>=right)return;// 选择最右边的元素作为基准值intpivot=nums[right];intleftIndex=left;intrightIndex=right-1;while(leftIndex<=rightIndex){// 从左往右找第一个大于等于基准数的数字while(leftIndex<=rightIndex&&nums[leftIndex]<pivot){leftIndex++;}// 从右往左找第一个小于基准数的数字while(leftIndex<=rightIndex&&nums[rightIndex]>pivot){rightIndex--;}// 只有当左指针仍在右指针左侧时才交换if(leftIndex<rightIndex){swap(leftIndex,rightIndex,nums);leftIndex++;rightIndex--;}else{// 退出循环条件break;}}// 将基准值放到正确位置swap(leftIndex,right,nums);// 递归排序左右子数组sort(left,leftIndex-1,nums);sort(leftIndex+1,right,nums);}publicvoidswap(intx,inty,int[]nums){inttemp=nums[x];nums[x]=nums[y];nums[y]=temp;}