八种经典排序算法总结，妈妈再也不用担心我不会了
myzbx 2025-07-02 23:17 22 浏览
前言
算法和数据结构是一个程序员的内功，所以经常在一些笔试中都会要求手写一些简单的排序算法，以此考验面试者的编程水平。下面我就简单介绍八种常见的排序算法，一起学习一下。
一、冒泡排序
思路：
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素就是最大的数；
- 排除最大的数，接着下一轮继续相同的操作，确定第二大的数...
- 重复步骤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^2)
空间复杂度：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^2)
空间复杂度：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^2)
算法空间复杂度：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步骤。对右边重复1，2步骤。
- 左右两边数列递归结束后，排序完成。
动画演示：
实现代码：
/**
* @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)
算法稳定性：不稳定
六、归并排序
归并排序是采用分治法的典型应用，而且是一种稳定的排序方式，不过需要使用到额外的空间。
思路：
- 把数组不断划分成子序列，划成长度只有2或者1的子序列。
- 然后利用临时数组，对子序列进行排序，合并，再把临时数组的值复制回原数组。
- 反复操作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)
算法稳定性：稳定
七、堆排序
大顶堆概念：每个节点的值都大于或者等于它的左右子节点的值，所以顶点的数就是最大值。
思路：
- 对原数组构建成大顶堆。
- 交换头尾值，尾指针索引减一，固定最大值。
- 重新构建大顶堆。
- 重复步骤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)
算法稳定性：不稳定
八、桶排序
思路：
- 找出最大值，最小值。
- 根据数组的长度，创建出若干个桶。
- 遍历数组的元素，根据元素的值放入到对应的桶中。
- 对每个桶的元素进行排序(可使用快排，插入排序等)。
- 按顺序合并每个桶的元素，排序完成。
对于数组中的元素分布均匀的情况，排序效率较高。相反的，如果分布不均匀，则会导致大部分的数落入到同一个桶中，使效率降低。
动画演示(来源于五分钟学算法，侵删)：
实现代码：
/**
* @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)
算法稳定性：稳定(取决于桶内的排序算法，这里使用的是插入排序所以是稳定的)。
总结
讲完这些排序算法后，可能有人会问学这些排序算法有什么用呢，难道就为了应付笔试面试？平时开发也没用得上这些。
我觉得我们应该换个角度来看，比如高中时我们学物理，化学，数学，那么多公式定理，现在也没怎么用得上，但是高中课本为什么要教这些呢？
我的理解是：第一，普及一些常识性的问题。第二，锻炼思维，提高解决问题的能力。第三，为了区分人才。
回到学排序算法有什么用的问题上，实际上也一样。这些最基本的排序算法就是一些常识性的问题，作为开发者应该了解掌握。同时也锻炼了编程思维，其中包含有双指针，分治，递归等等的思想。最后在面试中体现出来的就是人才的划分，懂得这些基本的排序算法当然要比不懂的人要更有竞争力。
建议大家看完之后，能找时间动手写一下，加深理解。
本文为阿里云原创内容，未经允许不得转载。
相关推荐
- 如何设计一个优秀的电子商务产品详情页
-
加入人人都是产品经理【起点学院】产品经理实战训练营，BAT产品总监手把手带你学产品电子商务网站的产品详情页面无疑是设计师和开发人员关注的最重要的网页之一。产品详情页面是客户作出“加入购物车”决定的页面...
- 怎么在JS中使用Ajax进行异步请求?
-
大家好，今天我来分享一项JavaScript的实战技巧，即如何在JS中使用Ajax进行异步请求，让你的网页速度瞬间提升。Ajax是一种在不刷新整个网页的情况下与服务器进行数据交互的技术，可以实现异步加...
- 中小企业如何组建,管理团队_中小企业应当如何开展组织结构设计变革
-
前言写了太多关于产品的东西觉得应该换换口味.从码农到架构师,从前端到平面再到UI、UE,最后走向了产品这条不归路,其实以前一直再给你们讲.产品经理跟项目经理区别没有特别大,两个岗位之间有很...
- 前端监控 SDK 开发分享_前端监控系统 开源
-
一、前言随着前端的发展和被重视，慢慢的行业内对于前端监控系统的重视程度也在增加。这里不对为什么需要监控再做解释。那我们先直接说说需求。对于中小型公司来说，可以直接使用三方的监控，比如自己搭建一套免费的...
- Ajax 会被 fetch 取代吗?Axios 怎么办?
-
大家好，很高兴又见面了，我是"高级前端进阶"，由我带着大家一起关注前端前沿、深入前端底层技术，大家一起进步，也欢迎大家关注、点赞、收藏、转发！今天给大家带来的主题是ajax、fetch...
- 前端面试题《AJAX》_前端面试ajax考点汇总
-
1.什么是ajax？ajax作用是什么？AJAX=异步JavaScript和XML。AJAX是一种用于创建快速动态网页的技术。通过在后台与服务器进行少量数据交换,AJAX可以使网页实...
- Ajax 详细介绍_ajax
-
1、ajax是什么?asynchronousjavascriptandxml:异步的javascript和xml。ajax是用来改善用户体验的一种技术，其本质是利用浏览器内置的一个特殊的...
- 6款可替代dreamweaver的工具_替代powerdesigner的工具
-
dreamweaver对一个web前端工作者来说，再熟悉不过了，像我07年接触web前端开发就是用的dreamweaver，一直用到现在，身边的朋友有跟我推荐过各种更好用的可替代dreamweaver...
- 我敢保证，全网没有再比这更详细的Java知识点总结了，送你啊
-
接下来你看到的将是全网最详细的Java知识点总结，全文分为三大部分：Java基础、Java框架、Java+云数据小编将为大家仔细讲解每大部分里面的详细知识点，别眨眼，从小白到大佬、零基础到精通，你绝...
- 福斯《死侍》发布新剧照 "小贱贱"韦德被改造前造型曝光
-
时光网讯福斯出品的科幻片《死侍》今天发布新剧照，其中一张是较为罕见的死侍在被改造之前的剧照，其余两张剧照都是死侍在执行任务中的状态。据外媒推测，片方此时发布剧照，预计是为了给不久之后影片发布首款正式预...
- 2021年超详细的java学习路线总结—纯干货分享
-
本文整理了java开发的学习路线和相关的学习资源，非常适合零基础入门java的同学，希望大家在学习的时候，能够节省时间。纯干货，良心推荐！第一阶段：Java基础重点知识点：数据类型、核心语法、面向对象...
- 不用海淘，真黑五来到你身边:亚马逊15件热卖爆款推荐!
-
Fujifilm富士instaxMini8小黄人拍立得相机（黄色/蓝色）扫二维码进入购物页面黑五是入手一个轻巧可爱的拍立得相机的好时机，此款是mini8的小黄人特别版，除了颜色涂装成小黄人...
- 2025 年 Python 爬虫四大前沿技术:从异步到 AI
-
作为互联网大厂的后端Python爬虫开发，你是否也曾遇到过这些痛点：面对海量目标URL，单线程爬虫爬取一周还没完成任务；动态渲染的SPA页面，requests库返回的全是空白代码；好不容易...
- 最贱超级英雄《死侍》来了!_死侍超燃
-
死侍Deadpool(2016)导演:蒂姆·米勒编剧:略特·里斯/保罗·沃尼克主演:瑞恩·雷诺兹/莫蕾娜·巴卡林/吉娜·卡拉诺/艾德·斯克林/T·J·米勒类型:动作/...
- 停止javascript的ajax请求，取消axios请求，取消reactfetch请求
-
一、Ajax原生里可以通过XMLHttpRequest对象上的abort方法来中断ajax。注意abort方法不能阻止向服务器发送请求，只能停止当前ajax请求。停止javascript的ajax请求...
- 一周热门
- 最近发表
- 标签列表
-
- HTML 简介 (30)
- HTML 响应式设计 (31)
- HTML URL 编码 (32)
- HTML Web 服务器 (31)
- HTML 表单属性 (32)
- HTML 音频 (31)
- HTML5 支持 (33)
- HTML API (36)
- HTML 总结 (32)
- HTML 全局属性 (32)
- HTML 事件 (31)
- HTML 画布 (32)
- HTTP 方法 (30)
- 键盘快捷键 (30)
- CSS 语法 (35)
- CSS 轮廓宽度 (31)
- CSS 谷歌字体 (33)
- CSS 链接 (31)
- CSS 定位 (31)
- CSS 图片库 (32)
- CSS 图像精灵 (31)
- SVG 文本 (32)
- 时钟启动 (33)
- HTML 游戏 (34)
- JS Loop For (32)