文档章节

六个排序算法

奋斗到天明
 奋斗到天明
发布于 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
排序(上):冒泡排序、插入排序和选择排序

如何分析一个排序算法? 分析一个排序算法的三要素:排序算法的执行效率、排序算法的内存消耗以及排序算法的稳定性。 排序算法的执行效率 对于排序算法执行效率的分析,一般是从以下三个方面...

hardyyao
2018/11/04
0
0
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

没有更多内容

加载失败,请刷新页面

加载更多

Go 示例测试实现原理剖析

简介 示例测试相对于单元测试和性能测试来说,其实现机制比较简单。它没有复杂的数据结构,也不需要额外的流程控制,其核心工作原理在于收集测试过程中的打印日志,然后与期望字符串做比较,...

恋恋美食
15分钟前
0
0
org.apache.commons.lang 时间格式化或者时间字符串转date

一直觉得 org.apache.commons.lang 包的时间 操作挺不好用的,但是一般都有这个工具包 例子: System.out.println(DateFormatUtils.format(new Date(), "yyyy-MM-dd"));        Sys......

之渊
16分钟前
0
0
jdk11 HttpClient 爬虫

目的: 获得目标背单词网站中的单词, 写了一个简单的小爬虫, 使用jdk11 到此, 思路明确! 第一步, 把冰箱门...., 串词了,Sorry!! 第一步, 调用登陆接口, 拿到sessionid! 第二步, 带着sessionid...

GOToo
32分钟前
6
0
matlab-自控原理 taylor 泰勒展开 一、二元函数

  matlab : R2018a 64bit     OS : Windows 10 x64 typesetting : Markdown    blog : my.oschina.net/zhichengjiu    gitee : gitee.com/zhichengjiu   一元函数的泰勒展开 code c......

志成就
43分钟前
2
0
PreparedStatement批量执行sql

案例: 工具方法: public static Connection getConnection(){try {Class.forName("com.mysql.jdbc.Driver");ct = DriverManager.getConnection("jdbc:mysql://127.0.0.1:3306/......

ZeroneLove
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部