排序算法(zt)

上一篇 / 下一篇  2007-05-25 15:28:00 / 个人分类：.Net 开发

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

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

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

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

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

一，冒泡排序

代码
  1. public void bubbleSort(int[] array) {   
  2.   int temp;   
  3.   for(int i=0;i<array.length-1;i++){    
  4.    for(int j=i+1;j<array.length;j++){   
  5.     if (array>array[j]){   
  6.      temp=array;   
  7.      array=array[j];   
  8.      array[j]=temp;   
  9.     }   
  10.    }   
  11.   }   

　　这个是最简单，最易理解的排序算法。从队列的最左边开始，比较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比较小，特别是如果交换的性能消耗比比较的性能消耗大得多时，用选择排序是相当快的。

代码
  1. public void selectionSort(int[] array)   
  2.       {   
  3.       int out, in, min,nElems=array.length;   
  4.   
  5.       for(out=0; out<nElems-1; out++)   // 外层循环   
  6.          {   
  7.          min = out;                     // 最小值   
  8.          for(in=out+1; in<nElems; in++) // 内层循环   
  9.             if(a[in] < a[min] )         // 如果有比最小值还小的   
  10.                 min = in;               // 得到新最小值   
  11.          swap(out, min);                // 交换   
  12.          }  // end for(out)   
  13.       }  // end selectionSort()   
  14.   
  15.     
  16.   
  17.  private void swap(int one, int two)   
  18.       {   
  19.       long temp = a[one];   
  20.       a[one] = a[two];   
  21.       a[two] = temp;   
  22.       }   

三，插入排序

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

代码
  1. public void insertionSort(int a[]){   
  2.       int in, out,nElems=a.length;   
  3.   
  4.       for(out=1; out<nElems; out++) {    // 外层循环   
  5.           long temp = a[out];            // 先把要插入有序队列中的元素取出   
  6.          in = out;                      // 要从这个元素的左边开始依次比较了   
  7.          while(in>0 && a[in-1] >= temp){ // 比较条件,   
  8.             a[in] = a[in-1];            // 比temp大的元素，就要右移了   
  9.             --in;                       // 再比较左边的   
  10.             }   
  11.          a[in] = temp;                  // 找到合适的位置了   
  12.          }  // end for   
  13.       }  // end insertionSort()   
  14.   

　　在外层的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：

代码
  1. class Link   
  2.    {   
  3.    public long dData;                     
  4.   
  5.    public Link next;                      
  6.    public Link(long dd)                 
  7.       { dData = dd; }   
  8.    }     

建立有序链表SortedList.java

代码
  1. class SortedList   
  2.    {   
  3.    private Link first;               
  4.    public SortedList()               
  5.       { first = null; }                      
  6.    public SortedList(Link[] linkArr)     
  7.   
  8.       {                                  
  9.   
  10.       first = null;                           
  11.       for(int j=0; j<linkArr.length; j++)     
  12.          insert( linkArr[j] );                
  13.   
  14.       }   
  15.    public void insert(Link k)        
  16.   
  17.       {   
  18.       Link previous = null;               
  19.       Link current = first;   
  20.                                           
  21.   
  22.       while(current != null && k.dData > current.dData)   
  23.          {                                
  24.   
  25.          previous = current;   
  26.          current = current.next;          
  27.          }   
  28.       if(previous==null)                 
  29.          first = k;                       
  30.   
  31.       else                                
  32.          previous.next = k;               
  33.   
  34.       k.next = current;                  
  35.       }  // end insert()   
  36.    public Link remove()              
  37.   
  38.       {                              
  39.       Link temp = first;                
  40.   
  41.       first = first.next;                
  42.   
  43.       return temp;                        
  44.   
  45.       }   
  46.    }     

测试类ListInsertionSortApp.java:

代码
  1. class ListInsertionSortApp   
  2.    {   
  3.    public static void main(String[] args)   
  4.       {   
  5.       int size = 10;   
  6.                                  // 建立一个随机数组   
  7.       Link[] linkArray = new Link[size];   
  8.   
  9.       for(int j=0; j<size; j++)     
  10.   
  11.          {                               
  12.          int n = (int)(java.lang.Math.random()*99);   
  13.          Link newLink = new Link(n);  // 建立链表   
  14.   
  15.          linkArray[j] = newLink;         
  16.   
  17.          }   
  18.                                     
  19.       System.out.print("Unsorted array: ");   
  20.       for(int j=0; j<size; j++)   
  21.          System.out.print( linkArray[j].dData + " " );   
  22.       System.out.println("");   
  23.   
  24.       SortedList theSortedList = new SortedList(linkArray);   
  25.   
  26.       for(int j=0; j<size; j++)     
  27.          linkArray[j] = theSortedList.remove();   
  28.   
  29.                                     
  30.       System.out.print("Sorted Array:   ");   
  31.       for(int j=0; j<size; j++)   
  32.          System.out.print(linkArray[j].dData + " ");   
  33.       System.out.println("");   
  34.       }    
  35.   
  36.    }     　排序是数据结构中重要的一个部分，也是在实际开发中最易遇到的问题之一，当然了，你也可以不考虑这些排序的算法，直接把要排序的数据insert到数据库中，用数据库的order by 再select一下，也能产生排序结果，不过，开发一个好的系统，性能同样很重要。

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

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

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

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

    一，冒泡排序

    代码
    1. public void bubbleSort(int[] array) {   
    2.   int temp;   
    3.   for(int i=0;i<array.length-1;i++){    
    4.    for(int j=i+1;j<array.length;j++){   
    5.     if (array>array[j]){   
    6.      temp=array;   
    7.      array=array[j];   
    8.      array[j]=temp;   
    9.     }   
    10.    }   
    11.   }   

    　　这个是最简单，最易理解的排序算法。从队列的最左边开始，比较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比较小，特别是如果交换的性能消耗比比较的性能消耗大得多时，用选择排序是相当快的。

    代码
    1. public void selectionSort(int[] array)   
    2.       {   
    3.       int out, in, min,nElems=array.length;   
    4.   
    5.       for(out=0; out<nElems-1; out++)   // 外层循环   
    6.          {   
    7.          min = out;                     // 最小值   
    8.          for(in=out+1; in<nElems; in++) // 内层循环   
    9.             if(a[in] < a[min] )         // 如果有比最小值还小的   
    10.                 min = in;               // 得到新最小值   
    11.          swap(out, min);                // 交换   
    12.          }  // end for(out)   
    13.       }  // end selectionSort()   
    14.   
    15.     
    16.   
    17.  private void swap(int one, int two)   
    18.       {   
    19.       long temp = a[one];   
    20.       a[one] = a[two];   
    21.       a[two] = temp;   
    22.       }   

    三，插入排序

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

    代码
    1. public void insertionSort(int a[]){   
    2.       int in, out,nElems=a.length;   
    3.   
    4.       for(out=1; out<nElems; out++) {    // 外层循环   
    5.           long temp = a[out];            // 先把要插入有序队列中的元素取出   
    6.          in = out;                      // 要从这个元素的左边开始依次比较了   
    7.          while(in>0 && a[in-1] >= temp){ // 比较条件,   
    8.             a[in] = a[in-1];            // 比temp大的元素，就要右移了   
    9.             --in;                       // 再比较左边的   
    10.             }   
    11.          a[in] = temp;                  // 找到合适的位置了   
    12.          }  // end for   
    13.       }  // end insertionSort()   
    14.   

    　　在外层的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：

    代码
    1. class Link   
    2.    {   
    3.    public long dData;                     
    4.   
    5.    public Link next;                      
    6.    public Link(long dd)                 
    7.       { dData = dd; }   
    8.    }     

    建立有序链表SortedList.java

    代码
    1. class SortedList   
    2.    {   
    3.    private Link first;               
    4.    public SortedList()               
    5.       { first = null; }                      
    6.    public SortedList(Link[] linkArr)     
    7.   
    8.       {                                  
    9.   
    10.       first = null;                           
    11.       for(int j=0; j<linkArr.length; j++)     
    12.          insert( linkArr[j] );                
    13.   
    14.       }   
    15.    public void insert(Link k)        
    16.   
    17.       {   
    18.       Link previous = null;               
    19.       Link current = first;   
    20.                                           
    21.   
    22.       while(current != null && k.dData > current.dData)   
    23.          {                                
    24.   
    25.          previous = current;   
    26.          current = current.next;          
    27.          }   
    28.       if(previous==null)                 
    29.          first = k;                       
    30.   
    31.       else                                
    32.          previous.next = k;               
    33.   
    34.       k.next = current;                  
    35.       }  // end insert()   
    36.    public Link remove()              
    37.   
    38.       {                              
    39.       Link temp = first;                
    40.   
    41.       first = first.next;                
    42.   
    43.       return temp;                        
    44.   
    45.       }   
    46.    }     

    测试类ListInsertionSortApp.java:

    代码
    1. class ListInsertionSortApp   
    2.    {   
    3.    public static void main(String[] args)   
    4.       {   
    5.       int size = 10;   
    6.                                  // 建立一个随机数组   
    7.       Link[] linkArray = new Link[size];   
    8.   
    9.       for(int j=0; j<size; j++)     
    10.   
    11.          {                               
    12.          int n = (int)(java.lang.Math.random()*99);   
    13.          Link newLink = new Link(n);  // 建立链表   
    14.   
    15.          linkArray[j] = newLink;         
    16.   
    17.          }   
    18.                                     
    19.       System.out.print("Unsorted array: ");   
    20.       for(int j=0; j<size; j++)   
    21.          System.out.print( linkArray[j].dData + " " );   
    22.       System.out.println("");   
    23.   
    24.       SortedList theSortedList = new SortedList(linkArray);   
    25.   
    26.       for(int j=0; j<size; j++)     
    27.          linkArray[j] = theSortedList.remove();   
    28.   
    29.                                     
    30.       System.out.print("Sorted Array:   ");   
    31.       for(int j=0; j<size; j++)   
    32.          System.out.print(linkArray[j].dData + <

    导入论坛 引用链接 收藏 分享给好友 管理 举报

    TAG:

    betty 引用 删除 betty   /   2007-06-11 09:45:00

    师兄，来踩啦，呵呵


    这有个快速排序的倒序排序算法，C#


    using System.IO;
    using System.IO.Compression;


    namespace QuickSorter
    {
         public class QuickSorter
         {
              // 两个数值互换位置
              private void Swap(ref int l,ref int r)
              {
                   int s;
                   s=l;
                   l=r;
                   r=s;
              }
             
              // 排序过程
              public void Sort(int [] list,int low,int high)
              {
                   int pivot;
                   int l,r;
                   int mid;


                   if (high <= low)
                   {
                       return;
                   }
                   else if (high == low + 1)
                   {
                       if (list[low] < list[high])
                       {
                           Swap(ref list[low], ref list[high]);
                       }
                       return;
                   }


                   mid=(low+high)>>1;
                   pivot=list[mid];


                   Swap(ref list[low],ref list[mid]);


                   l=low+1;
                   r=high;


                   do
                   {
                       while (l <= r && list[l] > pivot)
                       {
                           l++;
                       }
                       while (r>=l && list[r] <= pivot)
                       {
                           r--;
                       }
                       if (l < r)
                       {
                           Swap(ref list[l], ref list[r]);
                       }
                   }while(l<r);


                   list[low]=list[r];
                   list[r]=pivot;


                   if (low + 1 < r)
                   {
                       Sort(list, low, r - 1);
                   }
                   if (r + 1 < high)
                   {
                       Sort(list, r + 1, high);
                   }
              }
         }
            


    }


     

     

    评分：0

    我来说两句

    显示全部

    :loveliness: :handshake :victory: :funk: :time: :kiss: :call: :hug: :lol :'( :Q :L ;P :$ :P :o :@ :D :( :)