文档章节

排序算法比较

f
 fang_faye
发布于 2017/08/10 13:52
字数 1559
阅读 3
收藏 0

1、二分查找排序

二分查找排序:在直接插入方法的上加入分治的思想

public class SortInHalf {

    public static void main(String[] args) {
        int[] arrays = {12,3,45,6,1,34,2,5,8};
        HalfSort(arrays);
    }
    /**
     * 二分查找排序方法
     * @param arrays
     */
    public static void HalfSort(int[] arrays) {
        int sign = 1;
        int start = 0;
        int end = 0;
        int half = 0;
        int tempint = 0;
        while(sign<arrays.length) {
            start = 0;
            end = sign-1;
            tempint = arrays[sign];
            while(start<=end) {
                half = (start+end)/2;
                if(tempint>=arrays[half]) {
                    start = half+1;
                }else {
                    end = half-1;
                }
            }
            Move(arrays, sign, start);
            PrintoutForASort(arrays,sign);
            sign++;
        }
    }
    /**
     * 将数组从sign-1位置开始,以此向后挪动一位
     * @param arrays
     * @param sign
     * @param target
     */
    public static void Move(int[] arrays,int sign,int target) {
        int x = arrays[sign];
        for(int i=sign-1;i>=target;i--) {
            arrays[i+1]=arrays[i];
        }
        arrays[target]=x;
    }
    /**
     * 输出数组内容
     * @param arrays
     * @param sign
     */
    public static void PrintoutForASort(int[] arrays,int sign) {
        System.out.print("第"+sign+"次排序结果:");
        for(int i=0;i<arrays.length;i++) {
            System.out.print(arrays[i]+",");
        }
        System.out.println();
    }
}
输出:

第1次排序结果:3,12,45,6,1,34,2,5,8,
第2次排序结果:3,12,45,6,1,34,2,5,8,
第3次排序结果:3,6,12,45,1,34,2,5,8,
第4次排序结果:1,3,6,12,45,34,2,5,8,
第5次排序结果:1,3,6,12,34,45,2,5,8,
第6次排序结果:1,2,3,6,12,34,45,5,8,
第7次排序结果:1,2,3,5,6,12,34,45,8,
第8次排序结果:1,2,3,5,6,8,12,34,45,

2、快速排序

public class SortInQuick {
    private static int sign = 1;
    public static void main(String[] args) {
        int[] arrays = {12,3,45,6,1,34,2,5,8};
        int start = 0;
        int end = arrays.length-1;
        quicksort(arrays, start, end);
    }
    /**
     * 快速排序
     * @param arrays
     * @param start
     * @param end
     */
    public static void quicksort(int[] arrays, int start, int end) {
        if(start>end) {return;}
        int signi = start;
        int signj = end;
        int target = arrays[start];
        while(signi<signj) {
            while(arrays[signj]>=target&&signi<signj) {
                signj--;
            }
            while (arrays[signi]<=target&&signi<signj) {
                signi++;
            }
            if(signi<signj) {
                exchange(arrays, signi, signj);
            }
        }

        exchange(arrays, start, signi);
        PrintoutForASort(arrays);
        quicksort(arrays, signi+1, end);
        quicksort(arrays, start, signi-1);
    }
    /**
     * 交换数组arrays中位置i和j的内容
     * @param arrays
     * @param i
     * @param j
     */
    public static void exchange(int[] arrays, int i, int j) {
        int temp = 0;
        temp = arrays[i];
        arrays[i] = arrays[j];
        arrays[j] = temp;
    }
    
    /**
     * 输出数组内容
     * @param arrays
     * @param sign
     */
    public static void PrintoutForASort(int[] arrays) {
        System.out.print("第"+sign+"次排序结果:");
        for(int i=0;i<arrays.length;i++) {
            System.out.print(arrays[i]+",");
        }
        System.out.println();
        sign++;
    }
}
输出结果:

第1次排序结果:8,3,5,6,1,2,12,34,45,
第2次排序结果:8,3,5,6,1,2,12,34,45,
第3次排序结果:8,3,5,6,1,2,12,34,45,
第4次排序结果:2,3,5,6,1,8,12,34,45,
第5次排序结果:1,2,5,6,3,8,12,34,45,
第6次排序结果:1,2,3,5,6,8,12,34,45,
第7次排序结果:1,2,3,5,6,8,12,34,45,
第8次排序结果:1,2,3,5,6,8,12,34,45,
第9次排序结果:1,2,3,5,6,8,12,34,45,

3、归并排序
public class SortInMerger {

    private static int sign = 0;
    public static void main(String[] args) {
        int[] arrays = {12,3,45,6,1,34,2,5,8};
        int start = 0;
        int end = arrays.length-1;
        merge(arrays, start, end);
    }

    /**
     * 将一个序列递归划分为最小单元,再进行排序
     * 当一个序列只有0个或者1个元素时便可认为是有序序列
     * @param arrays
     */
    public static void merge(int[] arrays, int start, int end) {
        if(start>=end) {return;}
        int mid = (start+end)/2;
        merge(arrays, start, mid);
        merge(arrays, mid+1, end);
        mergesort(arrays, start, mid, end);
        PrintoutForASort(arrays);
    }
    
    /**
     * 对划分后的两个有序序列进行归并排序
     * @param arrays
     * @param start
     * @param mid
     * @param end
     */
    public static void mergesort(int[] arrays, int start, int mid, int end) {
        if(start>=end) {
            return;
        }
        int i = 0;
        int j = 0;
        int k = start;
        int[] temparrays = new int[arrays.length];
        for(i=start;i<=end;i++) {
            temparrays[j]=arrays[i];
            j++;
        }
        j = mid - start + 1;
        i = 0;
        while(i<=mid-start&&j<=end-start) {
            if(temparrays[i]<=temparrays[j]) {
                arrays[k] = temparrays[i];
                i++;
            }else {
                arrays[k] = temparrays[j];
                j++;
            }
            k++;
        }
        while(i<=mid-start) {
            arrays[k] = temparrays[i];
            i++;
            k++;
        }
        while(j<=end-start) {
            arrays[k] = temparrays[j];
            j++;
            k++;
        }
    }
    
    /**
     * 输出数组内容
     * @param arrays
     */
    public static void PrintoutForASort(int[] arrays) {
        System.out.print("第"+sign+"次排序结果:");
        for(int i=0;i<arrays.length;i++) {
            System.out.print(arrays[i]+",");
        }
        System.out.println();
        sign++;
    }
}
输出结果:

第0次排序结果:3,12,45,6,1,34,2,5,8,
第1次排序结果:3,12,45,6,1,34,2,5,8,
第2次排序结果:3,12,45,1,6,34,2,5,8,
第3次排序结果:1,3,6,12,45,34,2,5,8,
第4次排序结果:1,3,6,12,45,2,34,5,8,
第5次排序结果:1,3,6,12,45,2,34,5,8,
第6次排序结果:1,3,6,12,45,2,5,8,34,
第7次排序结果:1,2,3,5,6,8,12,34,45,

4、三种方法时间消耗对比

第一次运行结果:

二分查找排序需要的时间:16
快速排序需要的时间:0
归并排序需要的时间:0

第二次运行结果:

二分查找排序需要的时间:0
快速排序需要的时间:0
归并排序需要的时间:16

第三次运行结果:

二分查找排序需要的时间:0
快速排序需要的时间:0
归并排序需要的时间:15

ps:每次运行消耗的时间都不同~所以以上结果仅做参考
---------------------------分割线,再更新---------------------------

四、堆排序(大顶堆)

public class SortInHeap {
    private static int sign = 1;
    public static void main(String[] args) {
        int[] arrays = {12,3,45,6,1,34,2,5,8};
        heapsort(arrays);
    }
    /**
     * 堆排序过程
     * @param arrays
     */
    public static void heapsort(int[] arrays) {
        int range = arrays.length-1;
        for(;range>=0;range--) {
            adjust(arrays, range);
            exchange(arrays, range, 0);
            PrintoutForASort(arrays);
        }
    }
    /**
     * 大顶堆调整过程
     * @param arrays
     * @param range
     */
    public static void adjust(int[] arrays, int range) {
        int startadjust = (range-1)/2;
        for(;startadjust>=0;startadjust--) {
            if(arrays[startadjust*2+2]>arrays[startadjust]&&startadjust*2+2<=range) {
                exchange(arrays, startadjust*2+2, startadjust);
            }
            if (arrays[startadjust*2 + 1] > arrays[startadjust]&&startadjust*2+1<=range) {
                exchange(arrays, startadjust * 2 + 1, startadjust);
            }
        }
    }
    /**
     * 交换数组arrays中位置i和j的内容
     * @param arrays
     * @param i
     * @param j
     */
    public static void exchange(int[] arrays, int i, int j) {
        int temp = 0;
        temp = arrays[i];
        arrays[i] = arrays[j];
        arrays[j] = temp;
    }
    /**
     * 输出数组内容
     * @param arrays
     */
    public static void PrintoutForASort(int[] arrays) {
        System.out.print("第"+sign+"次排序结果:");
        for(int i=0;i<arrays.length;i++) {
            System.out.print(arrays[i]+",");
        }
        System.out.println();
        sign++;
    }
}

排序结果:

第1次排序结果:6,8,12,3,1,34,2,5,45,
第2次排序结果:3,8,6,5,1,12,2,34,45,
第3次排序结果:2,8,3,5,1,6,12,34,45,
第4次排序结果:3,6,2,5,1,8,12,34,45,
第5次排序结果:1,3,2,5,6,8,12,34,45,
第6次排序结果:3,2,1,5,6,8,12,34,45,
第7次排序结果:1,2,3,5,6,8,12,34,45,
第8次排序结果:1,2,3,5,6,8,12,34,45,
第9次排序结果:1,2,3,5,6,8,12,34,45,

堆排序和快速排序对比(知乎-邓毅):

平均时间上,堆排序的时间常数比快排要大一些,因此通常会慢一些,但是堆排序最差时间也是O(nlogn)的,这点比快排好。
快排在递归进行部分的排序的时候,只会访问局部的数据,因此缓存能够更大概率的命中;而堆排序的建堆过程是整个数组各个位置都访问到的,后面则是所有未排序数据各个位置都可能访问到的,所以不利于缓存发挥作用。简答的说就是快排的存取模型的局部性(locality)更强,堆排序差一些。
速度和缓存的问题都反映了堆排序让数据过于大距离的移动,你观察某个元素在整个排序过程中的移动过程,会发现它是前后大幅度的跑动;而快速排序则是尽快的移动到最终的位置,然后做小范围的跳动。

© 著作权归作者所有

f
粉丝 6
博文 150
码字总数 44609
作品 0
崇明
其他
私信 提问

暂无文章

OSChina 周六乱弹 —— 早上儿子问我他是怎么来的

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @凉小生 :#今日歌曲推荐# 少点戾气,愿你和这个世界温柔以待。中岛美嘉的单曲《僕が死のうと思ったのは (曾经我也想过一了百了)》 《僕が死の...

小小编辑
今天
1K
12
Excption与Error包结构,OOM 你遇到过哪些情况,SOF 你遇到过哪些情况

Throwable 是 Java 中所有错误与异常的超类,Throwable 包含两个子类,Error 与 Exception 。用于指示发生了异常情况。 Java 抛出的 Throwable 可以分成三种类型。 被检查异常(checked Exc...

Garphy
今天
23
0
计算机实现原理专题--二进制减法器(二)

在计算机实现原理专题--二进制减法器(一)中说明了基本原理,现准备说明如何来实现。 首先第一步255-b运算相当于对b进行按位取反,因此可将8个非门组成如下图的形式: 由于每次做减法时,我...

FAT_mt
昨天
19
0
好程序员大数据学习路线分享函数+map映射+元祖

好程序员大数据学习路线分享函数+map映射+元祖,大数据各个平台上的语言实现 hadoop 由java实现,2003年至今,三大块:数据处理,数据存储,数据计算 存储: hbase --> 数据成表 处理: hive --> 数...

好程序员官方
昨天
32
0
tabel 中含有复选框的列 数据理解

1、el-ui中实现某一列为复选框 实现多选非常简单: 手动添加一个el-table-column,设type属性为selction即可; 2、@selection-change事件:选项发生勾选状态变化时触发该事件 <el-table @sel...

everthing
昨天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部