济南新闻电视台:十二种排序包你满足(冒泡、插入、合并、快速排序等包罗希尔和计数排序)

admin 6个月前 (04-12) 科技 27 0

前言

排序算法在盘算机科学入门课程中很普遍,在学习排序算法的时刻,涉及到大量的种种焦点算法观点,例如大O示意法,分治法,堆和二叉树之类的数据结构,随机算法,最佳、最差和平均情形剖析,时空权衡以及上限和下限,本文就先容了十二种排序算法供人人学习。

简介

排序算法是用来凭据元素对应的对照运算符重新排列给定的数组的算法,输出的数组是一个凭据对照符从小到大或者从大到小依次排列的数组。对照运算符是用于确定响应数据结构中元素的新顺序,好比在整数数组内里,对应的对照符号就是大于或者小于号,用户也可以自己界说对应的对照运算符。

好比若是输入是[4,2,3,1],根据从小到大输出,效果应该是[1,2,3,4]

特征

稳固性

若是在数组中有两个元素是相等的,在经由某个排序算法之后,原来在前面的的谁人元素仍然在另一个元素的前面,那么我们就说这个排序算法是稳固的。

若是在排序之后,原来的两个相等元素中在前面的一个元素被移到了后面,那么这个算法就是不稳固的。

好比排序之前数组为[3(a),2,3(b)](其中ab划分代表两个差别的3),经由某个排序算法之后是[2,3(a),3(b)],那么这个算法就是稳固的;若是酿成了[2,3(b),3(a)],那么这个算法是不稳固的。

再好比在根据身高排队去食堂打饭的历程中,小明和小刚的身高都是170,原来小明在小刚前面,然则经由排序之后小明发现小刚到了他前面了,这样小明一定对这个不稳固的排序有意见。

时间庞大度

时间庞大度反映了算法的排序效率,通常用大O示意法来示意,通常表示这个算法需要的最多操作次数的量级,好比\(O(n)\)示意最多需要举行\(n\)量级操作。

空间庞大度

空间庞大度反映了算法需要消耗的空间,好比\(O(1)\)示意只需要常数目级的空间,不会随着数组巨细的转变而转变。

若是一个排序算法不需要分外的存储空间,可以直接在原来的数组完成排序操作,这个算法可以被称之为原地算法,空间庞大度是\(O(1)\)

对照排序、非对照排序

若是一个算法需要在排序的历程中使用对照操作来判断两个元素的巨细关系,那么这个排序算法就是对照排序,大部门排序算法都是对照排序,好比冒泡排序、插入排序、堆排序等等,这种排序算法的平均时间庞大度最快也只能是\(O(nlogn)\)

非对照排序对照典型的有计数排序、桶排序和基数排序,这类排序能够脱离对照排序时间庞大度的约束,到达\(O(n)\)级别的效率。

算法

首先界说基本的交流数组元素的基本方式,节约后面的代码量。

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

冒泡排序

冒泡排序是从左到右依次对照相邻的两个元素,若是前一个元素对照大,就把前一个元素和后一个交流位置,遍历数组之后保证最后一个元素相对于前面的永远是最大的。然后让最后一个保持稳定,重新遍历前n-1个元素,保证第n-1个元素在前n-1个元素内里是最大的。依此纪律直到第2个元素是前2个元素内里最大的,排序就竣事了。

由于这个排序的历程很像冒泡泡,找到最大的元素一直的移动到最后端,以是这个排序算法就叫冒泡排序。

图片来自这里

用Java代码实现

private void bubbleSort(int[] nums) {
    for (int i = nums.length - 1; i >= 1; i--) { // 冒泡获得n-1个最大值
        for (int j = 1; j <= i; j++) {
            if (nums[j-1]>nums[j])
                swap(nums, j, j-1);           // 交流获得较大值
        }
    }
}

冒泡排序的最大特点就是代码简朴,短短的五行代码就能完成整个排序的操作。

时间庞大度对照稳固不管怎样都需要\(O(n^2)\)次对照,以是是\(O(n^2)\)的时间庞大度。

空间庞大度是\(O(1)\),所有操作在原来的数组完成就可以了,不需要分外的空间。

算法是稳固的,在冒泡的历程中若是两个元素相等,那么他们的位置是不会交流的。

选择排序

选择排序的思绪对照简朴,先找到前n个元素中最大的值,然后和最后一个元素交流,这样保证最后一个元素一定是最大的,然后找到前n-1个元素中的最大值,和第n-1个元素举行交流,然后找到前n-2个元素中最大值,和第n-2个元素交流,依次类推到第2个元素,这样就获得了最后的排序数组。

实在整个历程和冒泡排序差不多,都是要找到最大的元素放到最后,差别点是冒泡排序是一直的交流元素,而选择排序只需要在每一轮交流一次。

原图来自这里

代码实现:

private void selectionSort(int[] nums) {
    for (int i = nums.length - 1; i > 0; i--) {
        int maxIndex = 0;         // 最大元素的位置
        for (int j = 0; j <= i; j++) {
            if (nums[maxIndex]<nums[j]) {
                maxIndex = j;
            }
        }
        swap(nums, maxIndex, i);   // 把这个最大的元素移到最后
    }
}

时间庞大度和冒泡排序一样对照稳固,都需要\(O(n^2)\)次对照,以是时间庞大度是\(O(n^2)\)

空间庞大度是\(O(1)\),不需要分外空间,是原地算法。

选择排序最简朴的版本是不稳固的,好比数组[1,3,2,2],示意为[1,3,2(a),2(b)],在经由一轮遍历之后酿成了[1,2(b),2(a),3],两个2之间的顺序由于第一个23的换取而颠倒了,以是不是稳固排序。

不外可以改善一下选择排序酿成稳固的。原来不稳固是由于交流位置导致的,现在若是改成插入操作(不是使用数组而是链表,把最大的元素插入到最后)的话,就能酿成稳固排序。好比[1,3,2(a),2(b)],在第一轮中酿成了[1,2(a),2(b),3],这样就能够保持相对位置,酿成稳固排序。

插入排序

插入排序的焦点头脑是遍历整个数组,保持当前元素左侧始终是排序后的数组,然后将当前元素插入到前面排序完成的数组的对应的位置,使其保持排序状态。有点动态计划的感受,类似于先把前i-1个元素排序完成,再插入第i个元素,组成i个元素的有序数组。

图片来自这里

简朴代码实现:

private void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {   // 从第二个元素最先遍历
        int j = i;
        while (j>0&&nums[j]<nums[j-1]) {     // 将当前元素移动到合适的位置
            swap(nums, j, j-1);
            j--;
        }
    }
}

时间庞大度上,插入排序在最好的情形,也就是数组已经排好序的时刻,庞大度是\(O(n)\),在其他情形下都是\(O(n^2)\)

空间庞大度是\(O(1)\),不需要分外的空间,是原地算法。

插入排序是稳固排序,每次交流都是相邻元素的交流,不会有选择排序的那种跳跃式交流元素。

希尔排序

希尔排序可以看作是一个冒泡排序或者插入排序的变形。希尔排序在每次的排序的时刻都把数组拆分成若干个序列,一个序列的相邻的元素索引相隔的牢固的距离gap,每一轮对这些序列举行冒泡或者插入排序,然后再缩小gap获得新的序列逐一排序,直到gap为1

好比对于数组[5,2,4,3,1,2],第一轮gap=3拆分成[5,3][2,1][4,2]三个数组举行插入排序获得[3,1,2,5,2,4];第二轮gap=2,拆分成[3,2,2][1,5,4]举行插入排序获得[2,1,2,4,3,5];最后gap=1,全局插入排序获得[1,2,2,3,4,5]

图片来自这里

简朴代码实现:

private void shellSor(int[] nums) {
    int gap = nums.length >> 1;
    while (gap > 0) {
        for (int i = 0; i < gap; i++) {                        // 对每个子序列举行排序
            for (int j = i+gap; j < nums.length; j+=gap) {     // 插入排序的部门
                int temp = j;
                while (temp > i && nums[temp] < nums[temp-gap]) {
                    swap(nums, temp, temp-gap);
                    temp -= gap;
                }
            }
        }
        gap >>= 1;
    }
}

Donald Shell于1959年公布了这种排序算法,运行时间在很大程度上取决于它使用的距离,在现实使用中,其时间庞大度仍然是一个悬而未决的问题,基本在\(O(n^2)\)\(O(n^{4/3})\)之间。

空间庞大度是\(O(1)\),是原地算法。

这个算法是不稳固的,内里有许多不相邻元素的交流操作。

合并排序

合并排序是典型的使用分治头脑(divide-and-conquer)解决问题的案例。在排序的历程中,把原来的数组酿成左右两个数组,然后划分举行排序,当左右的子数组排序完毕之后,再合并这两个子数组形成一个新的排序数组。整个历程递归举行,当只剩下一个元素或者没有元素的时刻就直接返回。

图片来自这里

代码如下:

private void mergeSort(int[] nums, int left, int right) {  // 需要左右界限确定排序局限
    if (left >= right) return;
    int mid = (left+right) / 2;

    mergeSort(nums, left, mid);                           // 先对左右子数组举行排序
    mergeSort(nums, mid+1, right);

    int[] temp = new int[right-left+1];                   // 暂且数组存放合并效果
    int i=left,j=mid+1;
    int cur = 0;
    while (i<=mid&&j<=right) {                            // 最先合并数组
        if (nums[i]<=nums[j]) temp[cur] = nums[i++];
        else temp[cur] = nums[j++];
        cur++;
    }
    while (i<=mid) temp[cur++] = nums[i++];
    while (j<=right) temp[cur++] = nums[j++];

    for (int k = 0; k < temp.length; k++) {             // 合并数组完成,拷贝到原来的数组中
        nums[left+k] = temp[k];
    }
}

时间庞大度上合并排序能够稳固在\(O(nlogn)\)的水平,在每一级的合并排序数组历程中总的操作次数是\(n\),总的层级数是\(logn\),相乘获得最后的效果就是\(O(nlogn)\)

空间庞大度是\(O(n)\),由于在合并的历程中需要使用暂且数组来存放暂且排序效果。

合并排序是稳固排序,保证原来相同的元素能够保持相对的位置。

快速排序

快速排序(有时称为分区交流排序)是一种高效的排序算法。由英国盘算机科学家Tony Hoare于1959年开发并于1961年揭晓,它在现在仍然是一种常用的排序算法。若是实现方式适当,它可以比主要竞争对手(合并排序和堆排序)快两到三倍。

其焦点的思绪是取第一个元素(或者最后一个元素)作为分界点,把整个数组分成左右两侧,左边的元素小于或者即是分界点元素,而右边的元素大于分界点元素,然后把分界点移到中心位置,对左右子数组划分举行递归,最后就能获得一个排序完成的数组。当子数组只有一个或者没有元素的时刻就竣事这个递归历程。

其中最主要的是将整个数组凭据分界点元素划分成左右两侧的逻辑,现在有两种算法,图片展示的是第一种。

图片来自这里

第一种实现,也是图片中的排序逻辑的实现:

private void quickSort(int[] nums, int left, int right) {
    if (left >= right) return;
    int lo = left+1;               // 小于分界点元素的最右侧的指针
    int hi = right;                // 大于分界点元素的最左侧的指针
    while (lo<=hi) {
        if (nums[lo]>nums[left]) { // 交流元素确保左侧指针指向元素小于分界点元素
            swap(nums, lo, hi);
            hi--;
        } else {
            lo++;
        }
    }
    lo--;                          // 回到小于分界点元素数组的最右侧
    swap(nums, left, lo);          // 将分界点元素移到左侧数组最右侧
    quickSort2(nums, left, lo-1);
    quickSort2(nums, lo+1, right);
}

第二种,不用hi来符号大于分界点元素的最右侧,而是只用一个lo来符号最左侧。在遍历整个数组的历程中,若是发现了一个小于即是分界点元素的元素,就和lo+1位置的元素交流,然后lo自增,这样可以保证lo的左侧一定都是小于即是分界点元素的,遍历到最后lo的位置就是新的分界点位置,和最最先的分界点元素位置交换。

private void quickSort(int[] nums, int left, int right) {
    if (left>=right) return;
    int cur = left + 1;                   // 从左侧第二个元素最先
    int lo = left;                        // 分界点为第一个元素
    while (cur <= right) {
        if (nums[cur] <= nums[left]) {    // 交流位置保证lo的左侧都是小于num[left]
            swap(nums, lo+1, cur);
            lo ++;
        }
        cur++;
    }
    swap(nums, left, lo);                 // 把分界点元素移动到新的分界位置
    quickSort(nums, left, lo-1);
    quickSort(nums, lo+1, right);
}

时间庞大度在最佳情形是\(O(nlogn)\),然则若是分界点元素选择欠妥可能会恶化到\(O(n^2)\),然则这种情形对照少见(好比数组完全逆序),若是随机选择分界点的话,时间庞大度能够稳固在\(O(nlogn)\)。另外若是元素中相同元素数目对照多的话,也会降低排序性能。

空间庞大度在\(O(logn)\)水平,属于客栈挪用,在最坏的情形下空间庞大度照样\(O(n)\),平均情形下庞大度是\(O(logn)\)

快速排序是不稳固的,由于包罗跳跃式交流元素位置。

堆排序

堆排序是一个效率要高得多的选择排序,首先把整个数组酿成一个最大堆,然后每次从堆顶取出最大的元素,这样依次取出的最大元素就形成了一个排序的数组。堆排序的焦点分成两个部门,第一个是新建一个堆,第二个是弹出堆顶元素后重修堆。

新建堆不需要分外的空间,而是使用原来的数组,一个数组在另一个维度上可以看成一个完全二叉树(除了最后一层之外其他的每一层都被完全填充,而且所有的节点都向左对齐),对于下标为i的元素,他的子节点是2*i+12*i+2(条件是没有超出界限)。在新建堆的时刻从左向右最先遍历,当遍历到一个元素的时刻,重新排列从这个元素节点到根节点的所有元素,保证知足最大堆的要求(父节点比子节点要大)。遍历完整个数组的时刻,这个最大堆就完成了。

在弹出根节点之后(把根节点的元素和树的最底层最右侧的元素交换),堆被损坏,需要重修。从根节点最先和两个子节点对照,若是父节点比最大的子节点小,那么就交换父节点和最大的子节点,然后把交换后在子节点位置的父节点看成新的父节点,和它的子节点对照,云云往复直到最后一层,这样最大堆就重修完毕了。

图片来自这里

简朴java代码:

private void heapSort(int[] nums) {
    heapify(nums);                                 // 新建一个最大堆
    for (int i = nums.length - 1; i >= 1; i--) {
        swap(nums, 0, i);                       // 弹出最大堆的堆顶放在最后
        rebuildHeap(nums, 0,i-1);          // 重修最大堆
    }
}

private void heapify(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int par = (i-1)>>1;                       // 找到父节点
        int child = i;                            // 界说子节点
        while (child>0&&nums[par]<nums[child]) {  // 从子节点到根节点构建最大堆
            swap(nums, par, child);
            child = par;
            par = (par-1) >> 1;
        }
    }
}

private void rebuildHeap(int[] nums, int par, int last) {
    int left = 2*par+1;                           // 左子节点
    int right = 2*par+2;                          // 右子节点
    int maxIndex = left;

    if (right<=last && nums[right]>nums[left]) {  // 找到最大子节点
        maxIndex = right;
    }

    if (left<=last && nums[par] < nums[maxIndex]) {// 和最大子节点对照
        swap(nums, par, maxIndex);                 // 交换到最大子节点
        rebuildHeap(nums, maxIndex, last);         // 重修最大子节点代表的子树
    }
}

时间庞大度稳固在\(O(nlogn)\),由于在构建堆的时刻时间遍历数组对于每个元素需要举行\(O(logn)\)次对照,时间庞大度是\(O(nlogn)\)。在弹出每个元素重修堆需要\(O(logn)\)的庞大度,时间庞大度也是\(O(nlogn)\),以是整体的时间庞大度是\(O(nlogn)\)

空间庞大度是\(O(1)\),在原数组举行所有操作就可以了。

堆排序是不稳固,堆得构建和重修的历程都市打乱元素的相对位置。

堆排序的代码量相对于其他的排序算法来说是对照多的,明白上也对照难,涉及到最大堆和二叉树等相关观点。虽然在现实使用中相对于快速排序不是那么好用,然则最坏情形下的\(O(nlogn)\)的时间庞大度也是优于快排的。空间使用是恒定的,是优于合并排序。

二叉搜索树排序

二叉树搜索排序用数组内的所有元素构建一个搜索二叉树,然后用中序遍历重新将所有的元素填充回原来的数组中。由于搜索二叉树不能用数组来示意,以是必须使用分外的数据结构来构建二叉树。

图片来自这里

简朴代码如下:

private int[] bstSort(int[] nums) {
    TreeNode root = new TreeNode(nums[0]);   // 构建根节点
    for (int i = 1; i < nums.length; i++) {  // 将所有的元素插入到二叉搜索树中
        buildTree(root, nums[i]);
    }
    inorderTraversal(root, nums, new int[1]);// 中序遍历获取二叉树中的所有节点
    return nums;
}

private void inorderTraversal(TreeNode node, int[] nums, int[] pos) {
    if (node == null) return;
    inorderTraversal(node.left, nums, pos);
    nums[pos[0]++] = node.val;
    inorderTraversal(node.right, nums, pos);
}

private void buildTree(TreeNode node, int num) {
    if (node == null) return;
    if (num >= node.val) {                   // 插入到右子树中
        if (node.right == null) {
            node.right = new TreeNode(num);
        } else {
            buildTree(node.right, num);
        }
    } else {                                 // 插入到左子树中
        if (node.left == null) {
            node.left = new TreeNode(num);
        } else {
            buildTree(node.left, num);
        }
    }
}

static class TreeNode {   // 树节点的数据结构
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}

时间庞大度上面凭据原数组转变对照大,最差情形是整个数组是已经排好序的,这样二叉树会酿成一个链表结构,时间庞大度退化到了\(O(n^2)\),然则最优和平均情形下时间庞大度在\(O(nlogn)\)水平。

空间庞大度是\(O(n)\),由于要构建一个包罗n个元素的二叉搜索树。

这个算法是稳固,在构建二叉树的历程中能够保证元素顺序的一致性。

计数排序

计数排序是一个最基本的非对照排序,能够将时间庞大度提高到\(O(n)\)的水平,然则使用上对照有局限性,通常只能应用在键的转变局限对照小的情形下,若是键的转变局限稀奇大,建议使用基数排序。

计数排序的历程是建立一个长度为数组中最小和最大元素之差的数组,划分对应数组中的每个元素,然后用这个新的数组来统计每个元素泛起的频率,然后遍历新的数组,凭据每个元素泛起的频率把元素放回到老的数组中,获得已经排好序的数组。

图片来自这里

简朴代码实现:

private void countSort(int[] nums) {
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int num : nums) {            // 找到最大最小值
        min = Math.min(min, num);
        max = Math.max(max, num);
    }
    int[] count = new int[max-min+1]; // 建立新数组
    for (int num : nums) {            // 统计每个元素泛起频率
        count[num-min]++;
    }
    int cur = 0;
    for (int i = 0; i < count.length; i++) {  // 凭据泛起频率把计数数组中的元素放回到旧数组中
        while (count[i]>0) {
            nums[cur++] = i+min;
            count[i]--;
        }
    }
}

计数排序能够将时间庞大度降低到\(O(n+r)\)(r为数组元素转变局限),不外这是对于数组元素的转变局限不是稀奇大。随着局限的变大,计数排序的性能就会逐渐降低。

空间庞大度为\(O(n+r)\),随着数组元素转变局限的增大,空间庞大度也会变大。

计数排序是稳固的,原来排在前面的相同在计数的时刻,仍然是排在每个计数位置的前面,在最后回复的时刻也是从每个计数位的前面最先回复,以是最后相对位置照样相同的。

桶排序

桶排序是将所有的元素漫衍到一系列的区间(也可以称之为)内里,然后对每个桶内里的所有元素划分举行排序的算法。

首先新建一个桶的数组,每个桶的规则需要提前制定好,好比元素在09为一个桶、1019为一个桶。然后遍历整个待排序的数组,把元素分配到对应的桶内里。接下来单独对每个桶内里的元素举行排序,排序算法可以选择对照排序或者非对照排序,获得排序后的数组。最后把所有的桶内的元素还原到原数组内里获得最后的排序数组。

图片来自这里

private void bucketSort(int[] nums) {
    int INTERVAL = 100;               // 界说桶的巨细
    int min = Integer.MAX_VALUE;
    int max = Integer.MIN_VALUE;
    for (int num : nums) {            // 找到数组元素的局限
        min = Math.min(min, num);
        max = Math.max(max, num);
    }
    int count = (max - min + 1);      // 盘算出桶的数目
    int bucketSize = (count % INTERVAL == 0) ?( count / INTERVAL) : (count / INTERVAL+1);
    List<Integer>[] buckets = new List[bucketSize];
    for (int num : nums) {            // 把所有元素放入对应的桶内里
        int quotient = (num-min) / INTERVAL;
        if (buckets[quotient] == null) buckets[quotient] = new ArrayList<>();
        buckets[quotient].add(num);
    }
    int cur = 0;
    for (List<Integer> bucket : buckets) {
        if (bucket != null) {
            bucket.sort(null);       // 对每个桶举行排序
            for (Integer integer : bucket) {  // 还原桶内里的元素到原数组
                nums[cur++] = integer;
            }
        }
    }
}

时间庞大度上桶排序和计数排序一样,是\(O(n+r)\)的水平,然则随着数据元素局限的增大,时间消耗也在增大。

空间庞大度也是\(O(n+r)\),需要分外的空间来保留所有的桶和桶内里的元素。

桶排序是稳固的(条件是桶内排序的逻辑是稳固的),和计数排序的逻辑类似,遍历历程插入桶的历程中没有改变相同元素的相对位置,排序也没有改变,最后的还原也没有改变。

基数排序

基数排序和桶排序有点相似,基数排序中需要把元素送入对应的桶中,不外规则是凭据所有数字的某一位上面的数字来分类。

假设当前数组的所有元素都是正数,桶的数目就牢固在了10个,然后盘算出最大元素的位数。首先凭据每个元素的最低位举行分组,好比1就放入1这个桶,13就放入3这个桶,111也放入1这个桶,然后把所有的数字凭据桶的顺序取出来,依次还原到原数组内里。在第二轮从第二位最先分组,好比1(看作01)放入0这个桶,13放入1这个桶,111也放入1这个桶,再把所有的元素从桶内里依次取出放入原数组。经由最大元素位数次的这样的操作之后,还原获得的数组就是一个已经排好序的数组。

图片来自这里

思量到数组内里另有负数的情形,可以把桶的巨细扩大到19个,划分代表对应位在-9~9之间的数字,代码如下:

private void radixSort(int[] nums) {
    int max = -1;
    int min = 1;
    for (int num : nums) {         // 盘算最大最小值
        max = Math.max(max, num);
        min = Math.min(min, num);
    }
    max = Math.max(max, -min);     // 求得绝对值最大的值
    int digits = 0;
    while (max > 0) {              // 盘算绝对值最大的值的位数
        max /= 10;
        digits++;
    }
    List<Integer>[] buckets = new List[19]; // 建一个包罗所有位数的数组
    for (int i = 0; i < buckets.length; i++) {
        buckets[i] = new ArrayList<>();
    }
    int pos;
    int cur;
    for (int i = 0, mod = 1; i < digits; i++, mod*=10) { // 对十进制每一位举行基数排序
        for (int num : nums) {                 // 扫描数组将值放入对应的桶
            pos = (num / mod) % 10;
            buckets[pos+9].add(num);
        }
        cur = 0;
        for (List<Integer> bucket : buckets) { // 将桶内元素放回到数组内里
            if (bucket!=null) {
                for (Integer integer : bucket) {
                    nums[cur++] = integer;
                }
                bucket.clear();                // 将桶清空
            }
        }
    }
}

时间庞大度基本在\(O(n·\frac{k}{d})\)水平,其中\(k\)为key的总数目,\(d\)为绝对值最大的数字的十进制位数。

空间庞大度是\(O(n+2^d)\)

基数排序是一个稳固排序算法,在排序添加元素的历程中没有改变相同元素的相互位置。

TimSort

Timsort是由Tim Peters在2002年实现的,自Python 2.3以来,它一直是Python的尺度排序算法。Java在JDK中使用Timsort对非基本类型举行排序。Android平台和GNU Octave还将其用作默认排序算法。

Timsort是一种稳固的夹杂排序算法,同时应用了二分插入排序和合并排序的头脑,在时间上击败了其他所有排序算法。它在最坏情形下的时间庞大度为\(O(nlogn)\)优于快速排序;最佳情形的时间庞大度为\(O(n)\),优于合并排序和堆排序。

由于使用了合并排序,使用分外的空间保留数据,TimSort空间庞大度是\(O(n)\)

由于篇幅缘故原由,TimSort的详细实现历程暂且就不讲了,感兴趣的同砚可以看我的另外一篇博客——世界上最快的排序算法——Timsort

总结

排序算法 最好情形 平均情形 最差情形 空间庞大度 稳固性
冒泡排序 \(n^2\) \(n^2\) \(n^2\) \(1\)
选择排序 \(n^2\) \(n^2\) \(n^2\) \(1\)
插入排序 \(n\) \(n^2\) \(n^2\) \(1\)
希尔排序 \(nlogn\) \(n^{4/3}\) \(n^{4/3}\) \(1\)
二叉树排序 \(nlogn\) \(nlogn\) \(n^2\) \(n\)
合并排序 \(nlogn\) \(nlogn\) \(nlogn\) \(n\)
快速排序 \(nlogn\) \(nlogn\) \(n^2\) \(logn\)
堆排序 \(nlogn\) \(nlogn\) \(nlogn\) \(1\)
计数排序 - \(n+r\) \(n+r\) \(n+r\)
桶排序 - \(n+r\) \(n+r\) \(n+r\)
基数排序 - \(\frac{nk}{d}\) \(\frac{nk}{d}\) \(n+2^d\)
TimSort \(n\) \(nlogn\) \(nlogn\) \(n\)

备注:\(r\)为排序数字的局限,\(d\)是数字总位数,\(k\)是数字总个数

上面的表格总结了讲到的排序算法的时间和空间庞大度以及稳固性等,在现实应用中会有种种排序算法变形的问题,都可以通过优化排序算法来到达优化算法的目的。

若是对时间庞大度要求对照高而且键的漫衍局限对照广,可以使用合并排序、快速排序和堆排序。

若是不能使用分外的空间,那么快速排序和堆排序都是不错的选择。

若是划定了排序的键的局限,可以优先思量使用桶排序。

若是不想写太多的代码同时时间庞大度没有太高的要求,可以思量冒泡排序、选择排序和插入排序。

若是排序的历程中没有庞大的分外操作,直接使用编程语言内置的排序算法就行了。

参考

超详细十大经典排序算法总结(java代码)
十大经典排序算法
十大经典排序算法(动图演示)
Sorting algorithm
Timsort
Data Structure - Sorting Techniques
This is the fastest sorting algorithm ever
TimSort
Timsort: The Fastest sorting algorithm for real-world problems

更多内容请看我的小我私家博客

,

阳光在线

阳光在线www.jinyanlawyer.com(原诚信在线)现已开放阳光在线手机版下载。阳光在线游戏公平、公开、公正,用实力赢取信誉。

网友评论

  • (*)

最新评论

文章归档

站点信息

  • 文章总数:833
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1457
  • 评论总数:420
  • 浏览总数:24830