Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

排序算法之冒泡排序 #23

Open
xuexueq opened this issue Oct 19, 2018 · 0 comments
Open

排序算法之冒泡排序 #23

xuexueq opened this issue Oct 19, 2018 · 0 comments
Labels
数据结构与算法 数据结构与算法

Comments

@xuexueq
Copy link
Owner

xuexueq commented Oct 19, 2018

冒泡排序(稳定)

思路:它重复地走访过要排序的数列(直到没有再需要交换),一次比较两个元素,如果它们的顺序错误就把它们交换过来。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

  • 算法分析

最佳情况:T(n) = O(n); 当输入的数据已经是正序时(都已经是正序了,为毛何必还排序呢....)
最差情况:T(n) = O(n2); 当输入的数据是反序时(卧槽,我直接反序不就完了....)
平均情况:T(n) = O(n2)

function bubbleSort(arr) {
    for(let i = 0, len = arr.length - 1; i < len; i++) {
        for(let j = 0; j < len - i; j++) {
            if(arr[j] > arr[j + 1]) {
                let temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    return arr;
}

对冒泡排序进行改进:每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

function bubbleSort(arr) {
    let len = arr.length;
    let low = 0;
    let high = len - 1;
    while(low < high) {
        for(let i = low; i < high; i++) { // 正向冒泡 找出最大值
            if(arr[i] > arr[i + 1]) {
                let temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }
        --high;
        for(let j = high; j > low; j--) { // 反向冒泡 找出最小值
            if(arr[j] < arr[j - 1]) {
                let temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
        }
        ++low;
    }
    return arr;
}
@xuexueq xuexueq added the 数据结构与算法 数据结构与算法 label Oct 19, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
数据结构与算法 数据结构与算法
Projects
None yet
Development

No branches or pull requests

1 participant