贵州门户网站建设,微博推广的方法,科技公司最全经营范围,网站建设合同属于什么类别大家好我是苏麟 , 今天带来番外篇 .
冒泡排序 BubbleSort
最基本的排序算法#xff0c;最常用的排序算法 .
我们以关键字序列{26,53,48,11,13,48,32,15}看一下排序过程: 动画演示 : 代码如下 : (基础版)
class Solution {public int[] sortArray(int[] nums) {for(int i …大家好我是苏麟 , 今天带来番外篇 .
冒泡排序 BubbleSort
最基本的排序算法最常用的排序算法 .
我们以关键字序列{26,53,48,11,13,48,32,15}看一下排序过程: 动画演示 : 代码如下 : (基础版)
class Solution {public int[] sortArray(int[] nums) {for(int i 0;i nums.length - 1;i){for(int j 0;j nums.length - i - 1;j){if(nums[j] nums[j 1]){int temp nums[j];nums[j] nums[j 1];nums[j 1] temp;}}}return nums;}
} 优化 :
class Solution {public int[] sortArray(int[] nums) {int flag 1;for(int i 0;flag i nums.length - 1;i){flag 0;for(int j 0;j nums.length - i - 1;j){if(nums[j] nums[j 1]){int temp nums[j];nums[j] nums[j 1];nums[j 1] temp;flag 1;}}}return nums;}
}
空间复杂度 仅仅使用一个辅助单元 因此空间复杂度为O(1)。
时间复杂度 假设待排序的元素个数为n则总共需要进行n-1趟排序对 j 个元素的子序列进行一趟排序需要进行j-1次关键字比较因此总的比较次数为n(n-1)/2因此时间复杂度为O(n^2)。
稳定性 冒泡排序的特点是稳定性好因为排序过程中始终只交换相邻元素比较对象大小相等时不交换相对位置不变故稳定。
选择排序 SelectSort
选择排序是默认前面都是已经排序好的然后从后面 选择最小的放在前面排序好的的后面首先第一轮循环的时候默认的排序好的为空然后从后面选择最小的放到数组的第一个位置第二轮循环的时候默认第个元素是已经 排序好的然后从剩下的找出最小的放到数组的第二个位置第三轮循环的时候默认前 两个都是已经排序好的然后再从剩下的选择一个最小的放到数组的第三个位置以此 类推。还是上面的序列我们看一下选择排序是怎么做的: 动画演示 : 代码 : public static void SelectSort(int[] nums){int min;for (int i 0;i nums.length;i){min i;for (int j i 1;j nums.length;j){if (nums[i] nums[j]){min j;}}if (i ! min){int temp nums[i];nums[i] nums[min];nums[min] temp;}}}
空间复杂度仅仅使用一个辅助单元 因此空间复杂度为O(1)
平均时间复杂度 在待排序序列已经有序的情况下简单选择排序不用移动元素。最坏情况下也就是序列正好是逆序的则要进行n(n-1)/2次比较因此最坏时间复杂度为O(n^2).
稳定性选择排序是不稳定算法
这期就到这里 , 下期见!
