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

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

  2.java代码示例：
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代码示例：
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代码示例：
  
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代码示例：
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作为距离排过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。

评论

2 楼 wzl454823 2010-12-24  

hpjianhua 写道

测试数据：

int a[] = new int[]{49,38,65,97,76,13,27,49};

用博主的冒泡算法输出以下结果：

第0回排序：[13, 49, 65, 97, 76, 38, 27, 49]
第1回排序：[13, 27, 65, 97, 76, 49, 38, 49]
第2回排序：[13, 27, 38, 97, 76, 65, 49, 49]
第3回排序：[13, 27, 38, 49, 97, 76, 65, 49]
第4回排序：[13, 27, 38, 49, 49, 97, 76, 65]
第5回排序：[13, 27, 38, 49, 49, 65, 97, 76]
第6回排序：[13, 27, 38, 49, 49, 65, 76, 97]
第7回排序：[13, 27, 38, 49, 49, 65, 76, 97]

博主应该好好检查下自己的算法！

给出我自己的算法：

	/**
	 * 交换两个数位置的算法
	 * @param data
	 * @param i
	 * @param j
	 */
	public static void swap(int[] data,int i,int j){
		int temp = 0;
		temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	/**
	 * 冒泡排序算法实现
	 * @param data
	 * @param n
	 */
	public static void bubble(int[] data,int n){
		for(int i = 0;i<n;i++){
			for(int j = 1;j<n;j++){
				if(data[j]<data[j-1]){
					swap(data,j,j-1);
				}
			}
			System.out.println("第"+i+"回排序："+Arrays.toString(data));
		}
	}

输出结果：

第0回排序：[38, 49, 65, 76, 13, 27, 49, 97]
第1回排序：[38, 49, 65, 13, 27, 49, 76, 97]
第2回排序：[38, 49, 13, 27, 49, 65, 76, 97]
第3回排序：[38, 13, 27, 49, 49, 65, 76, 97]
第4回排序：[13, 27, 38, 49, 49, 65, 76, 97]
第5回排序：[13, 27, 38, 49, 49, 65, 76, 97]
第6回排序：[13, 27, 38, 49, 49, 65, 76, 97]
第7回排序：[13, 27, 38, 49, 49, 65, 76, 97]

谢谢，我原来代码是在javaeye找的  还没等看。

1 楼 hpjianhua 2010-12-17  

测试数据：

int a[] = new int[]{49,38,65,97,76,13,27,49};

用博主的冒泡算法输出以下结果：

第0回排序：[13, 49, 65, 97, 76, 38, 27, 49]
第1回排序：[13, 27, 65, 97, 76, 49, 38, 49]
第2回排序：[13, 27, 38, 97, 76, 65, 49, 49]
第3回排序：[13, 27, 38, 49, 97, 76, 65, 49]
第4回排序：[13, 27, 38, 49, 49, 97, 76, 65]
第5回排序：[13, 27, 38, 49, 49, 65, 97, 76]
第6回排序：[13, 27, 38, 49, 49, 65, 76, 97]
第7回排序：[13, 27, 38, 49, 49, 65, 76, 97]

博主应该好好检查下自己的算法！

给出我自己的算法：

	/**
	 * 交换两个数位置的算法
	 * @param data
	 * @param i
	 * @param j
	 */
	public static void swap(int[] data,int i,int j){
		int temp = 0;
		temp = data[i];
		data[i] = data[j];
		data[j] = temp;
	}

	/**
	 * 冒泡排序算法实现
	 * @param data
	 * @param n
	 */
	public static void bubble(int[] data,int n){
		for(int i = 0;i<n;i++){
			for(int j = 1;j<n;j++){
				if(data[j]<data[j-1]){
					swap(data,j,j-1);
				}
			}
			System.out.println("第"+i+"回排序："+Arrays.toString(data));
		}
	}

输出结果：

第0回排序：[38, 49, 65, 76, 13, 27, 49, 97]
第1回排序：[38, 49, 65, 13, 27, 49, 76, 97]
第2回排序：[38, 49, 13, 27, 49, 65, 76, 97]
第3回排序：[38, 13, 27, 49, 49, 65, 76, 97]
第4回排序：[13, 27, 38, 49, 49, 65, 76, 97]
第5回排序：[13, 27, 38, 49, 49, 65, 76, 97]
第6回排序：[13, 27, 38, 49, 49, 65, 76, 97]
第7回排序：[13, 27, 38, 49, 49, 65, 76, 97]