经典排序算法有哪些？排序算法大全

港控/mmm° 2022-12-26 09:28 144阅读 0赞

# 前言 #

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

# 一、冒泡排序 #

思路：

*  比较相邻的元素。如果第一个比第二个大，就交换它们两个；
 *  对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
 *  排除最大的数，接着下一轮继续相同的操作，确定第二大的数...
 *  重复步骤1-3，直到排序完成。

动画演示：

![在这里插入图片描述][20200911232356915.gif_pic_center]

实现代码：

/**
     * @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。

动画演示：

![在这里插入图片描述][20200911232417555.gif_pic_center]

实现代码：

/**
     * @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)**

算法稳定性：稳定

# 三、选择排序 #

思路：

第一轮，找到最小的元素，和数组第一个数交换位置。

第二轮，找到第二小的元素，和数组第二个数交换位置...

直到最后一个元素，排序完成。

动画演示：  
![在这里插入图片描述][20200911232439594.gif_pic_center]  
实现代码：

/**
     * @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时，则数组排序完成。

动画演示：  
![在这里插入图片描述][20200911232456961.gif_pic_center]  
实现代码：

/**
     * @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.  左右两边数列递归结束后，排序完成。

动画演示：  
![在这里插入图片描述][20200911232516224.gif_pic_center]  
实现代码：

/**
     * @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)，所以是比较稳定的排序方式。

动画演示：  
![在这里插入图片描述][20200911232533783.gif_pic_center]  
实现代码：

/**
     * @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)**  
算法稳定性：稳定

# 七、堆排序 #

大顶堆概念：每个节点的值都大于或者等于它的左右子节点的值，所以顶点的数就是最大值。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3llaG9uZ3poaTE5OTQ_size_16_color_FFFFFF_t_70_pic_center]  
思路：

1.  对原数组构建成大顶堆。
2.  交换头尾值，尾指针索引减一，固定最大值。
3.  重新构建大顶堆。
4.  重复步骤2~3，直到最后一个元素，排序完成。

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

动画演示：  
![在这里插入图片描述][20200911232603224.gif_pic_center]  
实现代码：

/**
     * @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.  按顺序合并每个桶的元素，排序完成。

对于数组中的元素分布均匀的情况，排序效率较高。相反的，如果分布不均匀，则会导致大部分的数落入到同一个桶中，使效率降低。

动画演示(来源于五分钟学算法，侵删)：  
![在这里插入图片描述][20200911232658767.gif_pic_center]  
实现代码：

/**
     * @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)**

算法稳定性：稳定(取决于桶内的排序算法，这里使用的是插入排序所以是稳定的)。

# 总结 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3llaG9uZ3poaTE5OTQ_size_16_color_FFFFFF_t_70_pic_center 1]  
动画演示来源于算法学习网站：[https://visualgo.net][https_visualgo.net]

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

我觉得我们应该换个角度来看，比如高中时我们学物理，化学，数学，那么多公式定理，现在也没怎么用得上，但是高中课本为什么要教这些呢？

我的理解是：第一，普及一些常识性的问题。第二，锻炼思维，提高解决问题的能力。第三，为了区分人才。

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

建议大家看完之后，能找时间动手写一下，加深理解。

[20200911232356915.gif_pic_center]: /images/20221120/5309f1a1f4454395917e1407fe1866ae.png
[20200911232417555.gif_pic_center]: /images/20221120/3e88e3cc4cdb406eb562b9b891f5e559.png
[20200911232439594.gif_pic_center]: /images/20221120/d0c361b5375b4d758387e202587d5b8b.png
[20200911232456961.gif_pic_center]: /images/20221120/2e44311c903a4c99a911786ba84bedfe.png
[20200911232516224.gif_pic_center]: /images/20221120/9e7ff347002d49cca8007baf41bba5a2.png
[20200911232533783.gif_pic_center]: /images/20221120/e862f54a2b654e99bece7f59ea4ee07c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3llaG9uZ3poaTE5OTQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/abd07610bd9c4c148e3211c51b36a24d.png
[20200911232603224.gif_pic_center]: /images/20221120/74c3ca8438884cdfbeef8061ce2c184b.png
[20200911232658767.gif_pic_center]: /images/20221120/bf6a62843b2c48848ecde0d1cdb9f7eb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3llaG9uZ3poaTE5OTQ_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/6256e89c17174c12a8b7fb6755e899f0.png
[https_visualgo.net]: https://visualgo.net/