微信公众号：一起学习大数据呀
关注可学习更多奇怪的知识！
前言
本文收集整理常见的十大排序算法，配套 Java 代码和视频短视频教程。帮助小伙伴们更快的理解和掌握。
不管你是为了应付考试，还是面试用，本文都可以帮到你，降低学习门槛，作者水平有限，难免遗漏错误，欢迎读者们留言指正。
算法目录
- 冒泡排序
- 选择排序
- 插入排序
- 快速排序
- 希尔排序
- 归并排序
- 堆排序
- 计数排序
- 桶排序
- 基数排序
1、冒泡排序
基本思想
每次比较两个相邻的元素，若顺序（从小到大或从大到小）“错误”就交换位置。
视频讲解
代码实现
public static void bubbleSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
// 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
boolean flag = true;
for (int j = 0; j < arr.length - i; j++) {
if (arr[j] > arr[j + 1]) { //前面的数字大于后面的数字就交换
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = false;
}
}
if (flag) { //没有数据交换，数组已经有序，退出排序
break;
}
}
}
image.gif
2、选择排序
基本思想
每一趟从待排序的记录中选出最大（小）的元素，顺序放在已排好序的序列最后，直到全部记录排序完毕。
视频讲解
代码实现
//1 找到数组最大的数字,并且返回下标
public static int findMaxPos(int[] arr , int n){
int max = arr[0];
int pos = 0;
for (int i = 0; i < n; i++){
if (max < arr[i]){
max = arr[i];
pos = i;
}
}
return pos;
}
//2 让最大值与最后一个元素交换
public static void selectionSort(int[] arr, int n){
while(n > 1) { // 3 不断循环 1 和 2 步骤
int pos = findMaxPos(arr, n);
int temp = 0;
temp = arr[n - 1];
arr[n - 1] = arr[pos];
arr[pos] = temp;
n-- ;
}
}
image.gif
3、插入排序
基本思想
将数组分为“已排序区间”和“未排序区间”。核心思想是提取“未排序区间”中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。重复该过程，直到排序区间中元素为空。
视频讲解
代码实现
//1 选择已排序区间的后一个元宵插入
public void insert(int[] arr, int n){
int key = arr[n];
int i = n;
while (arr[i - 1] > key){ //若前面的元素 > 后面元素
arr[i] = arr[i -1]; // 前面元素抄写到后面元素位置
i--;
if (i == 0){//防止数组越界
break;
}
}
arr[i] = key; // 把要插入的元素归位
}
// 2 多趟插入
public void insertSort(int[] arr, int n){
if (n <= 1){
return ;
}
for (int i = 1; i < n; i++){ // 从第二个元素开始，第一个看成有序区域就好
insert(arr, i);
}
}
image.gif
4、快速排序
基本思想
基本思想:在数组中找到一个基准数,一般来说选第一个,然后加两个哨兵, i 和 j ,一个头一个尾.
i 从左到右扫描遇到大于 基准数 的数字停下, j 从右到左扫描,遇到小于 基准数 的停下.
然后 i 坐标的数与 j 坐标的数交换.
视频讲解
代码实现
static void qucikSort(int left, int right) {
if (left > right){
return;
}
int i = left;
int j = right;
int povit = arr[left]; // 基准数
int temp;
while (i != j) {
while (arr[j] >= povit && i < j) {
j--;
}
while (arr[i] <= povit && i < j) {
i++;
}
if (i < j) {
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
//基准数归位
arr[left] = arr[i];
arr[i] = povit;
//递归
qucikSort(left, i - 1);
qucikSort(i + 1, right);
return;
}
image.gif
- 基准数优化
随机取基准数
三位数取中: 选取数组开头，中间和结尾的元素，通过比较，选择中间的值作为快排的基准。 - 序列长度达到一定大小时，使用插入排序
- 尾递归优化
- 聚集元素
5、希尔排序
基本思想
希尔排序是插入排序的一种改进版，通过比较相距一定距离（增量）的元素工作（交换；各趟比较所用的距离随着算法减小而减小，当增量减至1时，整个文件恰被分成一组，算法便终止。
视频讲解
代码实现
public class ShellSort {
public static void main(String[] args) {
int[] arr = {1, 3, 7, 2, 8, 6, 4, 9};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 希尔排序 针对有序序列在插入时采用移动法。
*
* @param arr
*/
static void shellSort(int[] arr) {
//增量 gap，并逐步缩小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//从第 gap 个元素，逐个对其所在组进行直接插入排序操作
for (int i = gap; i < arr.length; i++) {
int j = i;
int temp = arr[j];
//j - gap 同组相隔的元素没数组越界；
//arr[j - gap] > temp 前面的元素 > 后面的元素
while (j - gap >= 0 && arr[j - gap] > temp) {
//把前面元素抄写到后面的位置
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
}
image.gif
6、归并排序
基本思想
该算法采用经典的分治（divide-and-conquer）策略，它将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之。
视频讲解
代码实现
public class MergeSort {
public static void main(String[] args) {
int[] a = {6, 8, 10, 9, 4, 5, 2, 7};
int L = 0;
int R = a.length - 1;
mergSort(a, L, R);
System.out.println(Arrays.toString(a));
}
static void mergSort(int[] arr, int L, int R) {
// 递归出口
if (L == R) {
return;
} else {
int M = (L + R) / 2;
mergSort(arr, L, M);
mergSort(arr, M + 1, R);
merge(arr, L, M + 1, R);
}
}
static void merge(int[] arr, int L, int M, int R) {
int left_size = M - L;
int right_size = R - M + 1;
int[] L_arr = new int[left_size];
int[] R_arr = new int[right_size];
// 1 填充左边的数组
for (int i = L; i < M; i++) {
L_arr[i - L] = arr[i];
}
// 2 右边填充数组
for (int i = M; i <= R; i++) {
R_arr[i - M] = arr[i];
}
// 3 合并
int i = 0, j = 0, k = L;
while (i < left_size && j < right_size) {
if (L_arr[i] > R_arr[j]) {
arr[k] = R_arr[j];
k++;
j++;
} else {
arr[k] = L_arr[i];
i++;
k++;
}
}
// 4 若右边数组已空,把剩余左边数组补上
while (i < left_size) {
arr[k] = L_arr[i];
i++;
k++;
}
// 5 若左边数组已空,同上
while (j < right_size) {
arr[k] = R_arr[j];
k++;
j++;
}
}
}
image.gif
7、堆排序
基本思想
1）将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
2）将其与末尾元素进行交换，此时末尾就为最大值。
3）将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了。
视频讲解
代码实现
public class HeapSort {
public static void main(String[] args) {
int[] arr = {2,5,3,1,10,4};
heapSort(arr,arr.length);
for (int i : arr){
System.out.println(i + " ");
}
}
/***
* 交换函数
* @param arr
* @param i
* @param j
*/
static void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/***
* 构建大顶堆 (父节点大于子节点)
* @param tree 数组(树)
* @param n 数组长度
* @param i 父节点
*/
static void heapify(int tree[], int n, int i){
// 递归出口
if (i >= n){
return;
}
//左孩子节点
int c1 = 2*i + 1;
//右孩子节点
int c2 = 2*i + 2;
// 假设 i 为最大值
int max = i;
// c1 < n 保证 c1 不出界
if (c1 < n && tree[c1] > tree[max]){
max = c1;
}
if (c2 < n && tree[c2] > tree[max]){
max = c2;
}
if (max != i){
swap(tree, max, i);
heapify(tree, n, max);
}
}
/***
* 自下而上构建堆
* @param tree 数组
* @param n 数组长度
*/
static void buidHeap(int[] tree, int n){
// 最后一个叶子节点
int last_node = n - 1;
// 对应的父节点
int parent = (last_node - 1)/2;
for (int i = parent; i >= 0 ; i--){
heapify(tree, n, i);
}
}
/***
* 堆排序
* @param tree
* @param n
*/
static void heapSort(int[] tree, int n){
// 1) 建一个堆
buidHeap(tree, n);
// 2) 从最后一个节点出发
for (int i = n - 1; i >= 0; i--){
// 3) 先交换一下根节点和最后一个节点
// i 表示最后一个节点
// 0 表示根节点
swap(tree, i, 0);
heapify(tree, i, 0);
}
}
}
image.gif
8、计数排序
基本思想
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
注意：适合量大且范围小的数据
视频讲解
代码实现
public class CountSort {
public static void main(String[] args) {
int[] arr = {2 , 4, 2, 3, 7, 1, 1, 0, 0, 5, 6, 3, 7, 8, 9 };
System.out.println(Arrays.toString(countSort(arr)));
}
/***
* 计数排序
* @param arr
* @return
*/
static int[] countSort(int[] arr) {
//目标数组
int[] result = new int[arr.length];
//计数数组
int[] count = new int[10];
//对原数组记录各元素出现的次数
for (int i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
System.out.println(Arrays.toString(count));
//累加数组 看视频吧，我解释不了
for (int i = 1; i < count.length; i++) {
count[i] = count[i] + count[i - 1];
}
System.out.println(Arrays.toString(count));
//有点像众神归位
for (int i = arr.length - 1; i >= 0; i--) {
result[--count[arr[i]]] = arr[i];
}
return result;
}
}
image.gif
9、桶排序
基本思想
1）将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行快速排序。
2）桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
视频讲解
代码实现
static void bucketSort(int[] arr) {
//找到数组的最大值和最小值，用来计算映射函数
int min = arr[0];
int max = arr[0];
for (int i = 0; i < arr.length; i++) {
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
//计算出桶的数量
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for (int i = 0; i < bucketNum; i++) {
bucketArr.add(new ArrayList<Integer>());
}
//将属于同一个桶的元素放入对应的桶
for (int i = 0; i < arr.length; i++) {
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
//对每个桶进行排序
for (int i = 0; i < bucketArr.size(); i++) {
Collections.sort(bucketArr.get(i));
}
System.out.println(bucketArr.toString());
}
image.gif
10、基数排序
基本思想
桶思想的一种，非比较排序，多关键字排序。
对数据的每一位（个位，十位，百位）进行桶排序或计数排序，对每位排序后结果就是有序的。
视频讲解
**代码实现
public class RadixSort {
public static void main(String[] args) {
int[] arr = {421, 240, 115, 532, 305, 430, 324};
//1 先求最高位数
int maxDigit = getMaxDigit(arr);
System.out.println(Arrays.toString(radixSort(arr, maxDigit)));
}
/**
* 获取最高位数
*/
private static int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLenght(maxValue);
}
private static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
static int getNumLenght(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
static int[] radixSort(int[] arr, int maxDigit) {
int[] result = new int[arr.length];
int[] count = new int[10];
// maxDigit 是数字中最大的位数
for (int i = 0; i < maxDigit; i++) {
//求余数，如个位，十位
int division = (int) Math.pow(10, i);
System.out.println(division);
for (int j = 0; j < arr.length; j++) {
int num = arr[j] / division % 10;
System.out.println(num + " ");
count[num]++;
}
//跟计数排序一样，先做累加数组，再复制（我也有点懵）
for (int m = 1; m < count.length; m++) {
count[m] = count[m] + count[m - 1];
}
for (int n = arr.length - 1; n >= 0; n--) {
int num = arr[n] / division % 10;
result[--count[num]] = arr[n];
}
System.arraycopy(result, 0, arr, 0, arr.length);
Arrays.fill(count, 0);
}
return result;
}
}
image.gif
参考文献
1: 十大经典排序算法（动图演示）
2: 图解排序算法(四)之归并排序
3:【干货】史上最好的排序和数据结构入门
