排序方法有哪几种，八种经典排序算法介绍
算法和数据结构是一个程序员的内功，所以经常在一些笔试中都会要求手写一些简单的排序算法，以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法，一起学习一下。
一、冒泡排序
思路：
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
排除最大的数，接着下一轮继续相同的操作，确定第二大的数...
重复步骤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)
算法稳定性：稳定
二、插入排序
思路：
从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在前面已排序的元素序列中，从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤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)算法稳定性：稳定
本文地址：网络知识频道 https://www.hkm168.com/jiqiao/868867.html，易企推百科一个免费的知识分享平台，本站部分文章来网络分享，本着互联网分享的精神，如有涉及到您的权益，请联系我们删除，谢谢！
相关阅读
