乐趣区

关于react.js:八种经典排序算法总结

前言

算法和数据结构是一个程序员的内功,所以常常在一些口试中都会要求手写一些简略的排序算法,以此考验面试者的编程程度。上面我就简略介绍八种常见的排序算法,一起学习一下。

一、冒泡排序

思路:

  • 比拟相邻的元素。如果第一个比第二个大,就替换它们两个;
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最初一对,这样在最初的元素就是最大的数;
  • 排除最大的数,接着下一轮持续雷同的操作,确定第二大的数 …
  • 反复步骤 1 -3,直到排序实现。

动画演示:

实现代码:

_/**
 * @author Ye Hongzhi 公众号:java 技术爱好者
 * @name BubbleSort
 * @date 2020-09-05 21:38
 **/_
public class BubbleSort extends BaseSort {public static void main(String[] args) {BubbleSort sort = new BubbleSort();
        sort.printNums();}
    
    @Override
    protected void sort(int[] nums) {if (nums == null || nums.length < 2) {return;}
        for (int i = 0; i < nums.length - 1; i++) {for (int j = 0; j < nums.length - i - 1; j++) {if (nums[j] > nums[j + 1]) {int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }
}
_//10 万个数的数组,耗时:21554 毫秒_

均匀工夫复杂度:O(n²)

空间复杂度:O(1)

算法稳定性:稳固

二、插入排序

思路:

  1. 从第一个元素开始,该元素能够认为曾经被排序;
  2. 取出下一个元素,在后面已排序的元素序列中,从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一地位;
  4. 反复步骤 3,直到找到已排序的元素小于或者等于新元素的地位;
  5. 将新元素插入到该地位后;
  6. 反复步骤 2~5。

动画演示:

实现代码:

_/**
 * @author Ye Hongzhi 公众号:java 技术爱好者
 * @name InsertSort
 * @date 2020-09-05 22:34
 **/_
public class InsertSort extends BaseSort {public static void main(String[] args) {BaseSort sort = new InsertSort();
        sort.printNums();}
    @Override
    protected void sort(int[] nums) {if (nums == null || nums.length < 2) {return;}
        for (int i = 0; i < nums.length - 1; i++) {
            _// 以后值_
            int curr = nums[i + 1];
            _// 上一个数的指针_
            int preIndex = i;
            _// 在数组中找到一个比以后遍历的数小的第一个数_
            while (preIndex >= 0 && curr < nums[preIndex]) {
                _// 把比以后遍历的数大的数字往后挪动_
                nums[preIndex + 1] = nums[preIndex];
                _// 须要插入的数的下标往前挪动_
                preIndex--;
            }
            _// 插入到这个数的前面_
            nums[preIndex + 1] = curr;
        }
    }
}
_//10 万个数的数组,耗时:2051 毫秒_

均匀工夫复杂度:O(n²)

空间复杂度:O(1)

算法稳定性:稳固

三、抉择排序

思路:

第一轮,找到最小的元素,和数组第一个数替换地位。

第二轮,找到第二小的元素,和数组第二个数替换地位 …

直到最初一个元素,排序实现。

动画演示:

实现代码:

_/**
 * @author Ye Hongzhi 公众号:java 技术爱好者
 * @name SelectSort
 * @date 2020-09-06 22:27
 **/_
public class SelectSort extends BaseSort {public static void main(String[] args) {SelectSort sort = new SelectSort();
        sort.printNums();}
    @Override
    protected void sort(int[] nums) {for (int i = 0; i < nums.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < nums.length; j++) {if (nums[j] < nums[minIndex]) {minIndex = j;}
            }
            if (minIndex != i) {int temp = nums[i];
                nums[minIndex] = temp;
                nums[i] = nums[minIndex];
            }
        }
    }
}
_//10 万个数的数组,耗时:8492 毫秒_

算法复杂度:O(n²)
算法空间复杂度:O(1)
算法稳定性:不稳固

四、希尔排序

思路:

把数组宰割成若干 (h) 个小组(个别数组长度 length/2),而后对每一个小组别离进行插入排序。每一轮宰割的数组的个数逐渐放大,h/2->h/4->h/8,并且进行排序,保障有序。当 h = 1 时,则数组排序实现。

动画演示:

实现代码:

_/**
 * @author Ye Hongzhi 公众号:java 技术爱好者
 * @name SelectSort
 * @date 2020-09-06 22:27
 **/_
public class ShellSort extends BaseSort {public static void main(String[] args) {ShellSort sort = new ShellSort();
        sort.printNums();}

    @Override
    protected void sort(int[] nums) {if (nums == null || nums.length < 2) {return;}
        int length = nums.length;
        int temp;
        _// 步长_
        int gap = length / 2;
        while (gap > 0) {for (int i = gap; i < length; i++) {temp = nums[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && nums[preIndex] > temp) {nums[preIndex + gap] = nums[preIndex];
                    preIndex -= gap;
                }
                nums[preIndex + gap] = temp;
            }
            gap /= 2;
        }
    }
}
_//10 万个数的数组,耗时:261 毫秒_

算法复杂度:O(nlog2n)
算法空间复杂度:O(1)
算法稳定性:稳固

五、疾速排序

快排,面试最喜爱问的排序算法。这是使用分治法的一种排序算法。

思路:

  1. 从数组当选一个数做为基准值,个别选第一个数,或者最初一个数。
  2. 采纳双指针 (头尾两端) 遍历,从左往右找到比基准值大的第一个数,从右往左找到比基准值小的第一个数,替换两数地位,直到头尾指针相等或头指针大于尾指针,把基准值与头指针的数替换。这样一轮之后,右边的数就比基准值小,左边的数就比基准值大。
  3. 对右边的数列,反复下面 1,2 步骤。对左边反复 1,2 步骤。
  4. 左右两边数列递归完结后,排序实现。

动画演示:

实现代码:

_/**
 * @author Ye Hongzhi 公众号:java 技术爱好者
 * @name SelectSort
 * @date 2020-09-06 22:27
 **/_
public class QuickSort extends BaseSort {public static void main(String[] args) {QuickSort sort = new QuickSort();
        sort.printNums();}

    @Override
    protected void sort(int[] nums) {if (nums == null || nums.length < 2) {return;}
        quickSort(nums, 0, nums.length - 1);
    }

    private void quickSort(int[] nums, int star, int end) {if (star > end) {return;}
        int i = star;
        int j = end;
        int key = nums[star];
        while (i < j) {while (i < j && nums[j] > key) {j--;}
            while (i < j && nums[i] <= key) {i++;}
            if (i < j) {int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
            }
        }
        nums[star] = nums[i];
        nums[i] = key;
        quickSort(nums, star, i - 1);
        quickSort(nums, i + 1, end);
    }
}
_//10 万个数的数组,耗时:50 毫秒_

算法复杂度:O(nlogn)
算法空间复杂度:O(1)
算法稳定性:不稳固

六、归并排序

归并排序是采纳分治法的典型利用,而且是一种稳固的排序形式,不过须要应用到额定的空间。

思路:

  1. 把数组一直划分成子序列,划成长度只有 2 或者 1 的子序列。
  2. 而后利用长期数组,对子序列进行排序,合并,再把长期数组的值复制回原数组。
  3. 重复操作 1~2 步骤,直到排序实现。

归并排序的长处在于最好状况和最坏的状况的工夫复杂度都是 O(nlogn),所以是比较稳定的排序形式。

动画演示:

实现代码:

_/**
 * @author Ye Hongzhi 公众号:java 技术爱好者
 * @name MergeSort
 * @date 2020-09-08 23:30
 **/_
public class MergeSort extends BaseSort {public static void main(String[] args) {MergeSort sort = new MergeSort();
        sort.printNums();}

    @Override
    protected void sort(int[] nums) {if (nums == null || nums.length < 2) {return;}
        _// 归并排序_
        mergeSort(0, nums.length - 1, nums, new int[nums.length]);
    }

    private void mergeSort(int star, int end, int[] nums, int[] temp) {
        _// 递归终止条件_
        if (star >= end) {return;}
        int mid = star + (end - star) / 2;
        _// 右边进行归并排序_
        mergeSort(star, mid, nums, temp);
        _// 左边进行归并排序_
        mergeSort(mid + 1, end, nums, temp);
        _// 合并左右_
        merge(star, end, mid, nums, temp);
    }

    private void merge(int star, int end, int mid, int[] nums, int[] temp) {
        int index = 0;
        int i = star;
        int j = mid + 1;
        while (i <= mid && j <= end) {if (nums[i] > nums[j]) {temp[index++] = nums[j++];
            } else {temp[index++] = nums[i++];
            }
        }
        while (i <= mid) {temp[index++] = nums[i++];
        }
        while (j <= end) {temp[index++] = nums[j++];
        }
        _// 把长期数组中已排序的数复制到 nums 数组中_
        if (index >= 0) System.arraycopy(temp, 0, nums, star, index);
    }
}
_//10 万个数的数组,耗时:26 毫秒_

算法复杂度:O(nlogn)
算法空间复杂度:O(n)
算法稳定性:稳固

七、堆排序

大顶堆概念:每个节点的值都大于或者等于它的左右子节点的值,所以顶点的数就是最大值。

思路:

  1. 对原数组构建成大顶堆。
  2. 替换头尾值,尾指针索引减一,固定最大值。
  3. 从新构建大顶堆。
  4. 反复步骤 2~3,直到最初一个元素,排序实现。

构建大顶堆的思路,能够看代码正文。

动画演示:

实现代码:

_/**
 * @author Ye Hongzhi 公众号:java 技术爱好者
 * @name HeapSort
 * @date 2020-09-08 23:34
 **/_
public class HeapSort extends BaseSort {public static void main(String[] args) {HeapSort sort = new HeapSort();
        sort.printNums();}

    @Override
    protected void sort(int[] nums) {if (nums == null || nums.length < 2) {return;}
        heapSort(nums);
    }

    private void heapSort(int[] nums) {if (nums == null || nums.length < 2) {return;}
        _// 构建大根堆_
        createTopHeap(nums);
        int size = nums.length;
        while (size > 1) {
            _// 大根堆的替换头尾值,固定最大值在开端_
            swap(nums, 0, size - 1);
            _// 开端的索引值往左减 1_
            size--;
            _// 从新构建大根堆_
            updateHeap(nums, size);
        }
    }

    private void createTopHeap(int[] nums) {for (int i = 0; i < nums.length; i++) {
            _// 以后插入的索引_
            int currIndex = i;
            _// 父节点的索引_
            int parentIndex = (currIndex - 1) / 2;
            _// 如果以后遍历的值比父节点大的话,就替换值。而后持续往下层比拟_
            while (nums[currIndex] > nums[parentIndex]) {
                _// 替换以后遍历的值与父节点的值_
                swap(nums, currIndex, parentIndex);
                _// 把父节点的索引指向以后遍历的索引_
                currIndex = parentIndex;
                _// 往上计算父节点索引_
                parentIndex = (currIndex - 1) / 2;
            }
        }
    }

    private void updateHeap(int[] nums, int size) {
        int index = 0;
        _// 左节点索引_
        int left = 2 * index + 1;
        _// 右节点索引_
        int right = 2 * index + 2;
        while (left < size) {
            _// 最大值的索引_
            int largestIndex;
            _// 如果右节点大于左节点,则最大值索引指向右子节点索引_
            if (right < size && nums[left] < nums[right]) {largestIndex = right;} else {largestIndex = left;}
            _// 如果父节点大于最大值,则把父节点索引指向最大值索引_
            if (nums[index] > nums[largestIndex]) {largestIndex = index;}
            _// 如果父节点索引指向最大值索引,证实曾经是大根堆,退出循环_
            if (largestIndex == index) {break;}
            _// 如果不是大根堆,则替换父节点的值_
            swap(nums, largestIndex, index);
            _// 把最大值的索引变成父节点索引_
            index = largestIndex;
            _// 从新计算左节点索引_
            left = 2 * index + 1;
            _// 从新计算右节点索引_
            right = 2 * index + 2;
        }
    }

    private void swap(int[] nums, int i, int j) {int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}
_//10 万个数的数组,耗时:38 毫秒_

算法复杂度:O(nlogn)
算法空间复杂度:O(1)
算法稳定性:不稳固

八、桶排序

思路:

  1. 找出最大值,最小值。
  2. 依据数组的长度,创立出若干个桶。
  3. 遍历数组的元素,依据元素的值放入到对应的桶中。
  4. 对每个桶的元素进行排序(可应用快排,插入排序等)。
  5. 按程序合并每个桶的元素,排序实现。

对于数组中的元素散布平均的状况,排序效率较高。相同的,如果散布不平均,则会导致大部分的数落入到同一个桶中,使效率升高。

动画演示 (来源于五分钟学算法,侵删):

实现代码:

_/**
 * @author Ye Hongzhi 公众号:java 技术爱好者
 * @name BucketSort
 * @date 2020-09-08 23:37
 **/_
public class BucketSort extends BaseSort {public static void main(String[] args) {BucketSort sort = new BucketSort();
        sort.printNums();}

    @Override
    protected void sort(int[] nums) {if (nums == null || nums.length < 2) {return;}
        bucketSort(nums);
    }

    public void bucketSort(int[] nums) {if (nums == null || nums.length < 2) {return;}
        _// 找出最大值,最小值_
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int num : nums) {min = Math.min(min, num);
            max = Math.max(max, num);
        }
        int length = nums.length;
        _// 桶的数量_
        int bucketCount = (max - min) / length + 1;
        int[][] bucketArrays = new int[bucketCount][];
        _// 遍历数组,放入桶内_
        for (int i = 0; i < length; i++) {
            _// 找到桶的下标_
            int index = (nums[i] - min) / length;
            _// 增加到指定下标的桶里,并且应用插入排序排序_
            bucketArrays[index] = insertSortArrays(bucketArrays[index], nums[i]);
        }
        int k = 0;
        _// 合并全副桶的_
        for (int[] bucketArray : bucketArrays) {if (bucketArray == null || bucketArray.length == 0) {continue;}
            for (int i : bucketArray) {
                _// 把值放回到 nums 数组中_
                nums[k++] = i;
            }
        }
    }

    _// 每个桶应用插入排序进行排序_
    private int[] insertSortArrays(int[] arr, int num) {if (arr == null || arr.length == 0) {return new int[]{num};
        }
        _// 创立一个 temp 数组,长度是 arr 数组的长度 +1_
        int[] temp = new int[arr.length + 1];
        _// 把传进来的 arr 数组,复制到 temp 数组_
        for (int i = 0; i < arr.length; i++) {temp[i] = arr[i];
        }
        _// 找到一个地位,插入,造成新的有序的数组_
        int i;
        for (i = temp.length - 2; i >= 0 && temp[i] > num; i--) {temp[i + 1] = temp[i];
        }
        _// 插入须要增加的值_
        temp[i + 1] = num;
        _// 返回_
        return temp;
    }
}
_//10 万个数的数组,耗时:8750 毫秒_

算法复杂度:O(M+N)

算法空间复杂度:O(M+N)

算法稳定性:稳固(取决于桶内的排序算法,这里应用的是插入排序所以是稳固的)。

总结


动画演示来源于算法学习网站:https://visualgo.net

讲完这些排序算法后,可能有人会问学这些排序算法有什么用呢,难道就为了应酬口试面试?平时开发也没用得上这些。

我感觉咱们应该换个角度来看,比方高中时咱们学物理,化学,数学,那么多公式定理,当初也没怎么用得上,然而高中课本为什么要教这些呢?

我的了解是:第一,遍及一些常识性的问题。第二,锤炼思维,进步解决问题的能力。第三,为了辨别人才。

回到学排序算法有什么用的问题上,实际上也一样。这些最根本的排序算法就是一些常识性的问题,作为开发者应该理解把握。同时也锤炼了编程思维,其中蕴含有双指针,分治,递归等等的思维。最初在面试中体现进去的就是人才的划分,懂得这些根本的排序算法当然要比不懂的人要更有竞争力。

原文链接
本文为阿里云原创内容,未经容许不得转载。

退出移动版