文档章节

六个排序算法

奋斗到天明
 奋斗到天明
发布于 2016/05/12 10:55
字数 1559
阅读 40
收藏 7
点赞 2
评论 0

排序算法

这是一共列表六个算法,冒泡,选择,插入,归并,希尔,快速,此外还有快速排序中枢选择不同的算法。

冒泡排序

最简单的排序方法了,从第一个元素循环到最后一个元素。对比相邻元素,前者小于后者时,交换两者,结果是让最后一个元素为最小值。重复这个动作,让无序部分中的最小者慢慢到无序部分的最后面。从而让整个数组从大到小排序。
效率上来说,平均情况是$O(N^2)$,最坏的情况也是$O(N^2)$

private static void pop(int[] array){
    for (int i = 0; i < array.length; i++) {
        for (int j = 0; j < array.length - i - 1; j++) {
            if(array[j] < array[j + 1]){
                swap(j + 1, j, array);
            }
        }
    }
}

选择排序

也是比较简单的排序方法,从第一个元素循环到最后一个元素。对比第一个元素与循环中下标元素,前者小于后者时,交换两者,结果是让第一个元素为最大值。用第二个,第三个,第N个重复这个动作,从无序部分挑出最大的元素,慢慢让整个数组从大到小排序。
效率上来说,平均情况是$O(N^2)$,最坏的情况也是$O(N^2)$

private static void select(int[] array){
    for (int i = 0; i < array.length; i++) {
        for (int j = i; j < array.length; j++) {
            if(array[i] < array[j]){
                swap(j, i, array);
            }
        }
    }
}

插入排序

插入排序比之前两个有难度。对于某个元素他假设左边所有元素都是有序的。现将该元素从右到左和有序部分每个元素对比,插入到他们之中的合适位置,让有序部分依 然有序。依次从无序部分中拿过一个元素插入到有序部分。最后整个数组都成了有序数组。
效率上来说,平均情况是$O(N^2)$,最坏的情况也是$O(N^2)$

private static void insert(int[] array){
    for (int i = 0; i < array.length; i++) {
        for (int j = i; j > 0; j--) {
            if(array[j - 1] < array[j]){
                swap(j - 1, j, array);
            }
        }
    }
}

归并排序

归并排序利用了递归原理。将数组分为两部分,然后让分别让这两部分有序,最后合并这两部分。这是大体逻辑,需要递归的是分别让这两部分有序,让他们再分再分……再分,最后只有一个元素时,就不再分,让递归外层的去合并,合并合并……合并。当整个数组合并时,他们都有序了。
效率上来说,平均情况是$O(NLogN)$,最坏的情况也是$O(NLogN)$,但是他需要额外的空间。

private static void merge(int[] array){
    int[] temp = new int[array.length];
    mergeCore(0, array.length - 1, temp, array);
}

private static void mergeCore(int left, int right, int[] temp, int[] array) {
    if(left == right){
        return;
    }else{
        int mid = (left + right) / 2;

        mergeCore(left, mid, temp, array);
        mergeCore(mid + 1, right, temp, array);

        mergeTogether(left, mid, right, temp, array);
    }
}

private static void mergeTogether(int left, int mid, int right, int[] temp, int[] array) {
    int curTemp = 0;
    int curLeft = left;
    int curRight = mid + 1;
    int size = right - left;
    while(curLeft <= mid && curRight <= right){
        if(array[curLeft] >= array[curRight]){
            temp[curTemp++] = array[curLeft++];
        }else{
            temp[curTemp++] = array[curRight++];
        }
    }

    while(curLeft <= mid){
        temp[curTemp++] = array[curLeft++];
    }

    while(curRight <= right){
        temp[curTemp++] = array[curRight++];
    }

    for (int i = 0; i <= size; i++) {
        array[left++] = temp[i];
    }
}

希尔排序

算是插入排序的变种,在插入排序中如果整个数组都是倒序,那么效率就很低下。而希尔排序是将有许部分,按间隔分组。如原来是1-2-3-4-5-6……,而希尔排序是分为两组1-3-5,2-4-5。分别进行插入排序,这样交换的次数会减少。然后慢慢减小间隔,再次排序,最后当间隔是1时,希尔排序就退化成插入排序了。这个过程中,每个元素会逐渐靠近合适的位置。
目前最合理间隔的算法是$n=(n-1)/3$
效率上来说,平均情况是$O(N^{3/2})$,最坏的情况也是$O(N^{3/2})$

private static void shell(int[] array){
    int salt = 1;
    while(salt < array.length / 3){
        salt = salt * 3 + 1;
    }

    while(salt > 0){
        for (int i = salt; i < array.length; i++) {
            for (int j = i ; j > salt - 1; j = j - salt) {
                int t;
                if(array[j - salt] < array[j]){
                    swap(j - salt, j, array);
                }
            }

        }
        salt = (salt - 1)/3;
    }
}

快速排序

六种中最快速的排序了。取无序数组中的一个元素为枢纽。然后让所有的元素与之相比,大于的放一边,小于的放一边。中间放该元素。将两边再次重复这个步骤,直到只剩下一个元素,这样再回归。最后所有元素都有序了。
这里取的是枢纽元素是最后面的元素。
效率上来说,平均情况是$O(N*LogN)$,最坏的情况是$O(N²)$

private static void fast(int[] array){
    fastCort(0, array.length - 1, array);
}

private static int calcMid(int left, int right, int[] array) {
    int mid = (left + right)/2;
    if(array[left] < array[mid]){
        swap(left, mid, array);
    }
    if(array[left] < array[right]){
        swap(left, right, array);
    }
    if(array[mid] < array[right]){
        swap(mid, right, array);
    }
    swap(mid,right - 1, array);
    return 0;
}

private static void fastCort(int left, int right, int[] array) {
    if(left < right){
        int pivot = array[right];
        int border = findBorder(left, right, pivot, array);
        fastCort(left, border - 1, array);
        fastCort(border + 1, right, array);
    }else{
        return;
    }
}

private static int findBorder(int left, int right, int pivot, int[] array) {
    int curLeft = left - 1;
    int curRight = right;
    while(true){
        while(array[++curLeft] > pivot)
            ;

        while(curRight > left && array[--curRight] < pivot)
            ;

        if(curLeft >= curRight){
            break;
        }else{
            swap(curRight, curLeft, array);
        }
    }
    swap(right, curLeft, array);

    return curLeft;

}

三项取中快速排序

与前面的原理一样,不过枢纽取是取最左边、最右边、中间。三个元素,然后排序,取值中间的元素为枢纽。再递归。

private static void fastMid(int[] array){
    fastMidCort(0, array.length - 1, array);
}

private static void fastMidCort(int left, int right, int[] array) {
    if(right - left < 3){
        lessSort(left, right, array);
    }else{
        int pivot = calcMid(left, right, array);
        int border = findBorderMid(left, right, pivot, array);
        fastMidCort(left, border - 1, array);
        fastMidCort(border + 1, right, array);
    }
}

private static int findBorderMid(int left, int right, int pivot, int[] array) {
    int curLeft = left;
    int curRight = right - 1;
    while(true){
        while (array[++left] > pivot)
            ;
        while(array[--right] < pivot)
            ;

        if(curLeft >= curRight){
            break;
        }else {
            swap(curLeft, curRight, array);
        }
    }
    swap(curLeft, right - 1, array);
    return curLeft;
}

private static void lessSort(int left, int right, int[] array) {
    if(right <= left){
        return;
    }else if(right - left < 2){
        if(array[left] < array[right]){
            swap(left, right, array);
        }
    }else{
        if(array[left] < array[left + 1]){
            swap(left, left + 1, array);
        }
        if(array[left] < array[right]){
            swap(left, right, array);
        }
        if(array[left + 1] < array[right]){
            swap(left + 1, right, array);
        }
    }
}

private static void swap(int a, int b, int[] array) {
    int t;
    t = array[b];
    array[b] = array[a];
    array[a] = t;
}

© 著作权归作者所有

共有 人打赏支持
奋斗到天明
粉丝 18
博文 112
码字总数 82707
作品 0
昌平
程序员
维基百科上的算法和数据结构链接很强大

突然发现维基百科上的算法和数据结构比百度百科强多啦,图文并茂。 其实这个网站不错:http://www.sorting-algorithms.com 冒泡排序: bubble冒泡的意思 http://zh.wikipedia.org/wiki/%E5%8...

晨曦之光 ⋅ 2012/03/09 ⋅ 1

Rxjs实践-各种排序算法排序过程的可视化展示

这几天学习下《算法》的排序章节,具体见对排序的总结,想着做点东西,能将各种排序算法的排序过程使用Rxjs通过可视化的方式展示出来,正好练系一下Rxjs的使用 本文不会太多介绍Rxjs的基本概念...

xiyuyizhi ⋅ 2017/10/27 ⋅ 0

经典排序之 冒泡排序

Author: bakari Date: 2012.7.30 排序算法有很多种,每一种在不同的情况下都占有一席之地。关于排序算法我分“经典排序之”系列分别述之。本篇为冒泡排序。 冒泡排序是最古老的排序,我们最早...

chambai ⋅ 2012/08/11 ⋅ 0

字符串排序----排序算法的选择

对字符串的排序可以使用前面的通用排序算法,但有些专用的字符串排序算法将比通用排序算法效率更高,它们突破了NlogN的时间下界。 算法 是否稳定 原地排序 运行时间 额外空间 优势领域 低位优...

Superheros ⋅ 01/24 ⋅ 0

排序算法-09-冒泡排序(Bubble Sort)

Basics Sorting - 基础排序算法 算法复习——排序 算法分析 时间复杂度-执行时间(比较和交换次数) 空间复杂度-所消耗的额外内存空间 使用小堆栈或表 使用链表或指针、数组索引来代表数据 排序...

Corwien ⋅ 2016/06/17 ⋅ 0

Java实现几种常见排序方法(下)

插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。其具体步骤参见代码及注释。 /** 插入排序<br/> <ul> <li>从第一个元素开始,该元...

晨曦之光 ⋅ 2012/03/09 ⋅ 0

排序(sort)

1、定义 排序 所谓排序,就是要整理文件中的记录,使之按关键字递增(或递减)次序排列起来。其确切定义如下: 输入:n个记录R1,R2,…,Rn,其相应的关键字分别为K1,K2,…,Kn。 输出:R...

野渡书生 ⋅ 2016/04/29 ⋅ 0

输入排序算法的名字与待排序的数据列可完成数据排序?

拜托各位大神了 1.通过程序实现排序算法,算法支持冒泡排序、插入排序、希尔选择,且可扩展算法。只需要输入排序算法的名字与待排序的数据列表即可完成数据排序; 三个算法的代码写出来了,后...

禧禧的禧 ⋅ 2014/06/07 ⋅ 0

线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

1、概述 在之前的一篇文章《线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)》中,我们使用了fork/join框架提高归并排序的性 能。那篇文章发布后,有的读者联系我,觉得单就归...

yinwenjie ⋅ 2017/06/06 ⋅ 0

排序算法比较(时空复杂度,稳定性)

特别说明: 排序算法稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,ri=rj,且ri在rj之前,而在排序后的序列中...

Taisuke ⋅ 2014/06/10 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

idea 整合 vue 启动

刚学习Vue 搭建了一个项目 只能命令启动 Idea里面不会启动 尝试了一下修改启动的配置 如下: 1.首先你要保证你的package.json没有修改过 具体原因没有看 因为我改了这个name的值 就没办法启动...

事儿爹 ⋅ 25分钟前 ⋅ 0

数据仓库技术概述(一看就是架构师写的,对我极其有用)

ETL,是英文 Extract-Transform-Load 的缩写,用来描述将数据从来源端经过抽取(extract)、交互转换(transform)、加载(load)至目的端的过程。ETL一词较常用在数据仓库,但其对象并不限于...

gulf ⋅ 26分钟前 ⋅ 0

redis在windows环境的后台运行方法

在后台运行,首先需要安装redis服务,命令为 redis-server.exe --service-install redis.windows.conf --loglevel verbose 启动,命令为 redis-server --service-start 停止,命令为 redis-...

程序羊 ⋅ 28分钟前 ⋅ 0

比特币现金开发者提出新的交易订单规则

本周,四位比特币现金的四位开发者和研究员:Joannes Vermorel(Lokad),AmaurySéchet(比特币ABC),Shammah Chancellor(比特币ABC)和Tomas van der Wansem(Bitcrust)共同发表了一篇关...

lpy411 ⋅ 32分钟前 ⋅ 0

vue获取input输入框的数据

用惯了jQuery,突然使用vue感觉很不习惯,有很多不同的地方,感觉是两个不同的思想来写前端的代码。jQuery是使用选择器($)选取DOM对象,对其进行赋值、取值、事件绑定等操作。而Vue则是通过...

王子城 ⋅ 34分钟前 ⋅ 0

竟然这就是面向对象的游戏设计?!

从程序角度考虑,许多 JavaScript 都基于循环和大量的 if/else 语句。在本文中,我们可了解一种更聪明的做法 — 在 JavaScript 游戏中使用面向对象来设计。本文将概述原型继承和使用 JavaSc...

柳猫 ⋅ 39分钟前 ⋅ 2

git cmd git bash

刚用到了Git,看到windows环境下有两个命令输入窗口 第一个是可视化图形界面,第二个是CMD,第三个是Bash。 Git中的Bash是基于CMD的,在CMD的基础上增添一些新的命令与功能。所以建议在使用的...

东东笔记 ⋅ 41分钟前 ⋅ 0

分布式系统CAP和Base

1、分布式系统 1.1 简介 由多台计算机和通信的软件组件通过计算机网络连接(本地网络或广域网)组成。分布式系统是建立在网络之上的软件系统。正是因为软件的特性,所以分布式系统具有高度的...

xixingzhe ⋅ 52分钟前 ⋅ 0

查看磁盘占用情况

记一次jenkins构建失败的问题 Build step 'Send build artifacts over SSH' changed build result to UNSTABLE 网上查资料都没明确表明是什么错,回忆之前处理这样的问题。第一时间想到的是不...

ManderSF ⋅ 54分钟前 ⋅ 0

数据库管理提速:SQL解析的探索与应用

前言: SQL解析是一项复杂的技术,一般都是由数据库厂商来掌握,当然也有公司专门提供SQL解析的API。SQL解析与优化是属于编译器范畴,和C语言等其他语言的解析没有本质的区别。其中分为词法分...

java高级架构牛人 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部