三明商城网站开发设计,建筑企业网,广告电商,app开发的知名公司有哪些一、冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调#xff0c;比较是相邻的两个元素比较#xff0c;交换也发生在这两个元素之间。#xff08;类似于气泡上浮过程#xff09; 动图演示 代码实现 int a[]{2,5,3,7,4,8};for (int i 0; i a.length; i) {f… 一、冒泡排序 冒泡排序就是把小的元素往前调或者把大的元素往后调比较是相邻的两个元素比较交换也发生在这两个元素之间。类似于气泡上浮过程 动图演示 代码实现 int a[]{2,5,3,7,4,8};for (int i 0; i a.length; i) {for (int j 0; j a.length - i - 1; j) {if (a[j] a[j 1]) {int temp a[j];a[j] a[j 1];a[j 1] temp;}}} 二、选择排序 从未排序序列中找到最小最大放在已排序序列尾部 动图演示 代码实现 int a[]{2,5,3,7,4,8};for (int i 0; i a.length; i) {int ki;for (int j i1; j a.length - i - 1; j) {if (a[j] a[k]) {kj;}int temp a[j];a[j] a[k];a[k] temp;}} 三、快速排序 以一个元素为基数将小于基数的元素移到基数前面大于基数的元素移到基数后面对左右区间递归以上步骤直到区间只有一个数 动图演示 代码实现 public static void quickSort(int[] a, int left, int right) {if (left right) {return;}int i left;int j right;int base a[i];while (i j) {//先进行从后往前比较,比基准值小的交换,否则一直往前找比基准值小的while (a[j] base i j) {j--;}int temp a[i];a[i] a[j];a[j] temp;//再从前往后比较找比基准值大的交换否则一直往后找while (a[i] base i j) {i;}temp a[i];a[i] a[j];a[j] temp;}//当ij时,就以i或者j下标的元素看成分界线,这时左边比这个分界线的数小,右边比这个分界线的值大。然后再对这两个区进行递归直到每个组只剩一个数quickSort(a, left, i - 1); //分界线左边进行排序quickSort(a, i 1, right); //分界线后边进行排序} 注引用quickSort时left为0right为a.length-1 四、插入排序 将数组中的数据从第二位开始向前找到合适的位置插入有点类似向前的冒泡排序 动图演示 代码实现 for (int i 1; i a.length; i) { for (int j i; j 0; j--) {if (a[j]a[j-1]){int temp a[j];a[j] a[j - 1];a[j - 1] temp;} else {break;}}} 五、计数排序 首先设置一个包含所有范围数据的数组countcount[i]代表i这个数据出现了多少次最后从起始位置遍历时count[i]等于几就在数组中追加几个i。计数排序是一种特殊的桶排序适用于量大但是范围小的数据排序比如高考成绩排名。 动图演示 代码实现 int max a[0];for (int i 1; i a.length; i) {if (a[i] max) {max a[i];}}//找出最小的数minint min a[0];for (int i 1; i a.length; i) {if (a[i] min) {min a[i];}}//创建计数数组int[] count new int[max 1];//遍历afor (int i 0; i a.length; i) {count[a[i]];}//遍历输出计数数组int k 0;for (int i 0; i count.length; i) {while (count[i] 0) {a[k] i; //a[k]1; k;count[i]--;}} 代码优化 我们考虑一个问题如果数组是[101,103,110,116,,119,120],如果开辟了一个121大小的数组,前100个位置都是空的,显然是不合适的,因此我们可以把数组的大小设置成max-min1。这时我们向数组中计数时下标要减去一个偏移量min输出数组的时候要加上这个偏移量。 int max a[0];for (int i 1; i a.length; i) {if (a[i] max) {max a[i];}}//找出最小的数minint min a[0];for (int i 1; i a.length; i) {if (a[i] min) {min a[i];}}//创建计数数组int[] count new int[max - min 1];//遍历afor (int i 0; i a.length; i) {count[a[i] - min];}//遍历输出计数数组int k 0;for (int i 0; i count.length; i) {while (count[i] 0) {a[k] i min; //a[k]1; k;count[i]--;}} 六、希尔排序 希尔排序可以理解成插入排序的优化版本。 希尔排序是先将任意间隔为N的元素有序刚开始可以是Nn/2接着让NN/2让N一直缩小当N1,时此时序列间隔为1有序。 动图演示 代码实现 //希尔排序for (int gap a.length / 2; gap 0; gap / 2) {//插入排序将1换成gapfor (int i gap; i a.length; i) {for (int j i; j - gap0; j - gap) {if (a[j] a[j - gap]) {int temp a[j];a[j] a[j - gap];a[j - gap] temp;} else {break;}}}} 七、归并排序 归并排序的采用分治思想如果要排序一个数组我们先把数组从中间分成前后两个部分然后对前后两个部分分别进行排序再将排好序的两部分合并在一起这样整个数组就都有序了。核心是merge()合并函数。 动图演示 代码实现1递归 public class MergeSort {// 归并排序(递归public static int[] mergeSort(int[] arr, int left, int right) {// 如果 left right表示数组只有一个元素则不用递归排序if (left right) {// 把大的数组分隔成两个数组int mid (left right) / 2;// 对左半部分进行排序arr mergeSort(arr, left, mid);// 对右半部分进行排序arr mergeSort(arr, mid 1, right);//进行合并merge(arr, left, mid, right);}return arr;}// 合并函数merge把两个有序的数组合并起来// arr[left..mif]表示一个数组arr[mid1 .. right]表示一个数组private static void merge(int[] arr, int left, int mid, int right) {//先用一个临时数组把他们合并汇总起来int[] a new int[right - left 1];int i left;int j mid 1;int k 0;while (i mid j right) {if (arr[i] arr[j]) {a[k] arr[i];//(即a[k]a[i]; kk1; ii1;} else {a[k] arr[j];}}while(i mid) a[k] arr[i];while(j right) a[k] arr[j];// 把临时数组复制到原数组for (i 0; i k; i) {arr[left] a[i];}}
} 代码实现2非递归 public class MergeSort {// 归并排序非递归public static int[] mergeSort(int[] arr) {int n arr.length;// 子数组的大小分别为1248...// 刚开始合并的数组大小是1接着是2接着4....for (int i 1; i n; i i) {//进行数组进行划分int left 0;int mid left i - 1;int right mid i;//进行合并对数组大小为 i 的数组进行两两合并while (right n) {// 合并函数和递归式的合并函数一样merge(arr, left, mid, right);left right 1;mid left i - 1;right mid i;}// 还有一些被遗漏的数组没合并千万别忘了// 因为不可能每个字数组的大小都刚好为 iif (left n mid n) {merge(arr, left, mid, n - 1);}}return arr;}
}八、桶排序 桶排序是将数组分别放到有限数量的桶里。每个桶再进行排序。 桶排序就是把最大值和最小值之间的数进行瓜分例如分成 10 个区间10个区间对应10个桶我们把各元素放到对应区间的桶中去再对每个桶中的数进行排序可以采用归并排序也可以采用快速排序之类的。 那么桶排序当中所谓的“桶”又是什么概念呢 每一个桶bucket代表一个区间范围里面可以承载一个或多个元素。桶排序的第一步就是创建这些桶确定每一个桶的区间范围 具体建立多少个桶如何确定桶的区间范围有很多不同的方式。 我们这里创建的桶数量等于原始数列的元素数量除了最后一个桶只包含数列最大值前面各个桶的区间范围按照比例确定。 区间跨度大小 最大值-最小值/ 桶的数量 - 1 注除了最后一个桶之外其余的桶均分最大值和最小值的差值区间跨度大小也就是桶的范围的大小。 代码中所有的桶保存在ArrayList集合当中每一个桶被定义成一个链表LinkedListDouble这样便于在尾部插入元素。 定位元素属于第几个桶是按照比例来定位 (array[i] - min) * (bucketNum-1) / d 注要定位元素 array[i] 在第几个桶先减去最小值min,看它在桶数组ArrayList中的偏移为多少然后除以桶的区间大小d/(buketNum-1),相当于乘以(buketNum-1)/d除以桶区间大小就可以定位是在哪个桶里了。 同时代码使用了JDK的集合工具类Collections.sort来为桶内部的元素进行排序。Collections.sort底层采用的是归并排序或Timsort小伙伴们可以简单地把它们当做是一种时间复杂度 Onlogn的排序。 动图演示 代码实现 public static int[] BucketSort(int[] arr) {if(arr null || arr.length 2) return arr;int n arr.length;int max arr[0];int min arr[0];// 寻找数组的最大值与最小值for (int i 1; i n; i) {if(min arr[i])min arr[i];if(max arr[i])max arr[i];}//和优化版本的计数排序一样弄一个大小为 min 的偏移值int d max - min;//初始化桶int bucketNum arr.length;ArrayListLinkedListInteger bucketList new ArrayList(bucketNum);for (int i 0; i bucketNum; i) {bucketList.add(new LinkedListInteger());}//遍历原数组将每个元素放入桶中for (int i 0; i n; i) {int num (int)((arr[i] - min) * (bucketNum - 1) / d);bucketList.get(num).add(arr[i]);}//对桶内的元素进行排序我这里采用系统自带的排序工具for (int i 0; i bucketNum; i) {Collections.sort(bucketList.get(i));}//把每个桶排序好的数据进行合并汇总放回原数组int k 0;for (int i 0; i bucketNum; i) {for (Integer t : bucketList.get(i)) {arr[k] t min;}}return arr;} ArrayListhttps://www.runoob.com/java/java-arraylist.html LinkedListhttps://www.runoob.com/java/java-linkedlist.html 九、堆排序 堆的特点就是堆顶的元素是一个最值大顶堆的堆顶是最大值小顶堆则是最小值。 堆排序就是把堆顶的元素与最后一个元素交换交换之后破坏了堆的特性我们再把堆中剩余的元素再次构成一个大顶堆然后再把堆顶元素与最后第二个元素交换…如此往复下去等到剩余的元素只有一个的时候此时的数组就是有序的了。 堆Heap 父节点及子节点下标的关系 动图演示 思路 1.首先将待排序的数组构造成一个大根堆此时整个数组的最大值就是堆结构的顶端 2.将顶端的数与末尾的数交换此时末尾的数为最大值剩余待排序数组个数为n-1 3.将剩余的n-1个数再构造成大根堆再将顶端数与n-1位置的数交换如此反复执行便能得到有序数组 注意:升序用大根堆降序就用小根堆(默认为升序) 代码实现 public class Dui {public static void main(String[] args) {int a[]{31254};sort(a);for (int i 0; i a.length; i) {System.out.print(a[i] );}}//堆排序的方法private static void sort(int[] arr){//建堆for(int i arr.length/2 - 1; i 0; i--){adjustHeap(arr,i,arr.length);}//排序for(int j arr.length - 1; j 0; j--){//堆顶和最后一个元素交换swap(arr,0,j);//交换后重新建队adjustHeap(arr,0,j);}}//建堆的方法//实际上就是对于每一个节点比较其与其子节点中最大的那个数并将最大的那个数交换到节点位置private static void adjustHeap(int[] arr,int i,int length){int temp arr[i];for(int k i*21; k length; k k*21){if( k1 length arr[k] arr[k1] ){//有右孩子且右孩子大于左孩子k;}if( arr[k] temp ){//如果子大于父则父与子节点交换arr[i] arr[k];i k;}else{break;}}arr[i] temp;}//交换两个数的方法private static void swap(int[] arr, int i, int j){int temp arr[i];arr[i] arr[j];arr[j] temp;}} 详细内容也可参照此博客https://blog.csdn.net/weixin_51609435/article/details/122982075作者Oorik 也可参照bilibiliup主请叫我AXin的视频https://www.bilibili.com/video/BV1fp4y1D7cj/?spm_id_from333.337.search-card.all.click 十、基数排序 基数排序是一种特殊的桶排序 思路先以个位数的大小来对数据进行排序接着以十位数的大小来多数进行排序接着以百位数的大小… 排到最后就是一组有序的元素了。不过他在以某位数进行排序的时候是用“桶”来排序的。 由于某位数个位/十位…不是一整个数的大小范围为0-9所以我们需要10个桶然后把具有相同数值的数放进同一个桶里之后再把桶里的数按照0号桶到9号桶的顺序取出来这样一趟下来按照某位数的排序就完成了 动图演示 代码实现 public class RadioSort {public static int[] radioSort(int[] arr) {if(arr null || arr.length 2) return arr;int n arr.length;int max arr[0];// 找出最大值for (int i 1; i n; i) {if(max arr[i]) max arr[i];}// 计算最大值是几位数int num 1;while (max / 10 0) {num;max max / 10;}// 创建10个桶ArrayListLinkedListInteger bucketList new ArrayList(10);//初始化桶for (int i 0; i 10; i) {bucketList.add(new LinkedListInteger());}// 进行每一趟的排序从个位数开始排for (int i 1; i num; i) {for (int j 0; j n; j) {// 获取每个数最后第 i 位是数组int radio (arr[j] / (int)Math.pow(10,i-1)) % 10;//放进对应的桶里bucketList.get(radio).add(arr[j]);}//合并放回原数组int k 0;for (int j 0; j 10; j) {for (Integer t : bucketList.get(j)) {arr[k] t;}//取出来合并了之后把桶清光数据bucketList.get(j).clear();}}return arr;}
}
