算法通关村-番外篇排序算法

大家好我是苏麟 , 今天带来番外篇 . 

冒泡排序 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).

稳定性：选择排序是不稳定算法

这期就到这里 , 下期见!