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

          java排序法

          Posted on 2005-12-05 20:24 勇敢的心 閱讀(612) 評(píng)論(0)  編輯  收藏 所屬分類: Java
          /*這個(gè)程序是我在一個(gè)帖子上看到的,覺(jué)得寫(xiě)的十分的不錯(cuò),拿出來(lái)與大家共享下*/
          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("選擇法用時(shí)為:" + (end - begin)); 
              //打印排序好的結(jié)果 
              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("冒泡法用時(shí)為:" + (end - begin)); 
              //打印排序好的結(jié)果 
              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("插入法用時(shí)為:" + (end - begin)); 
              //打印排序好的結(jié)果 
              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("快速法用時(shí)為:" + (end - begin)); 
              //打印排序好的結(jié)果 
              for (int i = 0; i < vec.length; i++) { 
                System.out.println(vec[i]); 
              } 
            } 



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

          1. package org.jr.util;

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

          8. import org.jr.*;

          9. /**
          10. * 排序工具類,提供常見(jiàn)的需要排序但是又沒(méi)有實(shí)現(xiàn)Comparable接口的類。
          11. * 此類也提供一些創(chuàng)建的排序算法的范例。
          12. * @since  0.5
          13. */

          14. public class CompareUtil {
          15.   /**
          16.    * 私有構(gòu)造方法,防止類的實(shí)例化,因?yàn)楣ぞ哳惒恍枰獙?shí)例化。
          17.    */
          18.   private CompareUtil() {
          19.   }

          20.   /**
          21.    * 比較兩個(gè)數(shù)字。
          22.    * 這個(gè)方法取Number的double值進(jìn)行比較,因此只有在兩個(gè)數(shù)嚴(yán)格相等的情況下才返回0,
          23.    * 又可能因?yàn)镴ava中Double型和Float的精度不同而導(dǎo)致兩個(gè)相等的數(shù)不返回0。
          24.    * @param o1 第一個(gè)數(shù)字
          25.    * @param o2 第二個(gè)數(shù)字
          26.    * @return 第一個(gè)數(shù)字大于第二個(gè)返回1,等于返回0,否則返回-1
          27.    * @since  0.5
          28.    */
          29.   public static int compare(Number o1, Number o2) {
          30.     double n1 = o1.doubleValue();
          31.     double n2 = o2.doubleValue();
          32.     if (n1 < n2) {
          33.       return -1;
          34.     }
          35.     else if (n1 > n2) {
          36.       return 1;
          37.     }
          38.     else {
          39.       return 0;
          40.     }
          41.   }

          42.   /**
          43.    * 比較兩個(gè)布爾型值。
          44.    * 如果兩個(gè)的值不同,true被認(rèn)為等于1,而false等于0。
          45.    * @param o1 第一個(gè)值
          46.    * @param o2 第二個(gè)值
          47.    * @return 第一個(gè)值大于第二個(gè)返回1,等于返回0,否則返回-1
          48.    * @since  0.5
          49.    */
          50.   public static int compare(Boolean o1, Boolean o2) {
          51.     boolean b1 = o1.booleanValue();
          52.     boolean b2 = o2.booleanValue();
          53.     if (b1 == b2) {
          54.       return 0;
          55.     }
          56.     else if (b1) {
          57.       return 1;
          58.     }
          59.     else {
          60.       return -1;
          61.     }
          62.   }

          63.   /**
          64.    * 冒泡排序法排序。
          65.    * @param objects 排序?qū)ο?/FONT>
          66.    * @param isAscent 排序順序
          67.    * @return 排序后應(yīng)該有的索引數(shù)組
          68.    * @since  0.5
          69.    */
          70.   public static int[] n2sort(Comparable[] objects, boolean isAscent) {
          71.     int length = objects.length;
          72.     int[] indexes = ArrayUtil.getInitedIntArray(length);
          73.     for (int i = 0; i < length; i++) {
          74.       for (int j = i + 1; j < length; j++) {
          75.         if (isAscent == true) {
          76.           if (objects[indexes[i]].compareTo(objects[indexes[j]]) > 0) {
          77.             swap(indexes, i, j);
          78.           }
          79.         }
          80.         else {
          81.           if (objects[indexes[i]].compareTo(objects[indexes[j]]) < 0) {
          82.             swap(indexes, i, j);
          83.           }
          84.         }
          85.       }
          86.     }
          87.     return indexes;
          88.   }

          89.   /**
          90.    * 冒泡排序法排序。
          91.    * @param objects 排序?qū)ο?/FONT>
          92.    * @param key 排序關(guān)鍵字
          93.    * @param isAscent 排序順序
          94.    * @return 排序后應(yīng)該有的索引數(shù)組
          95.    * @since  0.5
          96.    */
          97.   public static int[] n2sort(PropertyComparable[] objects, int key,
          98.                              boolean isAscent) {
          99.     int length = objects.length;
          100.     int[] indexes = ArrayUtil.getInitedIntArray(length);
          101.     for (int i = 0; i < length; i++) {
          102.       for (int j = i + 1; j < length; j++) {
          103.         if (isAscent == true) {
          104.           if (objects[indexes[i]].compareTo(objects[indexes[j]], key) > 0) {
          105.             swap(indexes, i, j);
          106.           }
          107.         }
          108.         else {
          109.           if (objects[indexes[i]].compareTo(objects[indexes[j]], key) < 0) {
          110.             swap(indexes, i, j);
          111.           }
          112.         }
          113.       }
          114.     }
          115.     return indexes;
          116.   }

          117.   /**
          118.    * 冒泡排序法排序。
          119.    * @param objects 排序?qū)ο?/FONT>
          120.    * @return 按照升序排序后應(yīng)該有的索引數(shù)組
          121.    * @since  0.6
          122.    */
          123.   public static int[] n2sort(Comparable[] objects) {
          124.     return n2sort(objects,true);
          125.   }

          126.   /**
          127.    * 冒泡排序法排序。
          128.    * @param objects 排序?qū)ο?/FONT>
          129.    * @param key 排序關(guān)鍵字
          130.    * @return 按照升序排序后應(yīng)該有的索引數(shù)組
          131.    * @since  0.6
          132.    */
          133.   public static int[] n2sort(PropertyComparable[] objects, int key) {
          134.     return n2sort(objects,key);
          135.   }

          136.   /**
          137.    * 插入排序法排序。
          138.    * @param objects 排序?qū)ο?/FONT>
          139.    * @return 按照升序排序后應(yīng)該有的索引數(shù)組
          140.    * @since  0.6
          141.    */
          142.   public static int[] insertionSort(Comparable[] objects) {
          143.     int length = objects.length;
          144.     int[] indexes = ArrayUtil.getInitedIntArray(length);
          145.     for (int i = 1; i < length; i++) {
          146.         int j = i;
          147.         Comparable B = objects[indexes[i]];
          148.         while ((j > 0) && (objects[indexes[j-1]].compareTo(B) > 0)) {
          149.             indexes[j] = indexes[j-1];
          150.             j--;
          151.         }
          152.         indexes[j] = i;
          153.     }
          154.     return indexes;
          155.   }

          156.   /**
          157.    * 插入排序法排序。
          158.    * @param objects 排序?qū)ο?/FONT>
          159.    * @param key 排序關(guān)鍵字
          160.    * @return 按照升序排序后應(yīng)該有的索引數(shù)組
          161.    * @since  0.6
          162.    */
          163.   public static int[] insertionSort(PropertyComparable[] objects, int key) {
          164.     int length = objects.length;
          165.     int[] indexes = ArrayUtil.getInitedIntArray(length);
          166.     for (int i = 1; i < length; i++) {
          167.         int j = i;
          168.         Comparable B = objects[indexes[i]];
          169.         while ((j > 0) && (objects[indexes[j-1]].compareTo(B,key) > 0)) {
          170.             indexes[j] = indexes[j-1];
          171.             j--;
          172.         }
          173.         indexes[j] = i;
          174.     }
          175.     return indexes;
          176.   }

          177.   /**
          178.    * 選擇排序法排序。
          179.    * @param objects 排序?qū)ο?/FONT>
          180.    * @return 按照升序排序后應(yīng)該有的索引數(shù)組
          181.    * @since  0.6
          182.    */
          183.   public static int[] selectionSort(Comparable[] objects) {
          184.     int length = objects.length;
          185.     int[] indexes = ArrayUtil.getInitedIntArray(length);
          186.     for (int i = 0; i < length; i++) {
          187.         int min = i;
          188.         int j;
          189.         //在未排序列表里面查找最小元素
          190.         for (j = i + 1; j < length; j++) {
          191.             if (objects[indexes[j]].compareTo(objects[indexes[min]]) <0 ) {
          192.                 min = j;
          193.             }
          194.         }
          195.         //將最小的元素交換到未排序元素的最開(kāi)始
          196.         swap(indexes,i,min);
          197.     }
          198.     return indexes;
          199.   }

          200.   /**
          201.    * 選擇排序法排序。
          202.    * @param objects 排序?qū)ο?/FONT>
          203.    * @param key 排序關(guān)鍵字
          204.    * @return 按照升序排序后應(yīng)該有的索引數(shù)組
          205.    * @since  0.6
          206.    */
          207.   public static int[] selectionSort(PropertyComparable[] objects, int key) {
          208.     int length = objects.length;
          209.     int[] indexes = ArrayUtil.getInitedIntArray(length);
          210.     for (int i = 0; i < length; i++) {
          211.         int min = i;
          212.         int j;
          213.         //在未排序列表里面查找最小元素
          214.         for (j = i + 1; j < length; j++) {
          215.             if (objects[indexes[j]].compareTo(objects[indexes[min]],key) <0 ) {
          216.                 min = j;
          217.             }
          218.         }
          219.         //將最小的元素交換到未排序元素的最開(kāi)始
          220.         swap(indexes,i,min);
          221.     }
          222.     return indexes;
          223.   }

          224.   /**
          225.    * 雙向冒泡排序法排序。
          226.    * @param objects 排序?qū)ο?/FONT>
          227.    * @return 按照升序排序后應(yīng)該有的索引數(shù)組
          228.    * @since  0.6
          229.    */
          230.   public static int[] bidirectionalBubbleSort(Comparable[] objects) {
          231.     int length = objects.length;
          232.     int[] indexes = ArrayUtil.getInitedIntArray(length);
          233.     int j;
          234.     int limit = objects.length;
          235.     int start = -1;
          236.     while (start < limit) {
          237.         start++;
          238.         limit--;
          239.         for (j = start; j < limit; j++) {
          240.             if (objects[indexes[j]].compareTo(objects[indexes[j+1]]) > 0) {
          241.               swap(indexes,j,j+1);
          242.             }
          243.         }
          244.         for (j = limit; --j >= start;) {
          245.           if (objects[indexes[j]].compareTo(objects[indexes[j+1]]) > 0) {
          246.             swap(indexes,j,j+1);
          247.           }
          248.         }
          249.     }
          250.     return indexes;
          251.   }

          252.   /**
          253.    * 雙向冒泡排序法排序。
          254.    * @param objects 排序?qū)ο?/FONT>
          255.    * @param key 排序關(guān)鍵字
          256.    * @return 按照升序排序后應(yīng)該有的索引數(shù)組
          257.    * @since  0.6
          258.    */
          259.   public static int[] bidirectionalBubbleSort(PropertyComparable[] objects, int key) {
          260.     int length = objects.length;
          261.     int[] indexes = ArrayUtil.getInitedIntArray(length);
          262.     int j;
          263.     int limit = objects.length;
          264.     int start = -1;
          265.     while (start < limit) {
          266.         start++;
          267.         limit--;
          268.         for (j = start; j < limit; j++) {
          269.             if (objects[indexes[j]].compareTo(objects[indexes[j+1]]) > 0) {
          270.               swap(indexes,j,j+1);
          271.             }
          272.         }
          273.         for (j = limit; --j >= start;) {
          274.           if (objects[indexes[j]].compareTo(objects[indexes[j+1]],key) > 0) {
          275.             swap(indexes,j,j+1);
          276.           }
          277.         }
          278.     }
          279.     return indexes;
          280.   }

          281.   /**
          282.    * 交換兩個(gè)元素的值。
          283.    * @param indexes 原索引數(shù)組
          284.    * @param i 第一行
          285.    * @param j 第二行
          286.    */
          287.   private static void swap(int[] indexes, int i, int j) {
          288.     int tmp = indexes[i];
          289.     indexes[i] = indexes[j];
          290.     indexes[j] = tmp;
          291.   }

          292. }
          293. ------------------------------------------
          294. 冒泡排序:
          295. 1、比較相鄰的兩個(gè)元素,如果后面的比前面小,就對(duì)調(diào)二者。反復(fù)比較,到最后兩個(gè)元素。結(jié)果,最大值就跑到了最末位置。

          296. 2、反復(fù)第一步,直到所有較大值都跑到靠后的位置。

          297. ---------------------------------------------

          298. 選擇排序

          299. 1、一開(kāi)始整個(gè)數(shù)列是未排列的

          300. 2、從未排列的數(shù)中,挑選出最小的數(shù),和未排列的數(shù)中的第一個(gè)元素互調(diào),并將該最小的數(shù)歸類到已排序的序列中;

          301. 3、重復(fù)第2步,直到所有的數(shù)都?xì)w類到已排序數(shù)列中。

          302. ---------------------------------------------

          303. 插入排序法:

          304. 1、一開(kāi)始只有第一個(gè)數(shù)在已排序數(shù)列中,其他的數(shù)歸類到未排序數(shù)列中;

          305. 2、將未排序的第一個(gè)數(shù),插入到已排序數(shù)列中,使得插入后的已排序數(shù)列仍然維持由小到大的順序;

          306. 3、重復(fù)步驟2,直到所有的數(shù)都在已排序數(shù)列中。

          307. -----------------------------------------------

          主站蜘蛛池模板: 开封市| 河北省| 衡阳县| 泗洪县| 张掖市| 桑植县| 城步| 和平县| 讷河市| 勐海县| 林口县| 郧西县| 基隆市| 伊金霍洛旗| 常熟市| 胶南市| 商丘市| 资溪县| 灵宝市| 衡山县| 宜兴市| 永康市| 平陆县| 昔阳县| 清原| 花莲县| 千阳县| 浦县| 彭泽县| 黄山市| 平罗县| 衡南县| 台东市| 淅川县| 中超| 盱眙县| 剑阁县| 米脂县| 大化| 常熟市| 沙洋县|