冒泡排序

冒泡排序

冒泡排序每次检查相邻两个元素，以升序为例， 如果前面的元素大于后面的元素，就将相邻两个元素交换。当没有相邻的元素需要交换时，排序就完成了。

时间复杂度：$O(n^2)$

冒泡排序是稳定排序

伪代码

$ \begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \newline 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order stably.} \newline 3 & \textbf{Method. } \newline 4 & flag\gets True \newline 5 & \textbf{while }flag\newline 6 & \qquad flag\gets False\newline 7 & \qquad\textbf{for }i\gets1\textbf{ to }n-1\newline 8 & \qquad\qquad\textbf{if }A[i] >A[i + 1]\newline 9 & \qquad\qquad\qquad flag\gets True\newline 10 & \qquad\qquad\qquad \text{Swap } A[i]\text{ and }A[i + 1] \end{array}$

Java实现

public void bubbleSorted(int[] nums){
    boolean flag = true;
    while(flag){
        flag = false;
        for(int i = 0; i< nums.length-1; i++){
            if(nums[i] > nums[i+1]){
                int temp = nums[i];
                nums[i] = nums[i+1];
                nums[i+1] = temp;
                flag = true;
            }
        }
    }
}