文档章节

六个排序算法

奋斗到天明
 奋斗到天明
发布于 2016/05/12 10:55
字数 1559
阅读 40
收藏 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
排序算法-09-冒泡排序(Bubble Sort)

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

Corwien
2016/06/17
41
0
Java实现几种常见排序方法(下)

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

晨曦之光
2012/03/09
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

文件的压缩与解压(linux)

Linux下*.tar.gz文件解压缩命令 1.压缩命令:   命令格式:tar -zcvf 压缩后文件名.tar.gz 被压缩文件名 可先切换到当前目录下。压缩文件名和被压缩文件名都可加入路径。 2.解压缩命令: ...

qimh
21分钟前
1
0
invalid character found in the request target 异常

这个异常时因为Tomcat 9不支持请求格式出现“{”等非法字符的问题 因为tomcat版本问题遇到的坑,记录一下。 问题 今天由于要测试一下订单详情页的异步查询,在本地起了一个服务,发送的请求是...

edwardGe
26分钟前
1
0
发现抓包软件fiddler的bug

1个请求他跳转之后,直接400,被拦在了Apache,使用fiddler 的,replay requests 是同样的结果,但是replay composer确是正常的。 也就是说这replay requests 是发原来的包,replay composer...

NLGBZJ
36分钟前
1
0
linux screen 命令详解

shell关闭后, 主机仍然运行 screen命令 启动jenkins以后, screen, 然后按ctrl+a 再按d 这样暂停了子界面, 这时候回到了父界面 用screen –ls查看目前子界面的状态 [root@free /]# screen -l...

SuShine
37分钟前
1
0
mac机器切换无线网络导致网页不能打开的问题

问题: 公司和家里使用不同的WI-FI,每次从家到公司时自动切换网络后,公司的许多地址不能访问, ping域名是可以ping同的,但是网页却打不开... 问题分析: 初步猜想是DNS缓存的问题? 对于MAC系统没...

Lennie002
39分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部