JAVA中数组排序方法？内部排序和外部排序区别及优缺点？

黄玉昆

本帖最后由张亚青于 2013-3-3 13:55 编辑

求高手给详细介绍下排序方法（外部排序和内部排序），以及什么时候使用外部排序或者内部排序？

PS:

package com.itheima;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;
/**
*排序方法汇总。
*@author 张亚青
*
*/
/**
排序有8种方法：插入排序、希尔排序、选择排序、堆排序、冒泡排序、快速排序、归并排序、基数排序。
*/
public class Test3
{
public static void main(String [] args)
{
int [] arr={1,3,2,43,32,33,54,43,76,32,1,2,99,54};
System.out.println("数组排序前：");
printArray(arr);
SortTools.insertSort(arr);
System.out.println("数组排序后：");
printArray(arr);
}
public static void printArray(int[] array)
{
for (int i=0;i<array.length ;i++ )
{
System.out.print(" ");
System.out.print(array[i]);
if (i==array.length-1)
{
System.out.println();
}
}
}
}//Test3.class
/**
*排序工具类，提供一系列静态方法用于对数组进行排序。
*/
class SortTools
{
/**
*插入排序
*基本思想:在要排序的一组数中，假设前面的（n-1）[n>=2]个数已经是排好顺序的，现在要把第n个数插入到前面的有序数中，使得这n个数也是排好顺序
*的。如此反复循环，直到全部排好顺序。
*/
public static void insertSort(int [] array)
{
int temp=0;
for (int i=1;i<array.length ;i++ )
{
int j=i-1;
temp=array[i];
for (;j>=0&&array[j]>temp;j-- )
{
array[j+1]=array[j];
}
array[j+1]=temp;
}
}
/**
*希尔排序
*基本思想：算法先将要排序的一组数按某个增量d（n/2，n为要排序数的个数）分成若干组，每组中记录的小标相差d，对每组中全部元素进行直接插入排
*序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。当增量减到1时，进行直接插入排序后，排序完成。
*/
public static void shellSort(int [] array)
{
double dl=array.length;
int temp=0;
while (true)
{
dl=Math.ceil(dl/2);
int d=(int)dl;
for (int x=0;x<d ;x++ )
{
for (int i=x+d;i<array.length ;i+=d )
{
int j=i-d;
temp=array[i];
for (;j>=0&&temp<array[j] ;j-=d )
{
array[j+d]=array[j];
}
array[j+d]=temp;
}
}
if (d==1)
break;
}
}
/**
*选择排序
*基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的交换，如此循环到倒数第二个
*数和最后一个数比较为止。
*/
public static void selectSort(int [] array)
{
int position=0;
for (int i=0;i<array.length ;i++ )
{
int j=i+1;
position=i;
int temp=array[i];
for (;j<array.length ;j++ )
{
if (array[j]<temp)
{
temp=array[j];
position=j;
}
}
array[position]=array[i];
array[i]=temp;
}
}
/**
*堆排序
*基本思想：堆排序是一种树形选择排序，是对选择排序的有效改进。
* 堆的定义如下：具有n个元素的序列（h1,h2,...,hn），当且仅当满足（hi>=h2i,hi>=2i+1）或（hi<=h2i,hi<=2i+1）（i=1,2,...,n/2）时称
* 之为堆。现在讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。完全二叉树可以很直观地表示堆的结
* 构。堆顶为根，其他为左子树、右子树。初始时要排序的数的序列看作是一颗顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根
* 节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面（n-1）个数重新调整使之成为堆。以此类推，直到只有两个节点的堆，并对它们
* 作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序
* 有两个函数组成。一是键堆的渗透函数，二是反复调用渗透函数实现排序的函数。
*/
public static void heapSort(int[] array)
{
System.out.println("开始排序");
int arrayLength=array.length;
for (int i=0;i<arrayLength-1 ;i++ )
{
buildMaxHeap(array,arrayLength-1-i);
System.out.print("->");
swap(array,0,arrayLength-1-i);
System.out.println((arrayLength-1-i)+"---->"+Arrays.toString(array));
}
}
private static void swap(int[] array,int i,int j)
{
int temp=array[i];
array[i]=array[j];
array[j]=temp;
System.out.print("swap"+i+":"+j+">");
System.out.println(Arrays.toString(array));
}
private static void buildMaxHeap(int [] array,int lastIndex)
{
for (int i=lastIndex-2/2;i>=0 ;i-- )
{
int k=i;
while (k*2+1<=lastIndex)
{
int biggerIndex=2*k+1;
if (biggerIndex+1<lastIndex)
{
if (array[biggerIndex+1]>array[biggerIndex])
{
biggerIndex++;
}
}
if (array[k]<array[biggerIndex])
{
swap(array,k,biggerIndex);
k=biggerIndex;
}else{
break;
}
}
}
}
/**
*冒泡排序
*基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上
*冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
*/
public static void bubbleSort(int[] array)
{
for (int i=0;i<array.length-1 ; i++)
{
System.out.println("("+(i+1)+")");
for (int j=0;j<array.length-1-i ;j++ )
{
if (array[j]>array[j+1])
{
swap(array,j,j+1);
}
}
}
}
/**
*快速排序
*基本思想：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描，将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准
*元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。
*/
public static void quickSort(int [] array)
{
if (array.length>0)
{
quick(array,0,array.length-1);
}
}
private static void quick(int[] array,int low,int high)
{
if (low<high)
{
int mid=midIndex(array,low,high);
quick(array,low,mid-1);
quick(array,mid+1,high);
}
}
private static int midIndex(int[] array,int low,int high)
{
int temp=array[low];
while (low<high)
{
while (low<high&&array[high]>=temp)
{
high--;
}
array[low]=array[high];
while (low<high&&array[low]<=temp)
{
low++;
}
array[high]=array[low];
}
array[low]=temp;
return low;
}
/**
*归并排序
*基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后
*再把有序子序列合并为整体有序序列。
*/
public static void mergingSort(int[] array)
{
if (array.length>0)
{
_mergingSort(array,0,array.length-1);
}
}
private static void _mergingSort(int [] array,int left,int right)
{
if (left<right)
{
int center=(left+right)/2;
_mergingSort(array,left,center);
_mergingSort(array,center+1,right);
merge(array,left,center,right);
}
}
private static void merge(int [] array,int left,int center,int right)
{
int[] tmpArr=new int[array.length];
int mid=center+1;
int third=left;
int temp=left;
while (left<=center&&mid<=right)
{
if (array[left]<=array[mid])
{
tmpArr[third++]=array[left++];
}else{
tmpArr[third++]=array[mid++];
}
}
while (mid<=right)
{
tmpArr[third++]=array[mid++];
}
while (left<=center)
{
tmpArr[third++]=array[left++];
}
while (temp<=right)
{
array[temp]=tmpArr[temp++];
}
}
/**
* 基数排序
*基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序
*一直到最高位排序完成以后，数列就变成一个有序序列。
*/
public static void radixSort(int []array)
{
int max=array[0];
for (int i=0;i<array.length ;i++ )
{
if(array[i]>max)
max=array[i];
}
int time=0;
while (max>0)
{
max/=10;
time++;
}
List<ArrayList<Integer>> queue=new ArrayList<ArrayList<Integer>>();
for (int i=0;i<10 ;i++ )
{
ArrayList<Integer> queue1=new ArrayList<Integer>();
queue.add(queue1);
}
for (int i=0;i<time ;i++ )
{
for (int j=0;j<array.length ;j++ )
{
int x=array[j]%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
ArrayList<Integer> queue2=queue.get(x);
queue2.add(array[j]);
//queue.set(x,queue2);
}
int count=0;
for (int k=0;k<10 ;k++ )
{
while (queue.get(k).size()>0)
{
ArrayList<Integer> queue3=queue.get(k);
array[count]=queue3.get(0);
queue3.remove(0);
count++;
}
}
}
}
}//ArrayTools.class

复制代码

何伟 · 何伟

内部排序就是在内存中完成的排序,比如快速,冒泡这些,而外部排序时用来处理大数据的,就是内存装不了这么多数据.必须借用硬盘,不知道这样说对不对

赵海洋 · 赵海洋

内部排序和外部排序的主要区分就是是否在内存中进行排序，内部排序就是指排序的整个过程（从数据到算法再到结果等）都在内存中进行，主要的排序方法有插入排序，选择排序，快速排序，希尔排序，堆排序，归并排序等。
而外部排序是数据等信息在外存中，排序在内存进行，排序结果输出给外存，多是通过败者树算法进行归并类排序。最简单的二路归并等等。外部排序最大的效率问题就是内存外存的信息交换，频繁的访问外存会造成效率地下。
一般情况下，例如磁盘上的一组数据要进行排序，那么需要进行外部排序，因为数据在磁盘上，没有在内存中，应用主要看具体实际。

Benwolf0818 · Benwolf0818

排序（Sorting）是计算机程序设计中的一种重要操作，他的功能是将一个数据元素（或记录）的任意序列
重新排列成一个按关键字有序的序列。
排序分为两大类：内部排序，指的是待排序记录存放在计算机随机存储器中进行的排序过程；外部排序，指的
是待排序记录的数量很大，以致内存一次不能容纳全部记录，在排序过程中尚需对外存进行访问的排序过程。

黄玉昆 · 黄玉昆

你的代码好长啊，为啥我写到一定字数，就不能往下写了呢？我纠结啊

曹睿翔 · 曹睿翔

代码真长，学数据结构时也没弄的这么详细，顶你吧

江华 · 江华

一会仔细看下，学习学习！

邢义敏 · 邢义敏

若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。

李培根 · 李培根

黄玉昆发表于 2013-3-3 15:24
你的代码好长啊，为啥我写到一定字数，就不能往下写了呢？我纠结啊

你的discuz代码占了太多字符……

黄玉昆 · 黄玉昆

李培根发表于 2013-3-4 13:13
你的discuz代码占了太多字符……

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

帐号		自动登录	找回密码
密码			加入黑马

JAVA中数组排序方法？内部排序和外部排序区别及优缺点？

评分

9 个回复

评分

评分

评分

黑马骑士勋章