本帖最后由 麦子 于 2013-6-11 22:23 编辑
package com.soke.demo7; import java.util.Date;
public class Sort {
/**
* 作者：麦子
* 功能：实现各种排序算法：冒泡排序、选择排序、堆排序
* 本文中所采用的数据结构和算法都是个人思路,可能您有更好的数据结构和算法
*/
public static void main(String[] args) {
int len=100000;
int[] arra=new int[len];int[] arrb=new int[len];
int[] arrc=new int[len];
for(int i=0;i<len;i++){
int t=(int)(Math.random()*100);
arra=t;arrb=t;arrc=t;
}
/* for(int i=0;i<arr.length;i++){
System.out.print(arr+" ");
}
System.out.println(); */
//多态的体现,都可以用一个sort对象的sort方法来处理,jvm可自行解析是哪一个对象的sort方法
/* Sort sort = new Bubble();
sort.sort(arra); */
/* Sort sort = new Selection();
sort.sort(arra); */
/* Sort sort = new Stack();
sort.sort(arra); */
Sort sort0 = new Bubble();
Date date14 = new Date();
long a14 = date14.getTime();
sort0.sort(arra);
Date date15 = new Date();
long a15 = date15.getTime();
System.out.println("冒泡排序用时:"+(a15-a14)+"毫秒");
Sort sort1 = new Selection();
Date date0 = new Date();
long a0 = date0.getTime();
sort1.sort(arra);
Date date1 = new Date();
long a1 = date1.getTime();
System.out.println("选择排序用时:"+(a1-a0)+"毫秒");
Sort sort2 = new Stack();
Date date2 = new Date();
long a2 = date2.getTime();
sort2.sort(arrb);
Date date3 = new Date();
long a3 = date3.getTime();
System.out.println("堆排序用时:"+(a3-a2)+"毫秒");
/* 本程序中如果子类中没有重载或重写打印方法时，便都可采用下面的for循环来打印，
* 由于采用的是引用传递，故arr中元素的顺序已然发生变化特别注意当上面的 len 较大时，就不要打印了，这个相当耗时
* sort.show();
sort.traverseBinaryTree();
for(int i=0;i<arr.length;i++){
System.out.print(arr+" ");
} */
}
//下面的空方法，是为了实现java语言三大特征之一的多态，多态与继承联系甚为紧密
public void sort(int arr[]){}
}
//******************************************************************************
//创建一个冒牌排序的类,让其继承父类sort
class Bubble extends Sort{
//sort方法的重写
public void sort(int arr[]){
for(int i=0;i<arr.length-1;i++){
int temp=0;
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
temp=arr[j+1];
arr[j+1]=arr[j];
arr[j]=temp;
}
}
}
}
}
//******************************************************************************
//创建一个选择排序的类,让其继承父类sort
class Selection extends Sort{
public void sort(int arr[]){
for(int i=0;i<arr.length-1;i++){
int min=arr;
int minIndex=i;
for(int j=i+1;j<arr.length;j++){
if(min>arr[j]){
min=arr[j];
minIndex=j;
}
}
arr[minIndex]=arr;
arr=min;
}
}
}
//******************************************************************************
/*堆排序涉及二叉树的知识,请自行学习.若逻辑结构采用完全二叉树，存储结构采用数组.它的思想是:
* 由于要进行升序排序，故采取大根堆的形式,第一趟是从最后一个叶结点的父结点为‘根结点’开始,
* 将这棵‘树’堆化.‘根结点’依次向前移动至根结点.后面的每趟堆化都只需从根结点向下堆化处理
* 建立完一个大根堆就把堆顶元素与堆尾元素进行交换，然后将变量n减一，这样到n等于1时，
* 整个堆就完成了从小到大的排序.这样便不需要开辟其他的内存空间给”另一个存放每次堆化得到最大数“的数组
* 所谓的大根堆就是：‘根结点’数据域的值都要大于或等于其‘子结点’数据域的值
*/
//创建一个堆排序的类,让其继承父类sort
class Stack extends Sort{
public void sort(int arr[]){
int n=arr.length;//先将数组的长度赋给一个变量n;便于后面的操作
int temp=0;//在进行交换时用到的临时变量；定义在循环外面是为了节省占用的内存资源
for(int k=n;k>2;k--)//控制外层循环次数
{ if(n==arr.length){
for(int i=(n/2-1);i>=0;i--){//控制从哪个堆的堆顶元素进行堆化处理
for(int j=i;j<=(n/2-1);){
if((2*j+2)>(n-1)){
if(j<(n/2-1)&&arr[2*j+1]>=arr[2*j+2]&&arr[2*j+1]>arr[j])
{
temp = arr[j];
arr[j] = arr[2*j+1];
arr[2*j+1] = temp;
j = 2*j+1;
}else if(j<(n/2-1)&&arr[2*j+1]<arr[2*j+2]&&arr[2*j+2]>arr[j]){
temp = arr[j];
arr[j] = arr[2*j+2];
arr[2*j+2] = temp;
j = 2*j+2;
}else if(j==(n/2-1)&&arr[2*j+1]>arr[j]){
temp = arr[j];
arr[j] = arr[2*j+1];
arr[2*j+1] = temp;
j = 2*j+1;
}else{
j = n/2;
}
}else if((2*j+2)<=(n-1)){
if(arr[2*j+1]>=arr[2*j+2]&&arr[2*j+1]>arr[j])
{
temp = arr[j];
arr[j] = arr[2*j+1];
arr[2*j+1] = temp;
j = 2*j+1;
}else if(arr[2*j+1]<arr[2*j+2]&&arr[2*j+2]>arr[j]){
temp = arr[j];
arr[j] = arr[2*j+2];
arr[2*j+2] = temp;
j = 2*j+2;
}else{
j = n/2;
}
}
}
}
}else if(n>2){ //只需从完全二叉树的根结点向下堆化处理
for(int j=0;j<=(n/2-1);){
if((2*j+2)>(n-1)){
if(j<(n/2-1)&&arr[2*j+1]>=arr[2*j+2]&&arr[2*j+1]>arr[j])
{
temp = arr[j];
arr[j] = arr[2*j+1];
arr[2*j+1] = temp;
j = 2*j+1;
}else if(j<(n/2-1)&&arr[2*j+1]<arr[2*j+2]&&arr[2*j+2]>arr[j]){
temp = arr[j];
arr[j] = arr[2*j+2];
arr[2*j+2] = temp;
j = 2*j+2;
}else if(j==(n/2-1)&&arr[2*j+1]>arr[j]){
temp = arr[j];
arr[j] = arr[2*j+1];
arr[2*j+1] = temp;
j = 2*j+1;
}else{
j = n/2;
}
}else if((2*j+2)<=(n-1)){
if(arr[2*j+1]>=arr[2*j+2]&&arr[2*j+1]>arr[j])
{
temp = arr[j];
arr[j] = arr[2*j+1];
arr[2*j+1] = temp;
j = 2*j+1;
}else if(arr[2*j+1]<arr[2*j+2]&&arr[2*j+2]>arr[j]){
temp = arr[j];
arr[j] = arr[2*j+2];
arr[2*j+2] = temp;
j = 2*j+2;
}else{
j = n/2;
}
}
}
}
//一趟堆化结束后,将根结点与堆尾元素交换
temp = arr[0];
arr[0] = arr[n-1];
arr[n-1] = temp;
n--;
}
//最后‘堆’中只剩两个元素时按下面的操作,这样就完成了对整个完全二叉树的堆化处理
//也即完成了对整个数组的升序排序
if(n==2&&arr[1]<arr[0]){
temp = arr[1];
arr[1] = arr[0];
arr[0] = temp;
}
}
}
//****************************附上某次测试时的结果******************************
//冒泡排序用时:37830毫秒
//选择排序用时:4376毫秒
//堆排序用时:64毫秒
//****************************************************************************** | 
收藏
淘帖
踩
