BubbleSort最优实现

冒泡排序

//
// Created by krislyy on 2018/11/6.
//

#ifndef ALGORITHM_BUBBLESORT_H
#define ALGORITHM_BUBBLESORT_H

#include "utility.h"

namespace Algorithm {
    /*
     *起泡排序算法的不变性和单调性可分别概括为：经过k趟扫描交换后，最大的前k
     *个元素必然就位；经过k趟扫描交换之后，带求解问题的有效规模将缩减至n-k.
     *时间复杂度为O(n^2)
     */
    template <class T>
    static void BubbleSort_A(T A[], int n) {
        bool sorted = false; //借助bool元素可以及时退出
        while (!sorted) {
            sorted = true;
            for (int i = 1; i < n; ++i) {   //循环一次后使最大的元素冒泡出来
                if (A[i-1] > A[i]) {        //交换条件
                    swap(A[i-1], A[i]);
                    sorted = false;
                }
            }
            n--;
        }
    }
}

#endif //ALGORITHM_BUBBLESORT_H