Java 几种经典排序算法

在本文中，我们来学习在程序当中常用的集中算法，以java程序为例，每种算法我们都采用一个实例进行讲解。

1、插入排序
    基本思路：在每次循环中把一个元素插入到已经排序的部分序列里的合适位置，使得到的序列仍然是有序的。
  

   int a[] = {30,20,50,6};
   int tmp;
   int j;
   for (int i = 1; i < a.length; i++) {
       tmp = a[i];
       for (j = i-1; j>=0 && a[j] > tmp; j--) {
	   a[j + 1] = a[j];
	   a[j] = tmp;
       }
   }
   

   描述：
    a、整数数组，在外层循环的时候，我们从下标为1的数字开始循环（由于是把当前下标的数字与前面的做比较，所以前边下标为0的整数我们就可以把它看成是一个有序的数组即可），取当前下标的值，并且存储到临时变量里边；
    b、然后把当前值与前边排序好的数字做循环比对，从大到小比对，如果下标对应值大于临时变量值，那么，我们就把该值的下标增加1（即向后移动一位），并且把临时变量赋值给小下标对应的值，直到小数组循环到下标为0或者临时变量大于等于小循环下标对应的值为止；
    c、此为插入排序，插入排序是相对循环次数最少的算法，比冒泡排序效率要高；

2、冒泡排序
    基本思路：按照从前到后或者从后到前的顺序，两两数据进行比较，如果不符合制定的规则（即从大到小排序或者从小到大排序）怎么两个数字相互交换位置，直到所有数字都按照制定的规则排序为止；
   

    int a[] = {30,20,50,6};
    int tmp;
    int j;
    for (int i = 0; i < a.length; i++) {
        tmp = a[i];
        for (j = i+1; j < a.length; j++) {
            if(a[i] > a[j]){
                a[i] = a[j];
                a[j] = tmp;
                tmp = a[i];
            }
        }
    }
    

    a）先是外循环，后是内循环，外循环的原则是从下边的最小值到下标的最大值，内循环的原则是，从外循环的下标+1开始向上循环，循环过程中，如果遇见外循环中的当前值比内循环中的当前值大，那么就把两个下标的值进行交换；

3、选择排序
   基本思路：分为外循环和内循环，外循环从最大下标开始循环，内循环从下边为1开始循环，一直循环到外循环的当前下标，挑选出本次内循环中值最大的下边，然后，如果值最大的下标不等于外循环的当前下标，那么就把外循环当前下标的值与最大值下标的值进行交换，这样循环下去，每次都选择出未排序的数组中最大的值，放到内循环最大下标处，这样就是选择排序，我们可以理解为每次循环都选择出最大值的下标，内循环接受后再进行值交换，与冒泡排序不同的是，冒泡排序是每次遇见非指定循序的值，就进行值交换，所以，在执行效率上，选择排序对于系统的开销更小一点；
  

   int a[] = { 30, 10, 40, 5 };
   for (int i = a.length; --i >= 0;) {
      int largest = 0;
      for (int j = 1; j <= i; j++) {
         if (a[largest] < a[j]) {
            largest = j;
         }
      }
      if (largest != i) {
         int T = a[largest];
         [largest] = a[i];
         a[i] = T;
      }
   }