`
luccs624061082
  • 浏览: 84778 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

转载的算法集锦

阅读更多
排序算法很多地方都会用到,近期又重新看了一遍算法,并自己简单地实现了一遍,特此记录下来,为以后复习留点材料。
废话不多说,下面逐一看看经典的排序算法:

1. 选择排序
选择排序的基本思想是遍历数组的过程中,以 i 代表当前需要排序的序号,则需要在剩余的 [i…n-1] 中找出其中的最小值,然后将找到的最小值与 i 指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程,所以人们形象地称之为选择排序。
举个实例来看看:
复制内容到剪贴板
代码:
初始: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]
        i = 0:  [2 , 17, 16, 16, 7, 31, 39, 32, 38 , 11] (0th [38]<->8th [2])
        i = 1:  [2, 7 , 16, 16, 17 , 31, 39, 32, 38, 11] (1st [38]<->4th [17])
        i = 2:  [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] (2nd [11]<->9th [16])
        i = 3:  [2, 7, 11, 16, 17, 31, 39, 32, 38, 16] ( 无需交换 )
        i = 4:  [2, 7, 11, 16, 16 , 31, 39, 32, 38, 17 ] (4th [17]<->9th [16])
        i = 5:  [2, 7, 11, 16, 16, 17 , 39, 32, 38, 31 ] (5th [31]<->9th [17])
        i = 6:  [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] (6th [39]<->9th [31])
        i = 7:  [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 )
        i = 8:  [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 )
        i = 9:  [2, 7, 11, 16, 16, 17, 31, 32, 38, 39] ( 无需交换 )

由例子可以看出,选择排序随着排序的进行( i 逐渐增大),比较的次数会越来越少,但是不论数组初始是否有序,选择排序都会从 i 至数组末尾进行一次选择比较,所以给定长度的数组,选择排序的比较次数是固定的: 1 + 2 + 3 + …. + n = n * (n + 1) / 2 ,而交换的次数则跟初始数组的顺序有关,如果初始数组顺序为随机,则在最坏情况下,数组元素将会交换 n 次,最好的情况下则可能 0 次(数组本身即为有序)。
由此可以推出,选择排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) (选择排序只需要一个额外空间用于数组元素交换)。
实现代码:
复制内容到剪贴板
代码:
/** 
* Selection Sorting 
*/
SELECTION(new Sortable() { 
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { 
        int len = array.length; 
        for (int i = 0; i < len; i++) { 
            int selected = i; 
            for (int j = i + 1; j < len; j++) { 
                int compare = array[j].compareTo(array[selected]); 
                if (compare != 0 && compare < 0 == ascend) { 
                    selected = j; 
                } 
            } 

            exchange(array, i, selected); 
        } 
    } 
})

2. 插入排序
插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好序,本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,为元素 x “腾位置”,最后将 k 对应的元素值赋为 x ,插入排序也是根据排序的特性来命名的。
以下是一个实例,红色 标记的数字为插入的数字,被划掉的数字是未参与此次排序的元素,红色 标记的数字与被划掉数字之间的元素为逐个向后移动的元素,比如第二趟参与排序的元素为 [11, 31, 12] ,需要插入的元素为 12 ,但是 12 当前并没有处于正确的位置,于是我们需要依次与前面的元素 31 、 11 做比较,一边比较一边移动比较过的元素,直到找到第一个比 12 小的元素 11 时停止比较,此时 31 对应的索引 1 则是 12 需要插入的位置。
复制内容到剪贴板
代码:
初始:    [11, 31, 12, 5, 34, 30, 26, 38, 36, 18]
        第一趟: [11, 31 , 12, 5, 34, 30, 26, 38, 36, 18] (无移动的元素)
        第二趟: [11, 12 , 31, 5, 34, 30, 26, 38, 36, 18] ( 31 向后移动)
        第三趟: [5 , 11, 12, 31, 34, 30, 26, 38, 36, 18] ( 11, 12, 31 皆向后移动)
        第四趟: [5, 11, 12, 31, 34 , 30, 26, 38, 36, 18] (无移动的元素)
        第五趟: [5, 11, 12, 30 , 31, 34, 26, 38, 36, 18] ( 31, 34 向后移动)
        第六趟: [5, 11, 12, 26 , 30, 31, 34, 38, 36, 18] ( 30, 31, 34 向后移动)
        第七趟: [5, 11, 12, 26, 30, 31, 34, 38 , 36, 18] (无移动的元素)
        第八趟: [5, 11, 12, 26, 30, 31, 34, 36 , 38, 18] ( 38 向后移动)
        第九趟: [5, 11, 12, 18 , 26, 30, 31, 34, 36, 38] ( 26, 30, 31, 34, 36, 38 向后移动)

插入排序会优于选择排序,理由是它在排序过程中能够利用前部分数组元素已经排好序的一个优势,有效地减少一些比较的次数,当然这种优势得看数组的初始顺序如何,最坏的情况下(给定的数组恰好为倒序)插入排序需要比较和移动的次数将会等于 1 + 2 + 3… + n = n * (n + 1) / 2 ,这种极端情况下,插入排序的效率甚至比选择排序更差。因此插入排序是一个不稳定的排序方法,插入效率与数组初始顺序息息相关。一般情况下,插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1) 。
实现代码:
复制内容到剪贴板
代码:
/** 
* Insertion Sorting 
*/
INSERTION(new Sortable() { 
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { 
        int len = array.length; 
        for (int i = 1; i < len; i++) { 
            T toInsert = array; 
            int j = i; 
            for (; j > 0; j--) { 
                int compare = array[j - 1].compareTo(toInsert); 
                if (compare == 0 || compare < 0 == ascend) { 
                    break; 
                } 
                array[j] = array[j - 1]; 
            } 

            array[j] = toInsert; 
        } 
    } 
})

3. 冒泡排序
冒泡排序可以算是最经典的排序算法了,记得小弟上学时最先接触的也就是这个算法了,因为实现方法最简单,两层 for 循环,里层循环中判断相邻两个元素是否逆序,是的话将两个元素交换,外层循环一次,就能将数组中剩下的元素中最小的元素“浮”到最前面,所以称之为冒泡排序。
照例举个简单的实例吧:
复制内容到剪贴板
代码:
初始状态:   [24, 19, 26, 39, 36, 7, 31, 29, 38, 23]
        内层第一趟: [24, 19, 26, 39, 36, 7, 31, 29, 23 , 38 ] ( 9th [23]<->8th [38 )
        内层第二趟: [24, 19, 26, 39, 36, 7, 31, 23 , 29 , 38] ( 8th [23]<->7th [29] )
        内层第三趟: [24, 19, 26, 39, 36, 7, 23 , 31 , 29, 38] ( 7th [23]<->6th [31] )
        内层第四趟: [24, 19, 26, 39, 36, 7, 23, 31, 29, 38] ( 7 、 23 都位于正确的顺序,无需交换)
        内层第五趟: [24, 19, 26, 39, 7 , 36 , 23, 31, 29, 38] ( 5th [7]<->4th [36] )
        内层第六趟: [24, 19, 26, 7 , 39 , 36, 23, 31, 29, 38] ( 4th [7]<->3rd [39] )
        内层第七趟: [24, 19, 7 , 26 , 39, 36, 23, 31, 29, 38] ( 3rd [7]<->2nd [26] )
        内层第八趟: [24, 7 , 19 , 26, 39, 36, 23, 31, 29, 38] ( 2nd [7]<->1st [19] )
        内层第九趟: [7 , 24 , 19, 26, 39, 36, 23, 31, 29, 38] ( 1st [7]<->0th [24] )
        ………
其实冒泡排序跟选择排序比较相像,比较次数一样,都为 n * (n + 1) / 2 ,但是冒泡排序在挑选最小值的过程中会进行额外的交换(冒泡排序在排序中只要发现相邻元素的顺序不对就会进行交换,与之对应的是选择排序,只会在内层循环比较结束之后根据情况决定是否进行交换),所以在我看来,选择排序属于冒泡排序的改进版。
实现代码:
复制内容到剪贴板
代码:
/** 
* Bubble Sorting, it's very similar with Insertion Sorting 
*/
BUBBLE(new Sortable() { 
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { 
        int length = array.length; 
        int lastExchangedIdx = 0; 
        for (int i = 0; i < length; i++) { 
            // mark the flag to identity whether exchange happened to false 
            boolean isExchanged = false; 
            // last compare and exchange happened before reaching index i 
            int currOrderedIdx = lastExchangedIdx > i ? lastExchangedIdx : i; 
            for (int j = length - 1; j > currOrderedIdx; j--) { 
                int compare = array[j - 1].compareTo(array[j]); 
                if (compare != 0 && compare > 0 == ascend) { 
                    exchange(array, j - 1, j); 
                    isExchanged = true; 
                    lastExchangedIdx = j; 
                } 
            } 
            // if no exchange happen means array is already in order 
            if (isExchanged == false) { 
                break; 
            } 
        } 
    } 
})
4. 希尔排序
希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”,划分为若干个小的数组,以 gap 来划分,比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ,如果以 gap = 2 来划分,可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组(对应的,如 gap = 3 ,则划分的数组为: [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] )然后分别对划分出来的数组进行插入排序,待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤,直至 gap = 1 ,即对整个数组进行插入排序,此时的数组已经基本上快排好序了,所以需要移动的元素会很小很小,解决了插入排序在处理大规模数组时较多移动次数的问题。
具体实例请参照插入排序。
希尔排序是插入排序的改进版,在数据量大的时候对效率的提升帮助很大,数据量小的时候建议直接使用插入排序就好了。
实现代码:
复制内容到剪贴板
代码:
/** 
* Shell Sorting 
*/
SHELL(new Sortable() { 
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { 
        int length = array.length; 
        int gap = 1; 

        // use the most next to length / 3 as the first gap 
        while (gap < length / 3) { 
            gap = gap * 3 + 1; 
        } 

        while (gap >= 1) { 
            for (int i = gap; i < length; i++) { 
                T next = array; 
                int j = i; 
                while (j >= gap) { 
                    int compare = array[j - gap].compareTo(next); 
                    // already find its position 
                    if (compare == 0 || compare < 0 == ascend) { 
                        break; 
                    } 

                    array[j] = array[j - gap]; 
                    j -= gap; 
                } 
                if (j != i) { 
                    array[j] = next; 
                } 
            } 
            gap /= 3; 
        } 

    } 
})


5. 归并排序
归并排序采用的是递归来实现,属于“分而治之”,将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序完毕之后再将排好序的两个数组“归并”到一起,归并排序最重要的也就是这个“归并”的过程,归并的过程中需要额外的跟需要归并的两个数组长度一致的空间,比如需要规定的数组分别为: [3, 6, 8, 11] 和 [1, 3, 12, 15] (虽然逻辑上被划为为两个数组,但实际上这些元素还是位于原来数组中的,只是通过一些 index 将其划分成两个数组,原数组为 [3, 6, 8, 11, 1, 3, 12, 15 ,我们设置三个指针 lo, mid, high 分别为 0,3,7 就可以实现逻辑上的子数组划分)那么需要的额外数组的长度为 4 + 4 = 8 。归并的过程可以简要地概括为如下:
1) 将两个子数组中的元素复制到新数组 copiedArray 中,以前面提到的例子为例,则 copiedArray = [3, 6, 8, 11, 1, 3, 12, 15] ;
2) 设置两个指针分别指向原子数组中对应的第一个元素,假定这两个指针取名为 leftIdx 和 rightIdx ,则 leftIdx = 0 (对应 copiedArray 中的第一个元素 [3] ), rightIdx = 4 (对应 copiedArray 中的第五个元素 [1] );
3) 比较 leftIdx 和 rightIdx 指向的数组元素值,选取其中较小的一个并将其值赋给原数组中对应的位置 i ,赋值完毕后分别对参与赋值的这两个索引做自增 1 操作,如果 leftIdx 或 rigthIdx 值已经达到对应数组的末尾,则余下只需要将剩下数组的元素按顺序 copy 到余下的位置即可。
下面给个归并的具体实例:
复制内容到剪贴板
代码:
第一趟: 

辅助数组 [21 , 28, 39 | 35, 38] (数组被拆分为左右两个子数组,以 | 分隔开) 

[21 ,  ,  ,  ,  ] (第一次 21 与 35 比较 , 左边子数组胜出, leftIdx = 0 , i = 0 ) 

第二趟: 

辅助数组 [21, 28 , 39 | 35, 38] 

[21 , 28,  ,  ,  ] (第二次 28 与 35 比较,左边子数组胜出, leftIdx = 1 , i = 1 ) 

第三趟: [21, 28, 39 | 35 , 38] 

[21 , 28 , 35,  ,  ] (第三次 39 与 35 比较,右边子数组胜出, rightIdx = 0 , i = 2 ) 

第四趟: [21, 28, 39 | 35, 38 ] 

[21 , 28 , 35 , 38,  ] (第四次 39 与 38 比较,右边子数组胜出, rightIdx = 1 , i = 3 ) 

第五趟: [21, 28, 39 | 35, 38] 

[21 , 28 , 35 , 38 , 39] (第五次时右边子数组已复制完,无需比较 leftIdx = 2 , i = 4 )
以上便是一次归并的过程,我们可以将整个需要排序的数组做有限次拆分(每次一分为二)直到分为长度为 1 的小数组为止,长度为 1 时数组已经不用排序了。在这之后再逆序(由于采用递归)依次对这些数组进行归并操作,直到最后一次归并长度为 n / 2 的子数组,归并完成之后数组排序也完成。
归并排序需要的额外空间是所有排序中最多的,每次归并需要与参与归并的两个数组长度之和相同个元素(为了提供辅助数组)。则可以推断归并排序的空间复杂度为 1 + 2 + 4 + … + n = n * ( n + 2) / 4 (忽略了 n 的奇偶性的判断),时间复杂度比较难估,这里小弟也忘记是多少了(囧)。
实现代码:
复制内容到剪贴板
代码:
/** 
* Merge sorting 
*/
MERGE(new Sortable() { 
    public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { 
        this.sort(array, 0, array.length - 1, ascend); 
    } 

    private <T extends Comparable<T>> void sort(T[] array, int lo, int hi, boolean ascend) { 
        // OPTIMIZE ONE 
        // if the substring's length is less than 20, 
        // use insertion sort to reduce recursive invocation 
        if (hi - lo < 20) { 
            for (int i = lo + 1; i <= hi; i++) { 
                T toInsert = array; 
                int j = i; 
                for (; j > lo; j--) { 
                    int compare = array[j - 1].compareTo(toInsert); 
                    if (compare == 0 || compare < 0 == ascend) { 
                        break; 
                    } 
                    array[j] = array[j - 1]; 
                } 

                array[j] = toInsert; 
            } 

            return; 
        } 

        int mid = lo + (hi - lo) / 2; 
        sort(array, lo, mid, ascend); 
        sort(array, mid + 1, hi, ascend); 
        merge(array, lo, mid, hi, ascend); 
    } 

    private <T extends Comparable<T>> void merge(T[] array, int lo, int mid, int hi, boolean ascend) { 
        // OPTIMIZE TWO 
        // if it is already in right order, skip this merge 
        // since there's no need to do so 
        int leftEndCompareToRigthStart = array[mid].compareTo(array[mid + 1]); 
        if (leftEndCompareToRigthStart == 0 || leftEndCompareToRigthStart < 0 == ascend) { 
            return; 
        } 

        @SuppressWarnings("unchecked") 
        T[] arrayCopy = (T[]) new Comparable[hi - lo + 1]; 
        System.arraycopy(array, lo, arrayCopy, 0, arrayCopy.length); 

        int lowIdx = 0; 
        int highIdx = mid - lo + 1; 

        for (int i = lo; i <= hi; i++) { 
            if (lowIdx > mid - lo) { 
                // left sub array exhausted 
                array = arrayCopy[highIdx++]; 
            } else if (highIdx > hi - lo) { 
                // right sub array exhausted 
                array = arrayCopy[lowIdx++]; 
            } else if (arrayCopy[lowIdx].compareTo(arrayCopy[highIdx]) < 0 == ascend) { 
                array = arrayCopy[lowIdx++]; 
            } else { 
                array = arrayCopy[highIdx++]; 
            } 
        } 
    } 
})

6. 快速排序
快速排序也是用归并方法实现的一个“分而治之”的排序算法,它的魅力之处在于它能在每次 partition (排序算法的核心所在)都能为一个数组元素确定其排序最终正确位置(一次就定位准,下次循环就不考虑这个元素了)。
分享到:
评论

相关推荐

    推箱子算法, 一个不错的算法, 转载

    推箱子算法,也被称为 Sokoban(索科班)算法,是一种经典的计算机科学问题,源自同名的益智游戏——推箱子。在这个游戏中,玩家需要操控一个角色在二维网格环境中移动,将散落的箱子推到指定的目标位置。游戏的关键...

    [转载]迭代算法 1.0

    迭代算法是计算机科学中一种非常基础且重要的计算方法,它通过重复执行一组步骤来逐步逼近问题的解或优化目标。在编程和算法设计中,迭代通常与循环结构紧密相关,如for、while等。本篇将深入探讨迭代算法的核心概念...

    [转载]多模匹配算法(C++)

    **多模匹配算法** 多模匹配算法是一种在文本搜索和字符串处理中广泛使用的高效算法,尤其在处理多个模式(或正则表达式)时。它主要用于查找一个文本串中的多个子串模式,而不只是单个模式。在这个场景下,传统的...

    转载 聚类算法综述 1.doc

    转载 聚类算法综述 1.doc

    RSA算法描述和代码(转载)

    根据提供的文件内容,本文将详细解析RSA算法的基本概念、工作原理及其实现步骤,并通过具体的Java代码示例来展示如何实现这一加密算法。 ### RSA算法概述 RSA算法是一种非对称加密技术,由Ron Rivest、Adi Shamir ...

    一文读懂遗传算法工作原理(附Python实现).pdf

    遗传算法工作原理及其Python实现 遗传算法是一种搜索启发式算法,通过模拟自然选择和遗传的过程来寻找最优解。该算法的理论基础来自于生物学领域,特别是关于遗传和进化的理论。 在下面,我们将详细介绍遗传算法的...

    (转载)prim算法.doc

    (转载)prim算法.doc

    烟花算法简易版,MATLAB带解析

    通过模拟烟花爆炸的方式来进行...版权声明:本文为CSDN博主「流云挽」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。 原文链接:https://blog.csdn.net/QS77258/article/details/124059890

    算法设计指南

    《算法设计指南》由算法领域的知名专家Steven Skiena教授编写, 其主要内容包括基本算法设计、算法分析、数据结构、排序与查找、图算法、动态...简书著作权归作者所有,任何形式的转载都请联系作者获得授权并注明出处。

    九章算法-面试常考算法模板 Cheat Sheet V4.11

    版权归属:九章算法(杭州)科技有限公司可以原转载和分享,转载时需保留此版权信息,不得对内容进增删和修改本作者:九章算法令狐冲排序数组(30-40%是分)

    扩展 KMP 算法(转载)

    扩展 KMP 算法 扩展 KMP 算法是 KMP 算法的变种,它可以找到字符串 S 中所有出现的子串 T。该算法的主要思路是,首先构建一个辅助数组 next,用于存储字符串 T 的最长相同前缀长度,然后使用该数组来计算字符串 S ...

    建模的十大算法(建模必用)(转载)

    在建模领域,掌握一些核心算法对于提升建模能力至关重要。"建模的十大算法(建模必用)"这个资料包显然包含了建模过程中常用的一些高效方法,旨在帮助研究者和实践者解决复杂问题。这里我们将深入探讨其中可能涵盖的...

    粒子群算法代码

    可以供大家开发更好的粒子群算法粒子群算法,也称粒子群优化算法(Particle Swarm Optimization),缩写为 PSO, 是近年来发展起来的一种新的进化算法...版权声明:本文为博主原创文章,转载请附上博文链接!

    Sha安全哈希算法 转载的

    SHA(Secure Hash Algorithm,安全哈希算法)是一类用于生成固定长度散列值的加密算法,主要用于数据完整性验证和数字签名。它通过特定的数学运算将任意长度的输入(也称为预映射或消息)转化为固定长度的输出,这个...

    论文研究-供应链系统中零售商横向转载的随机规划模型及算法.pdf

    论文研究-供应链系统中零售商横向转载的随机规划模型及算法.pdf, 为了研究随机需求下供应链系统中多零售商的横向转载问题, 提出了一种基于随机规划方法的多零售商横向...

    转载 RSA加密算法的基本原理.doc

    转载 RSA加密算法的基本原理.doc

    asiftmatlab-[转载]计算机视觉算法与代码集锦 计算机视觉.pdf

    这篇文档“asiftmatlab-[转载]计算机视觉算法与代码集锦 计算机视觉.pdf”显然是一个综合性的资源,涵盖了多个计算机视觉算法及其MATLAB实现。下面我们将详细探讨其中涉及的一些重要概念和技术。 1. 特征检测与提取...

    大规模网页快速去重算法

    这类差异多因转载过程中的编辑调整所致,如删减、乱码或标题更改。 ##### 通用聚类方法的局限性 传统聚类算法在解决网页去重问题上的应用遭遇了瓶颈。通常,此类算法将网页转换为向量,以6763个常用汉字为基础,...

    vb_GeneticAlgorithm.rar_VB 遗传算法_genetic algorithm_遗传算法 _遗传算法 VB

    用vb编写遗传算法,实际应用部分(如适应度函数需要自己编写,程序中已注明),此为转载代码

Global site tag (gtag.js) - Google Analytics