大家好我是苏麟 , 今天带来番外篇 .
冒泡排序 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).
稳定性:选择排序是不稳定算法
这期就到这里 , 下期见!