posts - 4, comments - 5, trackbacks - 0, articles - 10

java排序法

Posted on 2005-12-05 20:24 勇敢的心 阅读(605) 评论(0)  编辑  收藏 所属分类: Java
/*这个程序是我在一个帖子上看到的，觉得写的十分的不错，拿出来与大家共享下*/
package com.cucu.test; 

public class Sort { 

  public void swap(int a[], int i, int j) { 
    int tmp = a[i]; 
    a[i] = a[j]; 
    a[j] = tmp; 
  } 

  public int partition(int a[], int low, int high) { 
    int pivot, p_pos, i; 
    p_pos = low; 
    pivot = a[p_pos]; 
    for (i = low + 1; i <= high; i++) { 
      if (a[i] > pivot) { 
        p_pos++; 
        swap(a, p_pos, i); 
      } 
    } 
    swap(a, low, p_pos); 
    return p_pos; 
  } 

  public void quicksort(int a[], int low, int high) { 
    int pivot; 
    if (low < high) { 
      pivot = partition(a, low, high); 
      quicksort(a, low, pivot - 1); 
      quicksort(a, pivot + 1, high); 
    } 

  } 

  public static void main(String args[]) { 
    int vec[] = new int[] { 37, 47, 23, -5, 19, 56 }; 
    int temp; 
    //选择排序法(Selection Sort) 
    long begin = System.currentTimeMillis(); 
    for (int k = 0; k < 1000000; k++) { 
      for (int i = 0; i < vec.length; i++) { 
        for (int j = i; j < vec.length; j++) { 
          if (vec[j] > vec[i]) { 
            temp = vec[i]; 
            vec[i] = vec[j]; 
            vec[j] = temp; 
          } 
        } 

      } 
    } 
    long end = System.currentTimeMillis(); 
    System.out.println("选择法用时为：" + (end - begin)); 
    //打印排序好的结果 
    for (int i = 0; i < vec.length; i++) { 
      System.out.println(vec[i]); 
    } 
    //  冒泡排序法(Bubble Sort) 
    begin = System.currentTimeMillis(); 
    for (int k = 0; k < 1000000; k++) { 
      for (int i = 0; i < vec.length; i++) { 
        for (int j = i; j < vec.length - 1; j++) { 
          if (vec[j + 1] > vec[j]) { 
            temp = vec[j + 1]; 
            vec[j + 1] = vec[j]; 
            vec[j] = temp; 
          } 
        } 

      } 
    } 
    end = System.currentTimeMillis(); 
    System.out.println("冒泡法用时为：" + (end - begin)); 
    //打印排序好的结果 
    for (int i = 0; i < vec.length; i++) { 
      System.out.println(vec[i]); 
    } 

    //插入排序法(Insertion Sort) 
    begin = System.currentTimeMillis(); 
    for (int k = 0; k < 1000000; k++) { 
      for (int i = 1; i < vec.length; i++) { 
        int j = i; 
        while (vec[j - 1] < vec[i]) { 
          vec[j] = vec[j - 1]; 
          j--; 
          if (j <= 0) { 
            break; 
          } 
        } 
        vec[j] = vec[i]; 
      } 
    } 
    end = System.currentTimeMillis(); 
    System.out.println("插入法用时为：" + (end - begin)); 
    //打印排序好的结果 
    for (int i = 0; i < vec.length; i++) { 
      System.out.println(vec[i]); 
    } 

    //快速排序法(Quick Sort) 

    Sort s = new Sort(); 
    begin = System.currentTimeMillis(); 
    for (int k = 0; k < 1000000; k++) { 
      s.quicksort(vec, 0, 5); 
    } 
    end = System.currentTimeMillis(); 
    System.out.println("快速法用时为：" + (end - begin)); 
    //打印排序好的结果 
    for (int i = 0; i < vec.length; i++) { 
      System.out.println(vec[i]); 
    } 
  } 

} 

************************************************************************************

  1. package org.jr.util;

  3. /**
  4. * Copyright: Copyright (c) 2002-2004
  5. * Company: JavaResearch(http://www.javaresearch.org)
  6. * 最后更新日期:2003年3月4日
  7. * @author Cherami
  8. */

  10. import org.jr.*;

  12. /**
  13. * 排序工具类，提供常见的需要排序但是又没有实现Comparable接口的类。
  14. * 此类也提供一些创建的排序算法的范例。
  15. * @since  0.5
  16. */

  18. public class CompareUtil {
  19.   /**
  20.    * 私有构造方法，防止类的实例化，因为工具类不需要实例化。
  21.    */
  22.   private CompareUtil() {
  23.   }

  25.   /**
  26.    * 比较两个数字。
  27.    * 这个方法取Number的double值进行比较，因此只有在两个数严格相等的情况下才返回0，
  28.    * 又可能因为Java中Double型和Float的精度不同而导致两个相等的数不返回0。
  29.    * @param o1 第一个数字
  30.    * @param o2 第二个数字
  31.    * @return 第一个数字大于第二个返回1，等于返回0，否则返回－1
  32.    * @since  0.5
  33.    */
  34.   public static int compare(Number o1, Number o2) {
  35.     double n1 = o1.doubleValue();
  36.     double n2 = o2.doubleValue();
  37.     if (n1 < n2) {
  38.       return -1;
  39.     }
  40.     else if (n1 > n2) {
  41.       return 1;
  42.     }
  43.     else {
  44.       return 0;
  45.     }
  46.   }

  48.   /**
  49.    * 比较两个布尔型值。
  50.    * 如果两个的值不同，true被认为等于1，而false等于0。
  51.    * @param o1 第一个值
  52.    * @param o2 第二个值
  53.    * @return 第一个值大于第二个返回1，等于返回0，否则返回-1
  54.    * @since  0.5
  55.    */
  56.   public static int compare(Boolean o1, Boolean o2) {
  57.     boolean b1 = o1.booleanValue();
  58.     boolean b2 = o2.booleanValue();
  59.     if (b1 == b2) {
  60.       return 0;
  61.     }
  62.     else if (b1) {
  63.       return 1;
  64.     }
  65.     else {
  66.       return -1;
  67.     }
  68.   }

  70.   /**
  71.    * 冒泡排序法排序。
  72.    * @param objects 排序对象
  73.    * @param isAscent 排序顺序
  74.    * @return 排序后应该有的索引数组
  75.    * @since  0.5
  76.    */
  77.   public static int[] n2sort(Comparable[] objects, boolean isAscent) {
  78.     int length = objects.length;
  79.     int[] indexes = ArrayUtil.getInitedIntArray(length);
  80.     for (int i = 0; i < length; i++) {
  81.       for (int j = i + 1; j < length; j++) {
  82.         if (isAscent == true) {
  83.           if (objects[indexes[i]].compareTo(objects[indexes[j]]) > 0) {
  84.             swap(indexes, i, j);
  85.           }
  86.         }
  87.         else {
  88.           if (objects[indexes[i]].compareTo(objects[indexes[j]]) < 0) {
  89.             swap(indexes, i, j);
  90.           }
  91.         }
  92.       }
  93.     }
  94.     return indexes;
  95.   }

  97.   /**
  98.    * 冒泡排序法排序。
  99.    * @param objects 排序对象
  100.    * @param key 排序关键字
  101.    * @param isAscent 排序顺序
  102.    * @return 排序后应该有的索引数组
  103.    * @since  0.5
  104.    */
  105.   public static int[] n2sort(PropertyComparable[] objects, int key,
  106.                              boolean isAscent) {
  107.     int length = objects.length;
  108.     int[] indexes = ArrayUtil.getInitedIntArray(length);
  109.     for (int i = 0; i < length; i++) {
  110.       for (int j = i + 1; j < length; j++) {
  111.         if (isAscent == true) {
  112.           if (objects[indexes[i]].compareTo(objects[indexes[j]], key) > 0) {
  113.             swap(indexes, i, j);
  114.           }
  115.         }
  116.         else {
  117.           if (objects[indexes[i]].compareTo(objects[indexes[j]], key) < 0) {
  118.             swap(indexes, i, j);
  119.           }
  120.         }
  121.       }
  122.     }
  123.     return indexes;
  124.   }

  126.   /**
  127.    * 冒泡排序法排序。
  128.    * @param objects 排序对象
  129.    * @return 按照升序排序后应该有的索引数组
  130.    * @since  0.6
  131.    */
  132.   public static int[] n2sort(Comparable[] objects) {
  133.     return n2sort(objects,true);
  134.   }

  136.   /**
  137.    * 冒泡排序法排序。
  138.    * @param objects 排序对象
  139.    * @param key 排序关键字
  140.    * @return 按照升序排序后应该有的索引数组
  141.    * @since  0.6
  142.    */
  143.   public static int[] n2sort(PropertyComparable[] objects, int key) {
  144.     return n2sort(objects,key);
  145.   }

  147.   /**
  148.    * 插入排序法排序。
  149.    * @param objects 排序对象
  150.    * @return 按照升序排序后应该有的索引数组
  151.    * @since  0.6
  152.    */
  153.   public static int[] insertionSort(Comparable[] objects) {
  154.     int length = objects.length;
  155.     int[] indexes = ArrayUtil.getInitedIntArray(length);
  156.     for (int i = 1; i < length; i++) {
  157.         int j = i;
  158.         Comparable B = objects[indexes[i]];
  159.         while ((j > 0) && (objects[indexes[j-1]].compareTo(B) > 0)) {
  160.             indexes[j] = indexes[j-1];
  161.             j--;
  162.         }
  163.         indexes[j] = i;
  164.     }
  165.     return indexes;
  166.   }

  168.   /**
  169.    * 插入排序法排序。
  170.    * @param objects 排序对象
  171.    * @param key 排序关键字
  172.    * @return 按照升序排序后应该有的索引数组
  173.    * @since  0.6
  174.    */
  175.   public static int[] insertionSort(PropertyComparable[] objects, int key) {
  176.     int length = objects.length;
  177.     int[] indexes = ArrayUtil.getInitedIntArray(length);
  178.     for (int i = 1; i < length; i++) {
  179.         int j = i;
  180.         Comparable B = objects[indexes[i]];
  181.         while ((j > 0) && (objects[indexes[j-1]].compareTo(B,key) > 0)) {
  182.             indexes[j] = indexes[j-1];
  183.             j--;
  184.         }
  185.         indexes[j] = i;
  186.     }
  187.     return indexes;
  188.   }

  190.   /**
  191.    * 选择排序法排序。
  192.    * @param objects 排序对象
  193.    * @return 按照升序排序后应该有的索引数组
  194.    * @since  0.6
  195.    */
  196.   public static int[] selectionSort(Comparable[] objects) {
  197.     int length = objects.length;
  198.     int[] indexes = ArrayUtil.getInitedIntArray(length);
  199.     for (int i = 0; i < length; i++) {
  200.         int min = i;
  201.         int j;
  202.         //在未排序列表里面查找最小元素
  203.         for (j = i + 1; j < length; j++) {
  204.             if (objects[indexes[j]].compareTo(objects[indexes[min]]) <0 ) {
  205.                 min = j;
  206.             }
  207.         }
  208.         //将最小的元素交换到未排序元素的最开始
  209.         swap(indexes,i,min);
  210.     }
  211.     return indexes;
  212.   }

  214.   /**
  215.    * 选择排序法排序。
  216.    * @param objects 排序对象
  217.    * @param key 排序关键字
  218.    * @return 按照升序排序后应该有的索引数组
  219.    * @since  0.6
  220.    */
  221.   public static int[] selectionSort(PropertyComparable[] objects, int key) {
  222.     int length = objects.length;
  223.     int[] indexes = ArrayUtil.getInitedIntArray(length);
  224.     for (int i = 0; i < length; i++) {
  225.         int min = i;
  226.         int j;
  227.         //在未排序列表里面查找最小元素
  228.         for (j = i + 1; j < length; j++) {
  229.             if (objects[indexes[j]].compareTo(objects[indexes[min]],key) <0 ) {
  230.                 min = j;
  231.             }
  232.         }
  233.         //将最小的元素交换到未排序元素的最开始
  234.         swap(indexes,i,min);
  235.     }
  236.     return indexes;
  237.   }

  239.   /**
  240.    * 双向冒泡排序法排序。
  241.    * @param objects 排序对象
  242.    * @return 按照升序排序后应该有的索引数组
  243.    * @since  0.6
  244.    */
  245.   public static int[] bidirectionalBubbleSort(Comparable[] objects) {
  246.     int length = objects.length;
  247.     int[] indexes = ArrayUtil.getInitedIntArray(length);
  248.     int j;
  249.     int limit = objects.length;
  250.     int start = -1;
  251.     while (start < limit) {
  252.         start++;
  253.         limit--;
  254.         for (j = start; j < limit; j++) {
  255.             if (objects[indexes[j]].compareTo(objects[indexes[j+1]]) > 0) {
  256.               swap(indexes,j,j+1);
  257.             }
  258.         }
  259.         for (j = limit; --j >= start;) {
  260.           if (objects[indexes[j]].compareTo(objects[indexes[j+1]]) > 0) {
  261.             swap(indexes,j,j+1);
  262.           }
  263.         }
  264.     }
  265.     return indexes;
  266.   }

  268.   /**
  269.    * 双向冒泡排序法排序。
  270.    * @param objects 排序对象
  271.    * @param key 排序关键字
  272.    * @return 按照升序排序后应该有的索引数组
  273.    * @since  0.6
  274.    */
  275.   public static int[] bidirectionalBubbleSort(PropertyComparable[] objects, int key) {
  276.     int length = objects.length;
  277.     int[] indexes = ArrayUtil.getInitedIntArray(length);
  278.     int j;
  279.     int limit = objects.length;
  280.     int start = -1;
  281.     while (start < limit) {
  282.         start++;
  283.         limit--;
  284.         for (j = start; j < limit; j++) {
  285.             if (objects[indexes[j]].compareTo(objects[indexes[j+1]]) > 0) {
  286.               swap(indexes,j,j+1);
  287.             }
  288.         }
  289.         for (j = limit; --j >= start;) {
  290.           if (objects[indexes[j]].compareTo(objects[indexes[j+1]],key) > 0) {
  291.             swap(indexes,j,j+1);
  292.           }
  293.         }
  294.     }
  295.     return indexes;
  296.   }

  298.   /**
  299.    * 交换两个元素的值。
  300.    * @param indexes 原索引数组
  301.    * @param i 第一行
  302.    * @param j 第二行
  303.    */
  304.   private static void swap(int[] indexes, int i, int j) {
  305.     int tmp = indexes[i];
  306.     indexes[i] = indexes[j];
  307.     indexes[j] = tmp;
  308.   }

  310. }
  311. ------------------------------------------
  313. 冒泡排序：

  314. 1、比较相邻的两个元素，如果后面的比前面小，就对调二者。反复比较，到最后两个元素。结果，最大值就跑到了最末位置。

  315. 2、反复第一步，直到所有较大值都跑到靠后的位置。

  316. ---------------------------------------------

  317. 选择排序

  318. 1、一开始整个数列是未排列的

  319. 2、从未排列的数中，挑选出最小的数，和未排列的数中的第一个元素互调，并将该最小的数归类到已排序的序列中；

  320. 3、重复第2步，直到所有的数都归类到已排序数列中。

  321. ---------------------------------------------

  322. 插入排序法：

  323. 1、一开始只有第一个数在已排序数列中，其他的数归类到未排序数列中；

  324. 2、将未排序的第一个数，插入到已排序数列中，使得插入后的已排序数列仍然维持由小到大的顺序；

  325. 3、重复步骤2，直到所有的数都在已排序数列中。

  326. -----------------------------------------------


只有注册用户登录后才能发表评论。
网站导航: