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

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

冒泡排序 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;
    }
}

空间复杂度 仅仅使用一个辅助单元 ，因此空间复杂度为O(1)。

时间复杂度 假设待排序的元素个数为n，则总共需要进行n-1趟排序，对 j 个元素的子序列进行一趟排序需要进行j-1次关键字比较，因此总的比较次数为n(n-1)/2，因此时间复杂度为O(n^2)。

稳定性 冒泡排序的特点是稳定性好，因为排序过程中始终只交换相邻元素，比较对象大小相等时不交换，相对位置不变，故稳定。

这期就到这里 , 下期见!