常见排序算法 蔚落 2022-09-09 06:05 160阅读 0赞 ### 常见排序算法 ### * 1. 排序概述 * 2. 排序实现 * * 2.1 冒泡排序 * 2.2 快速排序 * 2.2 直接插入排序 * 2.2 希尔排序 * 2.2 简单选择排序 * 2.2 堆排序 * 2.2 归并排序 * 2. 代码实现 # 1. 排序概述 # ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16] # 2. 排序实现 # ## 2.1 冒泡排序 ## ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 1] ## 2.2 快速排序 ## ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 2] ## 2.2 直接插入排序 ## ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 3] ## 2.2 希尔排序 ## ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 4] ## 2.2 简单选择排序 ## ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 5] ## 2.2 堆排序 ## ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 6] ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 7] ## 2.2 归并排序 ## ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 8] # 2. 代码实现 # package com.zrj.algorithm.sort; import com.alibaba.fastjson.JSON; import java.util.ArrayList; import java.util.Arrays; import java.util.List; /** * 排序算法 * * @author zrj * @date 2021/8/29 * @since V1.0 **/ public class SortData { public static void main(String[] args) { int[] array = { 2, 5, 3, 1, 4}; bubbleSort( array ); insertSort( array ); hillSort( array ); selectSort( array ); quickSort( array, 0, array.length - 1 ); } /** * 冒泡排序 */ public static void bubbleSort(int[] array) { for (int i = array.length - 1; i >= 0; i--) { for (int j = 0; j < i; j++) { // 如果array[j]>array[j+1],交换位置 if (array[j] > array[j + 1]) { int variable = array[j]; array[j] = array[j + 1]; array[j + 1] = variable; } } } System.out.println( "冒泡排序:" + JSON.toJSONString( array ) ); } /** * 快速排序 */ public static void quickSort(int[] array, int left, int right) { int low = left; int high = right; if (low > high) { return; } // 取数组第一个数k作为衡量标准 int k = array[low]; while (low < high) { // 右侧找到第一个小于k的停止 while (low < high && array[high] >= k) { high--; } // 找到第一个比k小的数,放在low的位置 array[low] = array[high]; //找到第一个大于k的值停止 while (low < high && array[low] <= k) { low++; } array[high] = array[low]; } //赋值,然后左右递归 array[low] = k; quickSort( array, left, low - 1 ); quickSort( array, low + 1, right ); System.out.println( "快速排序:" + JSON.toJSONString( array ) ); } /** * 直接插入排序 */ public static void insertSort(int[] array) { int variable; for (int i = 0; i < array.length; i++) { variable = array[i]; for (int j = i - 1; j >= 0; j--) { if (array[j] > variable) { array[j + 1] = array[j]; array[j] = variable; } else { break; } } } System.out.println( "直接插入排序:" + JSON.toJSONString( array ) ); } /** * 希尔排序 */ public static void hillSort(int[] array) { int d = array.length; //临时变量 int variable; //共分成d组 for (; d >= 1; d /= 2) { //到那个元素就看这个元素在的那个组即可 for (int i = d; i < array.length; i++) { variable = array[i]; for (int j = i - d; j >= 0; j -= d) { if (array[j] > variable) { array[j + d] = array[j]; array[j] = variable; } else { break; } } } } System.out.println( "希尔排序:" + JSON.toJSONString( array ) ); } /** * 简单选择排序 */ public static void selectSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int min = i; // 最小位置 for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { min = j; // 更换最小位置 } } if (min != i) { swap( arr, i, min ); // 与第i个位置进行交换 } } System.out.println( "简单选择排序:" + JSON.toJSONString( arr ) ); } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } /** * 堆排序 * 下移交换 把当前节点有效变换成一个堆(小根) */ static void shiftDown(int arr[], int index, int len) { //0 号位置不用 int leftchild = index * 2 + 1;//左孩子 int rightchild = index * 2 + 2;//右孩子 if (leftchild >= len) { return; } else if (rightchild < len && arr[rightchild] < arr[index] && arr[rightchild] < arr[leftchild]) { //右孩子在范围内并且应该交换 swap( arr, index, rightchild );//交换节点值 shiftDown( arr, rightchild, len );//可能会对孩子节点的堆有影响,向下重构 } else if (arr[leftchild] < arr[index]) { //交换左孩子 swap( arr, index, leftchild ); shiftDown( arr, leftchild, len ); } } static void creatHeap(int arr[]) { //将数组创建成堆 for (int i = arr.length / 2; i >= 0; i--) { shiftDown( arr, i, arr.length ); } } static void heapSort(int arr[]) { System.out.println( "原始数组为:" + Arrays.toString( arr ) ); int val[] = new int[arr.length]; //临时储存结果 //step1建堆 creatHeap( arr ); System.out.println( "建堆后的序列为:" + Arrays.toString( arr ) ); //step2 进行n次取值建堆,每次取堆顶元素放到val数组中,最终结果即为一个递增排序的序列 for (int i = 0; i < arr.length; i++) { val[i] = arr[0];//将堆顶放入结果中 arr[0] = arr[arr.length - 1 - i];//删除堆顶元素,将末尾元素放到堆顶 shiftDown( arr, 0, arr.length - i );//将这个堆调整为合法的小根堆,注意(逻辑上的)长度有变化 } //数值克隆复制 for (int i = 0; i < arr.length; i++) { arr[i] = val[i]; } System.out.println( "堆排序后的序列为:" + Arrays.toString( arr ) ); } /** * 归并排序 */ private static void mergesort(int[] array, int left, int right) { int mid = (left + right) / 2; if (left < right) { mergesort( array, left, mid ); mergesort( array, mid + 1, right ); merge( array, left, mid, right ); } } private static void merge(int[] array, int l, int mid, int r) { int lindex = l; int rindex = mid + 1; int team[] = new int[r - l + 1]; int teamindex = 0; while (lindex <= mid && rindex <= r) { //先左右比较合并 if (array[lindex] <= array[rindex]) { team[teamindex++] = array[lindex++]; } else { team[teamindex++] = array[rindex++]; } } //当一个越界后剩余按序列添加即可 while (lindex <= mid) { team[teamindex++] = array[lindex++]; } while (rindex <= r) { team[teamindex++] = array[rindex++]; } for (int i = 0; i < teamindex; i++) { array[l + i] = team[i]; } } /** * 桶排序 */ public static void bucketSort() { int a[] = { 1, 8, 7, 44, 42, 46, 38, 34, 33, 17, 15, 16, 27, 28, 24}; List[] buckets = new ArrayList[5]; //初始化 for (int i = 0; i < buckets.length; i++) { buckets[i] = new ArrayList<Integer>(); } //将待排序序列放入对应桶中 for (int i = 0; i < a.length; i++) { int index = a[i] / 10;//对应的桶号 buckets[index].add( a[i] ); } //每个桶内进行排序(使用系统自带快排) for (int i = 0; i < buckets.length; i++) { buckets[i].sort( null ); for (int j = 0; j < buckets[i].size(); j++)//顺便打印输出 { System.out.print( buckets[i].get( j ) + " " ); } } } /** * 计数排序 */ public static void countSort(int[] a) { int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; //找到max和min for (int i = 0; i < a.length; i++) { if (a[i] < min) { min = a[i]; } if (a[i] > max) { max = a[i]; } } int[] count = new int[max - min + 1];//对元素进行计数 for (int i = 0; i < a.length; i++) { count[a[i] - min]++; } //排序取值 int index = 0; for (int i = 0; i < count.length; i++) { while (count[i]-- > 0) { a[index++] = i + min;//有min才是真正值 } } } /** * 基数排序 */ public static void radixSort(int[] arr) { { List<Integer>[] bucket = new ArrayList[10]; for (int i = 0; i < 10; i++) { bucket[i] = new ArrayList<>(); } //找到最大值 int max = 0;//假设都是正数 for (int i = 0; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; } } int divideNum = 1;//1 10 100 100……用来求对应位的数字 while (max > 0) { //max 和num 控制 for (int num : arr) { bucket[(num / divideNum) % 10].add( num );//分配 将对应位置的数字放到对应bucket中 } divideNum *= 10; max /= 10; int idx = 0; //收集 重新捡起数据 for (List<Integer> list : bucket) { for (int num : list) { arr[idx++] = num; } list.clear();//收集完需要清空留下次继续使用 } } } } } [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/7485d86047b84ad99aa72c627119d1c1.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/387e16ec49254ff690e14b610b444991.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/58b27bd1f8094244b6861d4695e0ccc8.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/ec0f772889264c7690fcd4561172abf6.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/d1c906e0bd72448f99c3310b635acf1f.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220829/ac759d6a77f94ecabf5b3c729194ba4e.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220829/5293dd02f0544f96ad668b0f46de6d79.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220829/8b9481af3db14bdf843967664e379975.png [watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6Z2W6IqC5YWI55Sf_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220829/1ae54c4ed8c54eedab563c5d681b8f13.png
相关 [排序算法] 常见的排序算法 前言 1.冒泡排序 2.选择排序 3.插入排序 4希尔排序 5.归并排序 6.快速排序 前言 在实际需求中,我们可能要 雨点打透心脏的1/2处/ 2023年09月29日 14:29/ 0 赞/ 203 阅读
相关 算法(一)常见排序 算法-常见排序 这里写目录标题 算法-常见排序 一. 常见排序列表 二. 参考下马老师的快速排序记忆法 三. 排序 àì夳堔傛蜴生んèń/ 2022年11月14日 13:14/ 0 赞/ 121 阅读
相关 常见排序算法总结 排序算法经过了很长时间的演变,产生了很多种不同的方法。对于初学者来说,对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合,很难通用。因此,我们很有必要对所有常 我会带着你远行/ 2022年08月23日 14:58/ 0 赞/ 156 阅读
相关 常见排序算法 注:点进链接查看算法具体实现!!! -------------------- 插入排序 [直接插入排序][Link 1] [希尔排序][Link 2] - 怼烎@/ 2022年06月16日 09:10/ 0 赞/ 166 阅读
相关 常见排序算法 常见排序: ![这里写图片描述][SouthEast] 1、直接插入排序 在给定数组中,拿出一个数M,与前面的数相比较,如果M大于前面的数,位置不变,如果小于前面的 迷南。/ 2022年06月05日 05:51/ 0 赞/ 205 阅读
相关 常见排序算法 常见排序算法 排序问题作为算法基础的重要组成部分,代码实现方式多种多样,但其原理是基本一致的。常见的排序算法有: ①. 冒泡排序 ②. 选择排序 ③. 插入排序 偏执的太偏执、/ 2022年05月16日 07:28/ 0 赞/ 235 阅读
相关 常见排序算法 今天实在不想刷笔试题就把常见的排序手敲了一遍 -------------------- 1.选择排序 class ChoiceSort<T extends 约定不等于承诺〃/ 2022年01月15日 13:35/ 0 赞/ 244 阅读
相关 常见排序算法 稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。(即原本a在b 墨蓝/ 2022年01月06日 03:01/ 0 赞/ 261 阅读
还没有评论,来说两句吧...