排序方法有哪几种，八种经典排序算法介绍

五、快速排序

快排，面试最喜欢问的排序算法。这是运用分治法的一种排序算法。

思路：

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  nums[j]) {                temp[index++] = nums[j++];            } else {                temp[index++] = nums[i++];            }        }        while (i <= mid) {            temp[index++] = nums[i++];        }        while (j = 0) System.arraycopy(temp, 0, nums, star, index);    }}//10万个数的数组，耗时：26毫秒

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

七、堆排序

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

思路：

1. 对原数组构建成大顶堆。

2. 交换头尾值，尾指针索引减一，固定最大值。

3. 重新构建大顶堆。

4. 重复步骤2~3，直到最后一个元素，排序完成。

构建大顶堆的思路，可以看代码注释。

动画演示：

本文地址：网络知识频道 https://www.hkm168.com/jiqiao/868867_2.html，易企推百科一个免费的知识分享平台，本站部分文章来网络分享，本着互联网分享的精神，如有涉及到您的权益，请联系我们删除，谢谢！