A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 麦子 于 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毫秒
//******************************************************************************

评分

参与人数 1技术分 +1 收起 理由
刘凯 + 1 赞一个!

查看全部评分

8 个回复

正序浏览
感谢分享   
回复 使用道具 举报
感谢分享!!!
回复 使用道具 举报
学习一下。谢谢分享。
回复 使用道具 举报
不错不错,赞一个
回复 使用道具 举报
学习了,哈哈
回复 使用道具 举报
看起来  代码越多 效率越好啊    赞啊
回复 使用道具 举报
堆排序看着有点晕{:soso_e134:}
回复 使用道具 举报
哥们!太给力了……
不过,这代码写的有点****,函数体里没必要写那么多重复的,将数组中元素交换可以单独写一个函数
  1. private static void swap(int[] arr,int a,int b)                        //
  2.         {
  3.                 int temp=arr[a];
  4.                 arr[a]=arr[b];
  5.                 arr[b]=temp;
  6.         }
复制代码
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马