补寒假作业时突然想到的冒泡排序优化：

用一个变量mark标记未排序部分与已排序部分的界限（就是最后一次交换的位置，剩下的未交换部分一定是已排序的），下次循环到这个界限停止即可，直到界限更新到边界。

小优化，估计能想到的人也不少。还是 O(n^2-n) 的冒泡，最优情况降到 O(n)，最差情况依旧，平均起来还是会比原来的快一些。

以下是Pascal代码，供参考（C/C++有qsort()，用Python写冒泡实在不舒服，还是用Pascal得了）：


program bubbleplus (input, output);
//略优化的冒泡排序 by cuihao

const
    MAXN = 65535;

var
    n, mark, newmark, temp, i, j: word;
    a: array [1 .. MAXN] of word;

begin
    write('数据规模: ');
    readln(n);

    writeln('未排序数组:');
    randomize;
    for i := 1 to n do
    begin   //随机数填充数组
        a[i] := random(MAXN);
        write(a[i]:6);
    end;

    writeln;
    write('开始排序... ');

    // 排序部分begin
    // 从小到大排序，从数组头向尾端冒泡
    mark := n;  //标记未排序部分末端
    repeat
        newmark := 0;
        for j := 1 to mark-1 do
            if a[j] > a[j+1] then
            begin
                temp := a[j];
                a[j] := a[j+1];
                a[j+1] := temp;
                newmark := j;
            end;
        mark := newmark;    //更新标记
    until mark = 0;
    // 排序部分 end

    writeln('排序完毕!');
    writeln('排序后数组:');
    mark := 0;
    for i := 1 to n-1 do
    begin   // 输出并检测算法正确性
        if a[i] > a[i+1] then
            mark := 1;
        write(a[i]:6);
    end;
    writeln(a[n]:6);

    if mark = 1 then
        writeln('算法错误')
    else
        writeln('正常结束.')
end.