## 史上最全经典排序算法总结(Java实现)
查找和排序算法是算法的入门知识,其经典思想可以用于很多算法当中。因为其实现代码较短,应用较常见。所以在面试中经常会问到排序算法及其相关的问题。但万变不离其宗,只要熟悉了思想,灵活运用也不是难事。一般在面试中最常考的是快速排序和归并排序,并且经常有面试官要求现场写出这两种排序的代码。对这两种排序的代码一定要信手拈来才行。还有插入排序、冒泡排序、堆排序、基数排序、桶排序等。面试官对于这些排序可能会要求比较各自的优劣、各种算法的思想及其使用场景。还有要会分析算法的时间和空间复杂度。通常查找和排序算法的考察是面试的开始,如果这些问题回答不好,估计面试官都没有继续面试下去的兴趣都没了。所以想开个好头就要把常见的排序算法思想及其特点要熟练掌握,有必要时要熟练写出代码。下面主要介绍经典排序算法。
### 0、排序算法说明
#### 0.1 **排序的定义**
对一序列对象根据某个关键字进行排序。
#### 0.2 术语说明
- **稳定**:如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
- **不稳定**:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面;
- **内排序**:所有排序操作都在内存中完成;
- **外排序**:由于数据太大,因此把数据放在磁盘中,而排序通过磁盘和内存的数据传输才能进行;
- **时间复杂度:** 一个算法执行所耗费的时间。
- **空间复杂度**:运行完一个程序所需内存的大小。
#### 0.3 算法总结
![算法总结](https://raw.githubusercontent.com/JourWon/image/master/史上最全经典排序算法总结(Java实现)/算法总结.jpg)
**图片名词解释:**
- n: 数据规模
- k: “桶”的个数
- In-place: 占用常数内存,不占用额外内存
- Out-place: 占用额外内存
#### 0.4 算法分类
![算法分类](https://raw.githubusercontent.com/JourWon/image/master/史上最全经典排序算法总结(Java实现)/算法分类.jpg)
#### 0.5 比较和非比较的区别
常见的**快速排序、归并排序、堆排序、冒泡排序**等属于**比较排序**。**在排序的最终结果里,元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较,才能确定自己的位置。**
在**冒泡排序**之类的排序中,问题规模为n,又因为需要比较n次,所以平均时间复杂度为O(n²)。在**归并排序、快速排序**之类的排序中,问题规模通过**分治法**消减为logN次,所以时间复杂度平均**O(nlogn)**。
比较排序的优势是,适用于各种规模的数据,也不在乎数据的分布,都能进行排序。可以说,**比较排序适用于一切需要排序的情况。**
**计数排序、基数排序、桶排序**则属于**非比较排序**。非比较排序是通过确定每个元素之前,应该有多少个元素来排序。针对数组arr,计算arr[i]之前有多少个元素,则唯一确定了arr[i]在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可,所有一次遍历即可解决。算法时间复杂度**O(n)**。
**非比较排序时间复杂度底,但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。**
------
下面的排序算法统一使用的测试代码如下,[源码GitHub链接](https://github.com/JourWon/sort-algorithm)
```java
public static void main(String[] args) {
int[] array = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
// 只需要修改成对应的方法名就可以了
bubbleSort(array);
System.out.println(Arrays.toString(array));
}
```
### 1、冒泡排序(Bubble Sort)
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
#### 1.1 算法描述
- 比较相邻的元素。如果第一个比第二个大,就交换它们两个;
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对,这样在最后的元素应该会是最大的数;
- 针对所有的元素重复以上的步骤,除了最后一个;
- 重复步骤1~3,直到排序完成。
**1.2 动图演示**
![冒泡排序](https://raw.githubusercontent.com/JourWon/image/master/史上最全经典排序算法总结(Java实现)/冒泡排序.gif)
#### 1.3 代码实现
```java
/**
* Description:冒泡排序
*
* @param array 需要排序的数组
* @author JourWon
* @date 2019/7/11 9:54
*/
public static void bubbleSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
// 外层循环控制比较轮数i
for (int i = 0; i < length; i++) {
// 内层循环控制每一轮比较次数,每进行一轮排序都会找出一个较大值
// (array.length - 1)防止索引越界,(array.length - 1 - i)减少比较次数
for (int j = 0; j < length - 1 - i; j++) {
// 前面的数大于后面的数就进行交换
if (array[j] > array[j + 1]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
}
```
#### 1.4 **算法分析**
**最佳情况:T(n) = O(n) 最差情况:T(n) = O(n2) 平均情况:T(n) = O(n2)**
### 2、选择排序(Selection Sort)
表现**最稳定的排序算法之一**,因为**无论什么数据进去都是O(n2)的时间复杂度**,所以用到它的时候,数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲,选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
#### 2.1 算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下:
- 初始状态:无序区为R[1..n],有序区为空;
- 第i趟排序(i=1,2,3…n-1)开始时,当前有序区和无序区分别为R[1..i-1]和R(i..n)。该趟排序从当前无序区中-选出关键字最小的记录 R[k],将它与无序区的第1个记录R交换,使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区;
- n-1趟结束,数组有序化了。
#### **2.2 动图演示**
![选择排序](https://raw.githubusercontent.com/JourWon/image/master/史上最全经典排序算法总结(Java实现)/选择排序.gif)
#### 2.3 代码实现
```java
/**
* Description: 选择排序
*
* @param array
* @return void
* @author JourWon
* @date 2019/7/11 23:31
*/
public static void selectionSort(int[] array) {
if (array == null || array.length <= 1) {
return;
}
int length = array.length;
for (int i = 0; i < length - 1; i++) {
// 保存最小数的索引
int minIndex = i;
for (int j = i + 1; j < length; j++) {
// 找到最小的数
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
// 交换元素位置
if (i != minIndex) {
swap(array, minIndex, i);
}
}
}
/**
* Description: 交换元素位置
*
* @param array
* @param a
* @param b
* @return void
* @author JourWon
* @date 2019/7/11 17:57
*/
private static
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
Java是一种高性能、跨平台的面向对象编程语言。它由Sun Microsystems(现在是Oracle Corporation)的James Gosling等人在1995年推出,被设计为一种简单、健壮、可移植、多线程、动态的语言。Java的主要特点和优势包括以下几个方面: 跨平台性(Write Once, Run Anywhere): Java的代码可以在不同的平台上运行,只需编写一次代码,就可以在任何支持Java的设备上执行。这得益于Java虚拟机(JVM),它充当了代码和底层硬件之间的中介。 面向对象: Java是一种纯粹的面向对象编程语言,支持封装、继承和多态等面向对象的概念。这使得Java编写的代码更加模块化、可维护和可扩展。 多线程支持: Java内置了对多线程的支持,允许程序同时执行多个任务。这对于开发需要高并发性能的应用程序(如服务器端应用、网络应用等)非常重要。 自动内存管理(垃圾回收): Java具有自动内存管理机制,通过垃圾回收器自动回收不再使用的对象,使得开发者不需要手动管理内存,减轻了程序员的负担,同时也减少了内存泄漏的风险。
资源推荐
资源详情
资源评论
收起资源包目录
史上最全经典排序算法总结(Java实现).zip (45个子文件)
SJT-code
pom.xml 439B
sort-algorithm.iml 80B
src
main
java
com
jourwon
sort
HeapSort.java 3KB
SelectionSort.java 3KB
CountingSort.java 3KB
QuickSort.java 3KB
RadixSort.java 4KB
BucketSort.java 4KB
ShellSort.java 3KB
InsertionSort.java 2KB
BubbleSort.java 2KB
MergeSort.java 3KB
.idea
dictionaries
JourWon.xml 86B
codeStyles
codeStyleConfig.xml 149B
Project.xml 315B
vcs.xml 180B
workspace.xml 23KB
misc.xml 4KB
inspectionProfiles
Project_Default.xml 1KB
compiler.xml 598B
sonarlint
issuestore
e
1
e1766056aa26c116b07f805ebd7dd977f8c28cfb 86B
4
e4d8460f22ade3e5774b3a35b34eb0813f77150a 86B
8
9
892955fafe37fb088a9ed7bb9aad572644f4beab 86B
c
f
cfc5f1d6b01788778f802dc3b9069eb5b9910398 86B
index.pb 1019B
9
9
991efbc9e0018f4453429a31d87be8798f585569 86B
1
0
10d191ac5d338a084d25c650ec52b7ff37fa364e 86B
f
1
f11e536336278ee35c6e6e4f7e0105daa97e1377 226B
5
d
5dad41653cc4004fe8cd2b6e3e71801fb946d1d4 149B
4
4
44a3499226bcaa278aa79ec56e64638547e8f279 86B
442292b8a7efeabbe4cc176709b833b1792140ec 0B
3
3
33f0d976dce602912cadd82b6b0f1a14395f906d 86B
encodings.xml 270B
target
classes
META-INF
sort-algorithm.kotlin_module 16B
com
jourwon
sort
RadixSort.class 2KB
SelectionSort.class 1KB
BubbleSort.class 1KB
MergeSort.class 2KB
CountingSort.class 1KB
HeapSort.class 1KB
BucketSort.class 2KB
InsertionSort.class 1KB
QuickSort.class 1KB
ShellSort.class 1KB
README.md 30KB
共 45 条
- 1
资源评论
JJJ69
- 粉丝: 6165
- 资源: 5674
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功