黑马程序员技术交流社区

标题: JAVA中数组排序方法?内部排序和外部排序区别及优缺点? [打印本页]

作者: 张亚青    时间: 2013-3-2 10:41
标题: JAVA中数组排序方法?内部排序和外部排序区别及优缺点?
本帖最后由 张亚青 于 2013-3-3 13:55 编辑

求高手给详细介绍下排序方法(外部排序和内部排序),以及什么时候使用外部排序或者内部排序?

PS:
  1. package com.itheima;
  2. import java.util.List;
  3. import java.util.ArrayList;
  4. import java.util.Arrays;


  5. /**
  6. *排序方法汇总。
  7. *@author 张亚青
  8. *

  9. */


  10. /**
  11. 排序有8种方法:插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序。

  12.        
  13. */
  14. public class Test3
  15. {

  16.         public static void main(String [] args)
  17.         {
  18.                 int [] arr={1,3,2,43,32,33,54,43,76,32,1,2,99,54};

  19.                 System.out.println("数组排序前:");
  20.                 printArray(arr);
  21.                 SortTools.insertSort(arr);
  22.                 System.out.println("数组排序后:");
  23.                 printArray(arr);


  24.         }


  25.         public static void printArray(int[] array)
  26.         {
  27.                 for (int i=0;i<array.length ;i++ )
  28.                 {
  29.                         System.out.print(" ");
  30.                         System.out.print(array[i]);
  31.                         if (i==array.length-1)
  32.                         {
  33.                                 System.out.println();
  34.                         }
  35.                 }
  36.         }

  37. }//Test3.class



  38. /**
  39. *排序工具类,提供一系列静态方法用于对数组进行排序。
  40. */

  41. class SortTools
  42. {
  43.         /**
  44.         *插入排序
  45.         *基本思想:在要排序的一组数中,假设前面的(n-1)[n>=2]个数已经是排好顺序的,现在要把第n个数插入到前面的有序数中,使得这n个数也是排好顺序
  46.         *的。如此反复循环,直到全部排好顺序。
  47.         */
  48.         public static void insertSort(int [] array)
  49.         {
  50.                 int temp=0;

  51.                 for (int i=1;i<array.length ;i++ )
  52.                 {
  53.                         int j=i-1;
  54.                         temp=array[i];
  55.                         for (;j>=0&&array[j]>temp;j-- )
  56.                         {
  57.                                 array[j+1]=array[j];
  58.                         }
  59.                         array[j+1]=temp;

  60.                 }

  61.         }

  62.         /**
  63.         *希尔排序
  64.         *基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的小标相差d,对每组中全部元素进行直接插入排
  65.         *序,然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序。当增量减到1时,进行直接插入排序后,排序完成。
  66.         */
  67.         public static void shellSort(int [] array)
  68.         {
  69.                 double dl=array.length;
  70.                 int temp=0;
  71.                 while (true)
  72.                 {
  73.                         dl=Math.ceil(dl/2);
  74.                         int d=(int)dl;

  75.                         for (int x=0;x<d ;x++ )
  76.                         {
  77.                                 for (int i=x+d;i<array.length ;i+=d )
  78.                                 {
  79.                                         int j=i-d;
  80.                                         temp=array[i];
  81.                                         for (;j>=0&&temp<array[j] ;j-=d )
  82.                                         {
  83.                                                 array[j+d]=array[j];
  84.                                         }
  85.                                         array[j+d]=temp;
  86.                                 }
  87.                         }

  88.                         if (d==1)
  89.                                 break;
  90.                 }
  91.         }



  92.         /**
  93.         *选择排序
  94.         *基本思想:在要排序的一组数中,选出最小的一个数与第一个位置的数交换;然后在剩下的数当中再找最小的与第二个位置的交换,如此循环到倒数第二个
  95.         *数和最后一个数比较为止。
  96.         */
  97.         public static void selectSort(int [] array)
  98.         {
  99.                 int position=0;
  100.                 for (int i=0;i<array.length ;i++ )
  101.                 {
  102.                         int j=i+1;
  103.                         position=i;
  104.                         int temp=array[i];
  105.                         for (;j<array.length ;j++ )
  106.                         {
  107.                                 if (array[j]<temp)
  108.                                 {
  109.                                         temp=array[j];
  110.                                         position=j;
  111.                                 }
  112.                         }
  113.                         array[position]=array[i];
  114.                         array[i]=temp;
  115.                 }
  116.         }
  117.        
  118.        
  119.         /**
  120.         *堆排序
  121.         *基本思想:堆排序是一种树形选择排序,是对选择排序的有效改进。
  122.         *        堆的定义如下:具有n个元素的序列(h1,h2,...,hn),当且仅当满足(hi>=h2i,hi>=2i+1)或(hi<=h2i,hi<=2i+1)(i=1,2,...,n/2)时称
  123.         *        之为堆。现在讨论满足前者条件的堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最大项(大顶堆)。完全二叉树可以很直观地表示堆的结
  124.         *        构。堆顶为根,其他为左子树、右子树。初始时要排序的数的序列看作是一颗顺序存储的二叉树,调整它们的存储顺序,使之成为一个堆,这时堆的根
  125.         *        节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。以此类推,直到只有两个节点的堆,并对它们
  126.         *        作交换,最后得到有n个节点的有序序列。从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序
  127.         *        有两个函数组成。一是键堆的渗透函数,二是反复调用渗透函数实现排序的函数。
  128.         */

  129.         public static void heapSort(int[] array)
  130.         {
  131.                 System.out.println("开始排序");
  132.                 int arrayLength=array.length;
  133.                 for (int i=0;i<arrayLength-1 ;i++ )
  134.                 {
  135.                         buildMaxHeap(array,arrayLength-1-i);
  136.                         System.out.print("->");
  137.                         swap(array,0,arrayLength-1-i);
  138.                         System.out.println((arrayLength-1-i)+"---->"+Arrays.toString(array));
  139.                 }

  140.         }

  141.         private static void swap(int[] array,int i,int j)
  142.         {
  143.                 int temp=array[i];
  144.                 array[i]=array[j];
  145.                 array[j]=temp;
  146.                 System.out.print("swap"+i+":"+j+">");
  147.                 System.out.println(Arrays.toString(array));
  148.         }

  149.         private static void buildMaxHeap(int [] array,int lastIndex)
  150.         {
  151.                 for (int i=lastIndex-2/2;i>=0 ;i-- )
  152.                 {
  153.                         int k=i;
  154.                         while (k*2+1<=lastIndex)
  155.                         {
  156.                                 int biggerIndex=2*k+1;
  157.                                 if (biggerIndex+1<lastIndex)
  158.                                 {
  159.                                         if (array[biggerIndex+1]>array[biggerIndex])
  160.                                         {
  161.                                                 biggerIndex++;
  162.                                         }
  163.                                 }

  164.                                 if (array[k]<array[biggerIndex])
  165.                                 {
  166.                                        
  167.                                         swap(array,k,biggerIndex);
  168.                                         k=biggerIndex;
  169.                                 }else{
  170.                                         break;                               
  171.                                 }


  172.                         }

  173.                 }
  174.         }



  175.         /**
  176.         *冒泡排序
  177.         *基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上
  178.         *冒。即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。
  179.         */
  180.         public static void bubbleSort(int[] array)
  181.         {

  182.                 for (int i=0;i<array.length-1 ; i++)
  183.                 {
  184.                         System.out.println("("+(i+1)+")");
  185.                         for (int j=0;j<array.length-1-i ;j++ )
  186.                         {
  187.                                 if (array[j]>array[j+1])
  188.                                 {
  189.                                         swap(array,j,j+1);
  190.                                 }
  191.                         }
  192.                 }

  193.         }


  194.         /**
  195.         *快速排序
  196.         *基本思想:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准
  197.         *元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
  198.         */

  199.         public static void quickSort(int [] array)
  200.         {
  201.                 if (array.length>0)
  202.                 {
  203.                         quick(array,0,array.length-1);
  204.                 }
  205.         }

  206.         private static void quick(int[] array,int low,int high)
  207.         {
  208.                 if (low<high)
  209.                 {
  210.                         int mid=midIndex(array,low,high);
  211.                         quick(array,low,mid-1);
  212.                         quick(array,mid+1,high);
  213.                 }

  214.         }

  215.         private static int midIndex(int[] array,int low,int high)
  216.         {
  217.                 int temp=array[low];
  218.                 while (low<high)
  219.                 {
  220.                         while (low<high&&array[high]>=temp)
  221.                         {
  222.                                 high--;
  223.                         }
  224.                         array[low]=array[high];
  225.                         while (low<high&&array[low]<=temp)
  226.                         {
  227.                                 low++;
  228.                         }
  229.                         array[high]=array[low];
  230.                 }
  231.                 array[low]=temp;
  232.                 return low;
  233.         }


  234.         /**
  235.         *归并排序
  236.         *基本思想:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后
  237.         *再把有序子序列合并为整体有序序列。
  238.         */

  239.         public static void mergingSort(int[] array)
  240.         {
  241.                 if (array.length>0)
  242.                 {
  243.                         _mergingSort(array,0,array.length-1);
  244.                 }
  245.         }

  246.         private static void _mergingSort(int [] array,int left,int right)
  247.         {
  248.                 if (left<right)
  249.                 {
  250.                         int center=(left+right)/2;
  251.                         _mergingSort(array,left,center);
  252.                         _mergingSort(array,center+1,right);
  253.                         merge(array,left,center,right);
  254.                 }
  255.         }

  256.         private static void merge(int [] array,int left,int center,int right)
  257.         {
  258.                 int[] tmpArr=new int[array.length];
  259.                 int mid=center+1;
  260.                 int third=left;
  261.                 int temp=left;
  262.                 while (left<=center&&mid<=right)
  263.                 {
  264.                         if (array[left]<=array[mid])
  265.                         {
  266.                                 tmpArr[third++]=array[left++];
  267.                         }else{
  268.                                 tmpArr[third++]=array[mid++];
  269.                         }
  270.                 }

  271.                 while (mid<=right)
  272.                 {
  273.                         tmpArr[third++]=array[mid++];
  274.                 }
  275.                 while (left<=center)
  276.                 {
  277.                         tmpArr[third++]=array[left++];
  278.                 }

  279.                 while (temp<=right)
  280.                 {
  281.                         array[temp]=tmpArr[temp++];
  282.                 }
  283.         }


  284.         /**
  285.          * 基数排序
  286.          *基本思想:将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序
  287.          *一直到最高位排序完成以后,数列就变成一个有序序列。
  288.         */

  289.         public static void radixSort(int []array)
  290.         {
  291.                 int max=array[0];
  292.                 for (int i=0;i<array.length ;i++ )
  293.                 {
  294.                         if(array[i]>max)
  295.                                 max=array[i];
  296.                 }

  297.                 int time=0;
  298.                 while (max>0)
  299.                 {
  300.                         max/=10;
  301.                         time++;
  302.                 }

  303.                 List<ArrayList<Integer>> queue=new ArrayList<ArrayList<Integer>>();
  304.                 for (int i=0;i<10 ;i++ )
  305.                 {
  306.                         ArrayList<Integer> queue1=new ArrayList<Integer>();
  307.                         queue.add(queue1);
  308.                 }

  309.                 for (int i=0;i<time ;i++ )
  310.                 {
  311.                         for (int j=0;j<array.length ;j++ )
  312.                         {
  313.                                 int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
  314.                                 ArrayList<Integer> queue2=queue.get(x);
  315.                                 queue2.add(array[j]);
  316.                                 //queue.set(x,queue2);
  317.                         }
  318.                         int count=0;
  319.                         for (int k=0;k<10 ;k++ )
  320.                         {
  321.                                 while (queue.get(k).size()>0)
  322.                                 {
  323.                                         ArrayList<Integer> queue3=queue.get(k);
  324.                                         array[count]=queue3.get(0);
  325.                                         queue3.remove(0);
  326.                                         count++;
  327.                                 }
  328.                         }
  329.                 }
  330.         }
  331.        



  332. }//ArrayTools.class


复制代码

作者: 何伟    时间: 2013-3-2 12:19
内部排序就是在内存中完成的排序,比如快速,冒泡这些,而外部排序时用来处理大数据的,就是内存装不了这么多数据.必须借用硬盘,不知道这样说对不对
作者: 赵海洋    时间: 2013-3-2 12:29
内部排序和外部排序的主要区分就是是否在内存中进行排序,内部排序就是指排序的整个过程(从数据到算法再到结果等)都在内存中进行,主要的排序方法有插入排序,选择排序,快速排序,希尔排序,堆排序,归并排序等。
而外部排序是数据等信息在外存中,排序在内存进行,排序结果输出给外存,多是通过败者树算法进行归并类排序。最简单的二路归并等等。外部排序最大的效率问题就是内存外存的信息交换,频繁的访问外存会造成效率地下。
一般情况下,例如磁盘上的一组数据要进行排序,那么需要进行外部排序,因为数据在磁盘上,没有在内存中,应用主要看具体实际。
作者: Benwolf0818    时间: 2013-3-2 15:21
排序(Sorting)是计算机程序设计中的一种重要操作,他的功能是将一个数据元素(或记录)的任意序列
重新排列成一个按关键字有序的序列。
排序分为两大类:内部排序,指的是待排序记录存放在计算机随机存储器中进行的排序过程;外部排序,指的
是待排序记录的数量很大,以致内存一次不能容纳全部记录,在排序过程中尚需对外存进行访问的排序过程。
作者: 黄玉昆    时间: 2013-3-3 15:24
你的代码好长啊,为啥我写到一定字数,就不能往下写了呢?我纠结啊
作者: 曹睿翔    时间: 2013-3-3 15:32
代码真长,学数据结构时也没弄的这么详细,顶你吧
作者: 江华    时间: 2013-3-3 18:24
一会仔细看下,学习学习!
作者: 邢义敏    时间: 2013-3-3 20:41
若整个排序过程不需要访问外存便能完成,则称此类排序问题为内部排序;    反之,若参加排序的记录数量很大,整个序列的排序过程不可能在内存中完成,则称此类排序问题为外部排序。
作者: 李培根    时间: 2013-3-4 13:13
黄玉昆 发表于 2013-3-3 15:24
你的代码好长啊,为啥我写到一定字数,就不能往下写了呢?我纠结啊

你的discuz代码占了太多字符……
作者: 黄玉昆    时间: 2013-3-4 13:16
李培根 发表于 2013-3-4 13:13
你的discuz代码占了太多字符……

你是说我设置的加粗或者颜色之类的这些属性吗?




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2