选择，插入，冒泡，希尔等排序算法的比较

一。选择排序：
  1.原理：
     首先，找数组中最小的元素，把它与第一个位置的元素进行交换。然后，找到第二个最小的元素，并用数组中的第二个位置的元素进行交换。这样进行下去，直到整个数组排序完毕。

  2.java代码示例：

package com.qingbyqing.algorithm;
public class Selectionsort1 {
    static int[] a = { 2, 3, 1, 43, 23, 32, 5, 7, 4, 0, 31, 4, 7};
    public static void main(String[] args) {
        for (int i = 0; i < a.length - 1; i++) {
            int minIndex = i;// 最小元素
            for (int j = i + 1; j < a.length; j++) {
                if (a[minIndex] > a[j]) {// 比较
                    minIndex = j;
                    continue;
                }
            }
            // 交换
            int temp = a[i];
            a[i] = a[minIndex];
            a[minIndex] = temp;
        }
        // 测试输出结果
        for (int k = 0; k < a.length; k++) {
            System.out.print(a[k] + " ");
        }
    }
}

  3.简单说明：
     对于从1到N-1次的每一个i,有一次交换和N-1次的比较，所以一共有N-1次交换和（N-1)+(N-2)+......+2+1=N(N-1)/2次比较，无论输入数据是怎样的。
    选择排序唯一依赖输入部分的事min的更新次数，所以一般选择排序运行效率跟输入的数据关系不大。

二。插入排序：
   1.原理：
         在数组中将较大的元素向右移动一个位置，为要插入的元素腾出空间，然后较小的元素插入到这个空位置上。
2.java代码示例：

package com.qingbyqing.algorithm;

public class Insert {
    static int[] a = { 9, 4, 5, 7, 23, 3, 1, 4, 0, 6 };

    public static void main(String[] args) {

        for (int i = 1; i < a.length; i++) {

            for (int j = i; j > 0; j--) {

                if (a[j] < a[j - 1]) {// 比较
                    // 交换
                    int temp = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = temp;
                }
            }
        }
        // 测试输出结果
        for (int k = 0; k < a.length; k++) {
            System.out.print(a[k] + "　");
        }
    }
}

3.简单说明：
   插入排序的比较交换要根据 输入的数据而定：最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较交换操作需(n-1)次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。所以，如果需要排序的数据量比较小，有一定的顺序用插入排序还是一个不错的选择。

三。冒泡排序：

      1.原理：
         不断的遍历元素，交换倒序的相邻元素，直到排序完成
  
2.java代码示例：
  

package com.qingbyqing.algorithm;

public class Bubble {
    static int a[] = { 9, 4, 5, 7, 23, 3, 1, 4, 0, 6 };

    public static void main(String[] args) {

        for (int i = 0; i < a.length; i++) {
            for (int j = i + 1; j < a.length; j++) {
                if (a[i] > a[j]) {// 比较
                    // 交换
                    int temp = a[i];
                    a[i] = a[j];
                    a[j] = temp;
                }
            }
        }
        // 测试输出结果
        for (int k = 0; k < a.length; k++) {
            System.out.print(a[k] + " ");
        }
    }
}

3.简单说明：
    冒泡排序要要比选择排序，插入排序慢，它一般来说要进行N^2/2次 比较和交换，而选择排序一般进行N^2/2次比较，交换需要N次；插入排序最坏的情况下才需要N^2/2比较和交换，一般情况下只需N^2/4次比较和交换即可。但是冒泡排序的最大优点是:实现简单。

四。希尔排序：

      1.原理：
     插入排序很慢，是因为它只能交换相邻的元素，因此数组中的元素只能移动一个位置，希尔排序是插入排序的一个简单的扩展，它允许相隔很远的元素进行交换从而提高了速度。
      先取一个小于数组长度的整数h1作为第一个增量，把一个数组的全部元素分成h1个组。所有距离为h1的倍数的记录放在同一个组中。先在各组内进行直接插人排序；然后，取第二个增量h2<h1重复上述的分组和排序，直至所取的增量ht=1(ht<ht-l<…<h2<h1)，即所有记录放在同一组中进行直接插入排序为止。

2.java代码示例：

package com.qingbyqing.algorithm;

public class ShellSort {
    static int[] a = { 2, 3, 1, 43, 23, 32, 5, 7, 4, 0, 31, 4, 7 };
    public static void main(String[] args) {
        // 分组
        for (int h = a.length / 2; h > 0; h /= 2) {
            // 组内使用直接插入排序法排序(增量由1变成h)
            for (int i = h; i < a.length; i++) {
                int temp = a[i];
                int j = 0;
                for (j = i; j >= h; j -= h) {
                    if (temp < a[j - h]) {// 比较
                        a[j] = a[j - h];
                    } else {
                        break;
                    }
                }
                // 交换
                a[j] = temp;
            }
        }
        // 测试输出结果
        for (int k = 0; k < a.length; k++) {
            System.out.print(a[k] + " ");
        }
    }
}

3.简单说明：
      在希尔排序开始时增量较大，分组较多，每组的记录数目少，故各组内直接插入较快，后来增量hi逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按hi-1作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。