游戏化思维自学英语,像玩游戏一样过关斩将,让你对学习上瘾,在无形之中用地道的英语跟老外谈笑风生。详情加微信了解:cool-smiler

排序算法深入研究

薪薪向荣 JackLeon 3个月前 (03-19) 94次浏览 0个评论 扫描二维码

堆排序

堆积排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。

堆是具有以下性质的完全二叉树:

  • 每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;
  • 或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

排序算法深入研究

同时,我们对堆中的结点按层进行编号,将这种逻辑结构映射到数组中

该数组从逻辑上讲就是一个堆结构,我们用简单的公式来描述一下堆的定义就是:

  • 大顶堆:arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
  • 小顶堆:arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序的最好、最坏、平均时间复杂度都为Ο(nlogn)

步骤:

堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余 n-1 个元素重新构造成一个堆,这样会得到 n 个元素的次小值。如此反复执行,便能得到一个有序序列了

  1. 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)

假设给定无序序列结构如下:

此时我们从最后一个非叶子结点开始(叶结点自然不用调整,最后一个非叶子结点 arr.length/2-1=5/2-1=1,也就是下面的 6 结点),从左至右,从下至上进行调整

找到第二个非叶节点 4,由于[4,9,8]中 9 元素最大,4 和 9 交换

这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中 6 最大,交换 4 和 6

此时,我们就将一个无需序列构造成了一个大顶堆

  1. 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素。如此反复进行交换、重建、交换

将堆顶元素 9 和末尾元素 4 进行交换

重新调整结构,使其继续满足堆定义

再将堆顶元素 8 与末尾元素 5 进行交换,得到第二大元素 8

后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序

总结下堆排序的基本思路:

  • 将无需序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
  • 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
  • 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个序列有序

代码实现:

/**
     * 升序(大顶堆)
     * @param array
     * @return
     */
    public static Integer[] asc(Integer[] array) {
        int len = array.length;
        while (len > 1) {
            // 无序数组大顶堆排序
            bigHeapify(array, len);
            // 交换堆顶元素与末尾元素
            swap(array, 0, len - 1);
            len --;
        }
        return array;
    }

    /**
     * 大顶堆
     * @param array
     */
    private static void bigHeapify(Integer[] array, int length) {
        for (int i = length / 2 - 1; i >= 0; i--) {
            int lNode = i * 2 + 1;
            int rNode = i * 2 + 2;
            if(array[i] < array[lNode]){ // 左节点大于父节点时,交换值
                swap(array, i, lNode);
            }
            if(rNode < length && array[i] < array[rNode]){ // 右节点大于父节点时,交换值
                swap(array, i, rNode);
            }
        }
    }
    
    /**
     * 降序(小顶堆)
     * @param array
     * @return
     */
    public static Integer[] desc(Integer[] array) {
        int len = array.length;
        while (len > 1) {
            // 无序数组小顶堆排序
            smallHeapify(array, len);
            // 交换堆顶元素与末尾元素
            swap(array, 0, len - 1);
            len --;
        }
        return array;
    }

    /**
     * 小顶堆
     * @param array
     * @return
     */
    private static void smallHeapify(Integer[] array, int length) {
        for (int i = length / 2 - 1; i >= 0; i--) {
            int lNode = i * 2 + 1;
            int rNode = i * 2 + 2;
            if(array[i] > array[lNode]){ // 左节点小于于父节点时,交换值
                swap(array, i, lNode);
            }
            if(rNode < length && array[i] > array[rNode]){ // 右节点小于于父节点时,交换值
                swap(array, i, rNode);
            }
        }
    }
    
    /**
     * 交换值
     * @param array
     * @param s
     * @param t
     */
    private static void swap(Integer[] array, int s, int t) {
        array[s] = array[s] + array[t];
        array[t] = array[s] - array[t];
        array[s] = array[s] - array[t];
    }

排序效果:

快速排序

介绍:

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性。

步骤:

  1. 从数列中挑出一个元素,称为 “基准”(pivot),
  1. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
  1. 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

代码实现:

/**
 * Java
 */

void quickSort(Integer[] array, int left, int right) {
    final int left_ = left;
    final int right_ = right;
    if(left <= right){ 
        int pivot = array[left];    // 取第一个元素为基准
        while(left != right) {
            while (left < right && array[right] >= pivot) right --;
            array[left] = array[right];
            while (left < right &&  array[left] <= pivot) left ++;
            array[right] = array[left];
        }
        array[right] = pivot;    // 集准点归位
        quickSort(array, left_, left - 1);    // 递归左分区
        quickSort(array, right + 1, right_);    // 递归右分区
    }
}

排序效果:


归并排序

介绍:

归并排序(Merge sort,台湾译作:合并排序)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用

步骤:

  1. 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列
  1. 设定两个指针,最初位置分别为两个已经排序序列的起始位置
  1. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置
  1. 重复步骤 3 直到某一指针达到序列尾
  1. 将另一序列剩下的所有元素直接复制到合并序列尾

代码实现:

/**
 * JavaScript
 */

function mergeSort(arr) {  // 采用自上而下的递归方法
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

/**
 * Java
 */

public static Integer[] mergeSort(Integer[] array) {
    if(array.length < 2) return array;
    int middle = array.length / 2;
    Integer[] lArr = Arrays.copyOfRange(array, 0, middle);
    Integer[] rArr = Arrays.copyOfRange(array, middle, array.length);
    return sort(mergeSort(lArr), mergeSort(rArr));
}
    
private static Integer[] sort(Integer[] lArr, Integer[] rArr) {
    Integer[] array = new Integer[lArr.length + rArr.length];
    int index = 0;
    int r = 0;
    int l = 0;
    while (index < lArr.length + rArr.length) {
        if(l < lArr.length && r < rArr.length && rArr[r] > lArr[l]){
            array[index] = lArr[l];
            l++;
            index ++;
        }else if(r < rArr.length){
            array[index] = rArr[r];
            r++;
            index ++;
        }else{
            while (index < lArr.length + rArr.length && r < rArr.length){
                array[index] = rArr[r];
                r++;
                index ++;
            }
            while (index < lArr.length + rArr.length && l < lArr.length){
                array[index] = lArr[l];
                l++;
                index ++;
            }
        }
    }
    return array;
}

排序效果:


选择排序

介绍:

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾。以此类推,直到所有元素均排序完毕。

步骤:

  1. 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置
  1. 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
  1. 重复第二步,直到所有元素均排序完毕。

代码实现:

/**
 * JavaScript
 */
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

/**
 * Java
 */
void selectionSort(Integer[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < array.length; j++) {
            if(array[minIndex] >= array[j]) minIndex = j;
        }
        if(array[minIndex] == array[i]) continue;
        array[minIndex] = array[minIndex] + array[i];
        array[i] = array[minIndex] - array[i];
        array[minIndex] = array[minIndex] - array[i];
    }
}

排序效果:

冒泡排序

介绍:

冒泡排序(Bubble Sort,台湾译为:泡沫排序或气泡排序)是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

步骤:

  1. 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
  1. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
  1. 针对所有的元素重复以上的步骤,除了最后一个。
  1. 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

代码实现:

/**
 * Java
 */

void bubbleSort(Integer[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        for (int j = i + 1; j < array.length; j++) {
            if(array[i] > array[j]){
                array[i] = array[i] + array[j];
                array[j] = array[i] - array[j];
                array[i] = array[i] - array[j];
            }
        }
    }
}

排序效果:

插入排序

介绍:

插入排序(Insertion Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用 in-place 排序(即只需用到 O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

步骤:

  1. 从第一个元素开始,该元素可以认为已经被排序
  1. 取出下一个元素,在已经排序的元素序列中从后向前扫描
  1. 如果该元素(已排序)大于新元素,将该元素移到下一位置
  1. 重复步骤 3,直到找到已排序的元素小于或者等于新元素的位置
  1. 将新元素插入到该位置中
  1. 重复步骤 2

代码实现:

/**
 * JavaScript
 */

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

/**
 * Java
 */

void insertionSort(Integer[] array) {
    for (int i = 1; i < array.length; i++) {
        int current = array[i];
        int prevIndex = i - 1;
        while (prevIndex >= 0 && array[prevIndex] > current) {
            array[prevIndex + 1] = array[prevIndex];
            prevIndex --;
        }
        array[prevIndex + 1] = current;
    }
}

排序效果:

1

希尔排序

2

介绍:

3

4

希尔排序,也称递减增量排序算法,是插入排序的一种高速而稳定的改进版本。

5

6

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

7

8

1、插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率

9

10

2、但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

11

12

排序效果:

13

14

15

计数排序

介绍:

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数

计数排序是一个稳定的排序算法。当输入的元素是 n 个 0 到 k 之间的整数时,时间复杂度是 O(n+k),空间复杂度也是 O(n+k),其排序速度快于任何比较排序算法。当 k 不是很大并且序列比较集中时,计数排序是一个很有效的排序算法

步骤:
  1. 找出待排序的数组中最大和最小的元素;
  1. 统计数组中每个值为 i 的元素出现的次数,存入数组 C 的第 i 项;
  1. 对所有的计数累加(从 C 中的第一个元素开始,每一项和前一项相加);
  1. 反向填充目标数组:将每个元素 i 放在新数组的第 C(i)项,每放一个元素就将 C(i)减去 1。

代码实现:

/**
     * 计数排序
     * @param array
     */
    void countingSort(Integer[] array) {
        // 找出最大值、最小值
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] > max) max = array[i];
            if(array[i] < min) min = array[i];
        }
        // 最大最小元素之间范围[min, max]的长度
        int len = max - min + 1; 
        // 建立辅助数组,记录出现的次数,并初始化(0 次)
        int[] timesOfArray = new int[len + 1];
        for (int i = 0; i < array.length; i++) { 
            // 使用加 1 后的索引,有重复的该位置就自增
            timesOfArray[array[i] - min + 1] ++;
        }
        // 频率 -> 元素的开始索引
        for (int i = 0; i < len; i++) {
            timesOfArray[i + 1] += timesOfArray[i];
        }
        // 元素按照开始索引分类,用到一个和待排数组一样大临时数组存放数据
        int[] aux = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            // 填充一个数据后,自增,以便相同的数据可以填到下一个空位
            aux[timesOfArray[array[i] - min]++] = array[i];
        }
        // 数据回写
        for (int i = 0; i < array.length; i++) {
            array[i] = aux[i];
        }
    }

void countingSort(Integer[] array) {
        // 找出最大值
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if(array[i] > max) max = array[i];
        }
        max ++;
        // 建立辅助数组,记录出现的次数,并初始化(0 次)
        Integer[] timesOfArray = new Integer[max];
        for (int i = 0; i < timesOfArray.length; i++) {              // 运算次数  50 < O(n)
            timesOfArray[i] = 0;
        }
        // 遍历 array 数据,记录出现次数
        for (Integer integer : array) timesOfArray[integer] ++;     // 运算次数  100 = O(n)
        // 遍历 timesOfArray,实现 array 排序
        int j = 0;
        for (int i = 0; i < max; i++) {                          
            int times = timesOfArray[i];
            times += j;
            for (;j < times; j++) array[j] = i;                      // 运算次数  100 = O(n)
        }
    }

排序效果:

桶排序

介绍:

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)

桶排序最好情况下使用线性时间 O(n),桶排序的时间复杂度,取决与对各个桶之间数据进行排序的时间复杂度,因为其它部分的时间复杂度都为 O(n)。很显然,桶划分的越小,各个桶之间的数据越少,排序所用的时间也会越少。但相应的空间消耗就会增大

步骤:

  1. 设置一个定量的数组当作空桶;
  1. 遍历输入数据,并且把数据一个一个放到对应的桶里去;
  1. 对每个不是空的桶进行排序;
  1. 从不是空的桶里把排好序的数据拼接起来。 

代码实现:
排序效果:

基数排序

介绍:

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前

基数排序基于分别排序,分别收集,所以是稳定的。但基数排序的性能比桶排序要略差,每一次关键字的桶分配都需要 O(n)的时间复杂度,而且分配之后得到新的关键字序列又需要 O(n)的时间复杂度。假如待排数据可以分为 d 个关键字,则基数排序的时间复杂度将是 O(d*2n) ,当然 d 要远远小于 n,因此基本上还是线性级别的。

基数排序的空间复杂度为 O(n+k),其中 k 为桶的数量。一般来说 n>>k,因此额外空间需要大概 n 个左右

步骤:

  1. 取得数组中的最大数,并取得位数;
  1. arr 为原始数组,从最低位开始取每个位组成 radix 数组;
  1. 对 radix 进行计数排序(利用计数排序适用于小范围数的特点);

代码实现:
排序效果:


温馨提示:若在升级会员或付费后阅读过程中遇到问题,请加客服微信号(cool-smiler)沟通解决,祝您生活愉快。
转载请注明原文链接:排序算法深入研究
喜欢 (0)
[1186664388@qq.com]
分享 (0)
关于作者:
创享视界(creativeview.cn)是一个带动全民颠覆八小时工作制,通过投稿把自己的创意智慧变现的方式创造被动收入,从而实现财务自由的平台。我们相信,创新思维不仅有助于打造更出色的产品,还可以让世界变得更美好,让人人受益。
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
%d 博主赞过: