真干货!十大排序算法,包括视频和代码

微信公众号:一起学习大数据呀
关注可学习更多奇怪的知识!
前言
本文收集整理常见的十大排序算法,配套 Java 代码和视频短视频教程。帮助小伙伴们更快的理解和掌握。
不管你是为了应付考试,还是面试用,本文都可以帮到你,降低学习门槛,作者水平有限,难免遗漏错误,欢迎读者们留言指正。
算法目录
  1. 冒泡排序
  2. 选择排序
  3. 插入排序
  4. 快速排序
  5. 希尔排序
  6. 归并排序
  7. 堆排序
  8. 计数排序
  9. 桶排序
  10. 基数排序
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、选择排序
基本思想
每一趟从待排序的记录中选出最大(小)的元素,顺序放在已排好序的序列最后,直到全部记录排序完毕。
视频讲解
选择排序 空降(06:33)
代码实现
//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、插入排序
基本思想
将数组分为“已排序区间”和“未排序区间”。核心思想是提取“未排序区间”中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复该过程,直到排序区间中元素为空。
视频讲解
插入排序 空降(12:27)
代码实现
//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 快排的优化方案
  1. 基准数优化
    随机取基准数
    三位数取中: 选取数组开头,中间和结尾的元素,通过比较,选择中间的值作为快排的基准。
  2. 序列长度达到一定大小时,使用插入排序
  3. 尾递归优化
  4. 聚集元素
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> bucketArr = new ArrayList<>(bucketNum); for (int i = 0; i < bucketNum; i++) { bucketArr.add(new ArrayList()); }//将属于同一个桶的元素放入对应的桶 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 = https://www.it610.com/article/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:【干货】史上最好的排序和数据结构入门

    推荐阅读