文档章节

六个排序算法

奋斗到天明
 奋斗到天明
发布于 2016/05/12 10:55
字数 1559
阅读 41
收藏 7

排序算法

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

冒泡排序

最简单的排序方法了,从第一个元素循环到最后一个元素。对比相邻元素,前者小于后者时,交换两者,结果是让最后一个元素为最小值。重复这个动作,让无序部分中的最小者慢慢到无序部分的最后面。从而让整个数组从大到小排序。
效率上来说,平均情况是$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
2.3K
1
Rxjs实践-各种排序算法排序过程的可视化展示

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

xiyuyizhi
2017/10/27
0
0
经典排序之 冒泡排序

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

chambai
2012/08/11
0
0
Java实现几种常见排序方法(下)

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

晨曦之光
2012/03/09
0
0
排序算法-09-冒泡排序(Bubble Sort)

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

Corwien
2016/06/17
41
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周六乱弹 —— 到底谁是小公猫……

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子:分享Trivium的单曲《Throes Of Perdition》 《Throes Of Perdition》- Trivium 手机党少年们想听歌,请使劲儿戳(这里) @小鱼丁:...

小小编辑
22分钟前
13
1
基础选择器

注意:本教程参考自网上流传的李兴华老师的jquery开发框架视频,但是苦于没有相应的配套笔记,由我本人做了相应的整理. 本次学习的内容 学习jquery提供的各种选择器的使用,掌握了jquery选择...

江戸川
27分钟前
0
0
Spring中static变量不能@value注入的原因

今天本想使用@Value的方式使类中的变量获得yml文件中的配置值,然而一直失败,获得的一直为null。 类似于这样写的。 public class RedisShardedPool { private static ShardedJedisPool pool...

钟然千落
今天
2
0
CentOS7防火墙firewalld操作

firewalld Linux上新用的防火墙软件,跟iptables差不多的工具。 firewall-cmd 是 firewalld 的字符界面管理工具,firewalld是CentOS7的一大特性,最大的好处有两个:支持动态更新,不用重启服...

dingdayu
今天
1
0
关于组件化的最初步

一个工程可能会有多个版本,有国际版、国内版、还有针对各种不同的渠道化的打包版本、这个属于我们日常经常见到的打包差异化版本需求。 而对于工程的开发,比如以前的公司,分成了有三大块业...

DannyCoder
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部