排序研究一

　　排序是数据结构中重要的一个部分，也是在实际开发中最易遇到的问题之一，当然了，你也可以不考虑这些排序的算法，直接把要排序的数据insert到数据库中，用数据库的order by 再select一下，也能产生排序结果，不过，开发一个好的系统，性能同样很重要。

　　在一堆数据中，是比较的执行耗时多，还是复制交换的执行耗时比较多，大量数据比较时，是否会有内存限制等等，在综合这些因素后，我们选择适当的排序算法，常常会让系统性能提升数倍，当然了，如果你的系统中没有任何需要数据排序的，那就不考虑了。

　　所有的排序算法，都是在大数据量时才会显示出其运行差别，所以，在下面的讨论中，大家了解各特性，按需选用。（如果你觉得往数据库里插入数据，再带着order by 去select执行耗时最小，那就使用我提的这个方法吧）

　 注：以下的排序，均以int或long型来比较，其实，比较的元素可以是除这以外的任何对象，要对象实现比较功能，可参考jdk的compareable接口，这个后面再讨论。

所有的问题，都会有一个简单的解决方法，但它往往并不是最佳的方法。

一，冒泡排序

public void bubbleSort(int[] array) {
  int temp;
  for(int i=0;i<array.length-1;i++){ 
   for(int j=i+1;j<array.length;j++){
    if (array[i]>array[j]){
     temp=array[i];
     array[i]=array[j];
     array[j]=temp;
    }
   }
  }

　　这个是最简单，最易理解的排序算法。从队列的最左边开始，比较0号位置和1号位置的元素，如果左边的元素（０号）大，就让两个元素交换；如果右边的元素大，就什么也不做。然后右移一个位置比较1号位置和2号位置;沿着这个队列照这样比较下去，一直比较到队列的最右端，虽然没有把所有元素排好充，但是最大的那个元素已经在最右边了，也就像是在水底下冒泡一样，冒上来了。然后再从左边的1号开始，再循环前面的操作。。。。

　　可以看出，冒泡排序运行需要O(N^2)时间级别，其速度是很慢的,比较次数：N*(N-1)/2，交换次数最坏的情况也是：N*(N-1)/2。



2,选择排序

　　选择排序与冒泡排序有点相似，但是，选择排序对冒泡排序做了些许优化：减少元素交换的次数。
　　从下面的代码中，我们可以看出，通过每一次循环，标识出当前最小的元素，再做交换。

　　选择排序和冒泡排序执行了相同的比较次数：N*(N-1)/2,对于100个数据项就是要4950次比较，但选择排序只进行了不到100次交换。当N值很大时，比较的次数是主要的。所以，当N比较小，特别是如果交换的性能消耗比比较的性能消耗大得多时，用选择排序是相当快的。

public void selectionSort(int[] array)
      {
      int out, in, min,nElems=array.length;

      for(out=0; out<nElems-1; out++)   // 外层循环
         {
         min = out;                     // 最小值
         for(in=out+1; in<nElems; in++) // 内层循环
            if(a[in] < a[min] )         // 如果有比最小值还小的
                min = in;               // 得到新最小值
         swap(out, min);                // 交换
         }  // end for(out)
      }  // end selectionSort()

 

 private void swap(int one, int two)
      {
      long temp = a[one];
      a[one] = a[two];
      a[two] = temp;
      }

三，插入排序

　　插入排序的特点是局部有序,通过循环，在(局部)有序组中的适当位置插入元素进行排序。然而要做到这一点，就需要把部分已排序的队员右移以让出空间。当把最后一个要比较的元素移位之后，这个移动的过程就结束了。

public void insertionSort(int a[]){
      int in, out,nElems=a.length;

      for(out=1; out<nElems; out++) {    // 外层循环
          long temp = a[out];            // 先把要插入有序队列中的元素取出
         in = out;                      // 要从这个元素的左边开始依次比较了
         while(in>0 && a[in-1] >= temp){ // 比较条件,
            a[in] = a[in-1];            // 比temp大的元素，就要右移了
            --in;                       // 再比较左边的
            }
         a[in] = temp;                  // 找到合适的位置了
         }  // end for
      }  // end insertionSort()

　　在外层的for循环中，out变量从1开始，向右移动。它标记了未排序部分的最左端的数据。而在内层的while循环中，in变量从out变量开始，向左移动，直到temp变量小于in所指的数组数据项，或者它已经不能再往左移动了。while循环的每一趟都向右移动了一个已排序的数据项。

　　这个算法需要多少次比较和复制呢？在第一趟排序中，它最多比较一次，在第二趟中最多比较两次，依此类推了，最后一趟最多，N-1次.所以：

1+2+3+......+N-1=N*(N-1)/2

　　然而，在每一趟排序发现插入点之前，平均只有全体数据项的一半真的进行了比较，所以实际上大约是N*(N-1)/4 次 (这个值不是精确值，只是一个概率的估算值，学过数理统计的朋友就不要太过计较了)

　　复制的次数大致等于比较的次数，由于一次复制与一次交换的时间耗费不同，所以相对于随机数据，这个算法比冒泡排序快一倍，比选择排序略快。

　　如果数据基本有序，插入排序几乎只需要O(N)的时间；然后对于逆序排列的数据，每次比较和移动都会执行，所以这时插入排序并不比冒泡快。

　　大家在选择算法时，要注意了，在事先估算待排序数据的状况下，再选择相应的算法。



四，有序链表排序

这里存储数据的方式就不是前面讨论的用数组来存储了，而是用链表这一个数据结构。

　　有序链表排序是一种高效的排序机制。所设有一个无序数组，如果从这个数组中取出数据，然后一个一个地插入有序链表，它们自动地按序排列，把它们从链表中删除重新放入数组，那么数组就会排好序了。

建立链表类Link.java：

class Link
   {
   public long dData;                  

   public Link next;                   
   public Link(long dd)              
      { dData = dd; }
   }  

建立有序链表SortedList.java

class SortedList
   {
   private Link first;            
   public SortedList()            
      { first = null; }                   
   public SortedList(Link[] linkArr)  

      {                               

      first = null;                        
      for(int j=0; j<linkArr.length; j++)  
         insert( linkArr[j] );             

      }
   public void insert(Link k)     

      {
      Link previous = null;            
      Link current = first;
                                       

      while(current != null && k.dData > current.dData)
         {                             

         previous = current;
         current = current.next;       
         }
      if(previous==null)              
         first = k;                    

      else                             
         previous.next = k;            

      k.next = current;               
      }  // end insert()
   public Link remove()           

      {                           
      Link temp = first;             

      first = first.next;             

      return temp;                     

      }
   }  

测试类ListInsertionSortApp.java:

class ListInsertionSortApp
   {
   public static void main(String[] args)
      {
      int size = 10;
                                 // 建立一个随机数组
      Link[] linkArray = new Link[size];

      for(int j=0; j<size; j++)  

         {                            
         int n = (int)(java.lang.Math.random()*99);
         Link newLink = new Link(n);  // 建立链表

         linkArray[j] = newLink;      

         }
                                 
      System.out.print("Unsorted array: ");
      for(int j=0; j<size; j++)
         System.out.print( linkArray[j].dData + " " );
      System.out.println("");

      SortedList theSortedList = new SortedList(linkArray);

      for(int j=0; j<size; j++)  
         linkArray[j] = theSortedList.remove();

                                 
      System.out.print("Sorted Array:   ");
      for(int j=0; j<size; j++)
         System.out.print(linkArray[j].dData + " ");
      System.out.println("");
      } 

   }  

　　这种排序方式总体上比在数组中用常用的插入排序效率更高一些，因为这种方式进行的复制次数少一些，但它仍然是一个时间级为O(N^2)的过程，因为在有序链表中每插入一个新的链结点，平均要与一半已存在数据进行比较。如果插入N个新数据，就进行了N*N/4次比较。每一个链结点只进行两次复制：一次从数组到链表，一次从链表到数组。在数组中进行插入排序需要N*N次移动，相比之下，２*N次移动更好。

注：以上提供的算法出自《Data Structures & Algorithms in Java》by Robert Lafore Sams © 1998

嗯，再写写二叉树，红黑树和AVL树就比较全了。

1. 我相信 java 标准库里面有快速排序的实现吧？
2. 通常人们说的冒泡排序不是那样的，而是只会比较交换相邻的两个元素。
3. 最后这个所谓的有序链表排序 …… 我还从来没见过这种玩法，考虑到操作链表的开销，真的有人这么干么？

冒泡排序确实有问题，对于一个n个元素的正序序列，冒泡排序跑一次就可以了，而这个“冒泡排序”可还是要跑n次。

其中内循环中的交换对随后的操作是无意义的，而冒泡排序中的交换是有一定意义的，它使得大元素缓慢向后移动。

自然而然，有人就想到了，使得移动步骤大点，使得大元素可以快速移动到序列的尾部。

呵呵，jdk源码中的TreeMap类的实现采用了红黑树，前几天刚看了一下。

呜，红黑树涉及的情况真多，要想自己正确写出来，还是要费点精力

有序链表换成binary search tree，效率可以提高不少，运气好的话，还可以捞个logN。
再说，排序的目的经常是为了更快的查找，有序链表查找可比不过有序数组，有序数组可以采用折半查找。

采用bst，那就可以达到“折半查找”的效果。

内排序怎么玩都行－－标准的快速排序法已经足够好了，标准库也有实现。麻烦的是外排序。还是以前学数据结构时写过一点排序，之后就再也没写过了。

这段时间正忙，周末争取把希尔排序，快速排序,归并等整理出来。

这些一般数据结构和算法的书上都有,有什么意义?

呵，自娱自乐，再温习一下其内的思路， 为解决其它问题提供好的想法构思。
欢迎有不同意见。