流 年

排序算法种类繁多。

根据处理的数据规模与存储特点，可分为内部排序和外部排序：前者处理的数据规模不大，内存足以容纳；后者处理的数据规模较大，必须将数据存放于外部存储器中，每次排序的时候需要访问外存。根据输入的不同形式，分为脱机算法和在线算法：前者待排序的数据是以批处理的形式给出的；而在云计算之类的环境中，待排序的数据是实时生成的，在排序算法开始运行时，数据并未完全就绪，而是随着排序算法本身的进行而逐步给出的。另外，针对不同的体系结构，又分为串行和并行两大类排序算法。根据算法是否采用随机策略，还有确定式和随机式之分。

冒泡排序(O(n^2))

冒泡排序是比较相邻两数的大小来完成排序的。这里定义比较边界，也就是进行大小比较的边界。对于长度为n的数组，第一趟的比较边界为[0,n-1]，也就是说从a[0]开始，相邻元素两两比较大小，如果满足条件就进行交换，否则继续比较，一直到最后一个比较的元素为a[n-1]为止，此时第一趟排序完成。以升序排序为例，每趟排序完成之后，比较边界中的最大值就沉入底部，比较边界就向前移动一个位置。所以，第二趟排序开始时，比较边界是[0,n-2]。对于长度为n的序列，最多需要n趟完成排序，所以冒泡排序就由两层循环构成，最外层循环用于控制排序的趟数，最内层循环用于比较相邻数字的大小并在本趟排序完成时更新比较边界。

//冒泡排序
public static void bubbleSort(int[] arr,int len){
    int temp=0;
    int compareRange=len-1;//冒泡排序中，参与比较的数字的边界。
    //冒泡排序主要是比较相邻两个数字的大小，以升序排列为例，如果前侧数字大于后侧数字，就进行交换，一直到比较边界。
    for (int i = 0; i <len ; i++) {//n个数使用冒泡排序，最多需要n趟完成排序。最外层循环用于控制排序趟数
        for (int j = 1; j <=compareRange ; j++) {
            if(arr[j-1]>arr[j]){
                temp=arr[j-1];
                arr[j-1]=arr[j];
                arr[j]=temp;
            }
        }
        compareRange--;//每进行一趟排序，序列中最大数字就沉到底部，比较边界就向前移动一个位置。
    }
    System.out.println("排序后数组"+Arrays.toString(arr));
}

在排序后期可能数组已经有序了而算法却还在一趟趟的比较数组元素大小，可以引入一个标记，如果在一趟排序中，数组元素没有发生过交换说明数组已经有序，跳出循环即可。优化后的代码如下：

……

在单循环积分淘汰赛中，经常会用到贝格尔编排法。

今天在项目的比赛规则中就用到了，我用PHP实现“贝格尔编排法”如下：

    /**
     * 贝格尔编排法（算法）
     * @param int $n
     * @return array
     */
    function berger($n){
            if ($n < 3)
            {
                    return 0;
            }
            $h = (1 == $n % 2) ? 0 : $n;
            $num = $h > 0 ? $n : $n + 1;

            $average = $num/2;
            $rs1 = array();
            for($i = 0; $i < $average; $i++){
                    $top = $i+1;
                    $temp = array();
                    for($j = 0; $j < $num-1; $j++){
                         if($top>$num-1){
                                 $top = 1;
                         }
                         $temp[] = $top;
                         $top++;
                    }
                    $temp[] = $h;
                    $rs1[] = $temp;
            }

            $rs2 = array();
            for($i = $average; $i < $n; $i++){
                    $top = (($top+2)>($num-1)) ? $top = 1 : $top+2;
                    $temp = array();
                    $temp[] = $h;
                    for($j = 0; $j < $num-1; $j++){
                         if($top>$num-1){
                                 $top = 1;
                         }
                         $temp[] = $top;
                         $top++;
                    }
                    $rs2[] = $temp;
            }

            $rs = array();
            foreach ($rs1 as $k => $v)
            {
                    $rs[] = $v;
                    if(isset($rs2[$k])){
                            $rs[] = $rs2[$k];
                    }
            }
            return $rs;
    }