网站建设实习生怎么样,网页设计制作注册界面实验报告,广东东莞市,wordpress 去除新闻对于排序算法#xff0c;是我们在数据结构阶段#xff0c;必须要牢牢掌握的一门知识体系#xff0c;但是#xff0c;对于排序算法#xff0c;里面涉及到的思路#xff0c;代码……各种时间复杂度等#xff0c;都需要我们#xff0c;记在脑袋瓜里面#xff01;#xf…对于排序算法是我们在数据结构阶段必须要牢牢掌握的一门知识体系但是对于排序算法里面涉及到的思路代码……各种时间复杂度等都需要我们记在脑袋瓜里面尽量一丢丢不要出现差错面试所必备的精彩提问言归正传对于排序我们首先需要知道的是排序的概念排序的概念所谓的排序就是使一串记录按照其中的某个或者某些关键字的大小递增递减的排序起来的操作稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍然在r[j]之前这种排序算法是稳定的否则是不稳定的就比如9 5 2 7 3 6 4 5 8 0 这些数据而言内部排序数据元素部分放在内存的排序外部排序数据元素不能同时放在内存中根据排序过程的要求不同在内存与外存之间移动数据的排序要排序的数据在内存中放不下下面笔者就以七种常见的排序算法为列来带大家走进排序直接插入排序希尔排序选择排序堆排序冒泡排序快速排序归并排序1.插入排序插入排序把待排序的记录按照其关键码值的大小逐个插入到一个已经排序好的有序序列中直到所有的记录插完为止从而得到一个新的有序序列扑克牌下面请看笔者的代码 public static void insertSort(int[] arr){//对传入的数组进行排序for (int i 1; iarr.length; i){for (int j i-1; j0; j--){if(arr[j]arr[j1]){//稳定的int temp arr[j];arr[j] arr[j1];arr[j1] temp;}elsebreak;}}System.out.println(Arrays.toString(arr));}public static void main(String[] args) {int[] array{12,56,32,67,10,19,4};insertSort(array);}2.希尔排序希尔排序的思想先选定一个整数把待排序文件中的所有记录分成多个组所有距离为一样的放在同一个组内并对每一组的记录进行插入排序取重复上述分组和排序的工作当达到1时所有记录在统一组内排序好先分组5组3组最后为1组假设初始的数据为 9 1 2 5 7 4 8 6 3 5 那么我们有着一下 的简单排序过程经过上述的过程我们可以看出组数越多每组进行排序的数据越少两两交换使用插入排序越有序越快组数越少每组数据越多数据在慢慢变得有序那么我们对于希尔排序有着一下的几点总结希尔排序是对直接插入排序算法的优化当gap1时都是预排序目的是让数组接近有序当gap1时数组已经接近有序了这样就会很快这样整体而言可以达到优化的效果我们实现后可以进行性能测试的对比希尔排序的时间复杂度不好计算因为gap的取值方法很多导致很难去计算因此在好些书中给出的希尔排序的时间复杂度不固定有了上述的思考我们接下来就该实现一下代码了 public static void shellSort(int[] array){int gaparray.length;//分组while (gap1){shell(array,gap);gapgap/2;}//整体进行插入排序此时gap1shell(array,1);}//插入排序public static void shell(int[] array,int gap){for (int i 0; i array.length; i) {int tmparray[i];int ji-gap;for(;j0;jj-gap){if (array[j]tmp){array[jgap]array[j];}else {break;}}array[jgap]tmp;}}public static void main(String[] args) {int[] array{12,56,32,67,10,19,4};shellSort(array);System.out.println(Arrays.toString(array));}3.选择排序在了解选择排序之前我们需要知道的是选择排序的思想:每一次从待排序的数据元素中选出最小最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完直接选择排序第一次从R[0]到R[n-1]中选出最小值与R[0]进行交换第二次从R[1]到R[n-1]中选出最小值与R[1]交换……以此类推从而得到从小到大的有序排序经过上面的简单分析我们可以得出下列的有效代码 public static void selectSort(int[] array) {for (int i 0; i array.length; i) {int minIndex i;for (int j i 1; j array.length; j) {if (array[j] array[minIndex]) {minIndex j;//minIndex保存最小数据的下标值}}swap(array, i, minIndex);}}private static void swap(int[] array,int i,int j){int tmparray[i];array[i]array[j];array[j]tmp;}public static void main(String[] args) {int[] array{12,56,32,67,10,4};selectSort(array);System.out.println(Arrays.toString(array));}4.堆排序对于堆排序是指利用堆积树堆这种数据结构所设计的一种排序算法它是一种选择排序通过堆来进行选择数据需要注意的是排升序建大堆排降序建小堆那么根据笔者之前的堆排序的环节https://blog.csdn.net/weixin_64308540/article/details/129217324?spm1001.2014.3001.5502我们可以有着一下的简单代码 public static void heapSort(int[] array){createBigHeap(array);//创建一个大根堆int endarray.length-1;while (end0){//等于0的时候就不换了swap(array,0,end);//交换shiftDown(array,0,end);//向下调整end--;}}private static void createBigHeap(int[] array){//建立大根堆从最后一颗子树开始for (int parent (array.length-1-1)/2; parent 0 ; parent--) {shiftDown(array,parent,array.length);//array,length是指结束位置}}//向下调整private static void shiftDown(int[] array,int parent,int len){int child2*parent1;while (childlen){//至少有左孩子if (child1len array[child]array[child1]){//有右孩子//此时child是左孩子最大值的下标child;}if (array[child]array[parent]){swap(array,child,parent);//交换parentchild;child2*parent1;}else {break;}}}private static void swap(int[] array,int i,int j){int tmparray[i];array[i]array[j];array[j]tmp;}public static void main(String[] args) {int[] array{12,56,32,67,10,4};heapSort(array);System.out.println(Arrays.toString(array));}5.交换排序对于交换排序我们在之前就已经有过接触其实就是最简单的冒泡排序交换排序的基本思想所谓交换就是根据序列中的两个记录键值的比较结果交换这两个记录在序列中的位置交换排序的特点将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动下面笔者就以冒泡排序来进行书写代码方法1public static void bubblesort2(int[] array ) {//趟数for (int i 0; i array.length-1; i) {//每趟执行的次数boolean flgfalse;for(int j0;jarray.length-1-i;j) {if(array[j]array[j1]) {int tmparray[j1];array[j1]array[j];array[j]tmp;}flgtrue;}if(flgfalse) {return ;}}}public static void main(String[] args) {int[] array{1,29,10,36,5,21,46,3,6};bubblesort2(array);System.out.println(Arrays.toString(array));}方法2 public static void bubbleSort2(int[] array){for (int i 0; i array.length; i) {for (int j 0; j array.length-1-i; j) {if (array[j]array[j1])swap(array,j,j1);}}}private static void swap(int[] array,int i,int j){int tmparray[i];array[i]array[j];array[j]tmp;}public static void main(String[] args) {int[] array{12,56,32,67,10,19,4};bubbleSort2(array);System.out.println(Arrays.toString(array));}在上述代码中方法1是对方法2的简单优化在方法1中我们通过一个boolean flgfalse;来优化了代码原因在于在进行冒泡排序的时候可能对于一串数据排到一半就有序了那么在没有优化之前肯定还得一个一个尝试去遍历但是在优化以后可以节约时间6.快速排序快速排序的思想任取待排序元素序列中的某元素一般是第一个元素作为基准值按照该排序码将待排序的集合分为两个子序列左子序中的所有元素均小于基准值右子序中的所有元素均大于基准值然后最左右子序列都重复该过程直到所有的元素都排序在相应的位置为止对于上述的简单思想我们有着挖坑法Hoare法下面我们先讲解一下挖坑法先将第一个数据存放在一个临时变量key中形成一个坑位设置两个变量ij排序开始的时候i0jN-1以第一个数组元素作为关键数据赋值给key即keyA[0]从j开始向前搜素即由后开始向前搜素j--),找到第一个小于key的值A[j],将A[j]与A[i]的值进行交换从i开始向后搜素即由前开始向后搜素i找到第一个大于key的值A[i]将A[i]与A[j]的值交换重复步骤34直到ij为止对于上述的思路我们可以用递归来实现package zyh.example.demo.algorithm.kuaisupaixu;import java.util.Arrays;/**
* ClassName KuaiPai13
* Author zhangyonghui
* Description
* Date 2022/3/29 11:26
* Version 1.0
**/
public class KuaiPai13 {public static void main(String[] args) {int[] arr new int[]{4, 7, 6, 5, 3, 2, 8, 1};quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}/*** 快速排序--挖坑法* param arr 数组* param startIndex 左边界索引* param endIndex 右边界索引*/public static void quickSort(int[] arr, int startIndex, int endIndex) {// 递归结束条件startIndex大等于endIndex的时候if (startIndex endIndex) {return;}// 得到基准元素位置int pivotIndex partition(arr, startIndex, endIndex);// 用分治法递归数列的两部分quickSort(arr, startIndex, pivotIndex - 1);quickSort(arr, pivotIndex 1, endIndex);}/*** 具体每一轮的快速排序* param arr 数组* param startIndex 左边界索引* param endIndex 右边界索引* return 返回基准值的位置此时基准值左边的元素都小于基准值基准值右边的元素都大于基准值*/private static int partition(int[] arr, int startIndex, int endIndex) {// 取第一个位置的元素作为基准元素int pivot arr[startIndex];// 初始化坑的位置初始等于pivot基准值的位置int kengIndex startIndex;//初始化左右游标/指针int leftYb startIndex;int rightYb endIndex;//大循环在左右指针重合时结束while ( leftYbrightYb ) {//right指针从右向左进行比较// leftYbrightYb 左游标永远小于右游标是遍历元素并发生元素变动的前提while ( leftYbrightYb) {// 先遍历右边// 如果元素大于基准值--右游标左移if (arr[rightYb] pivot) {rightYb--;}else{ //如果右边的当前元素小于基准值了那么将该元素填入坑中该元素本来的位置成为新的坑arr[kengIndex] arr[rightYb];kengIndex rightYb;leftYb;break;}}//再遍历左边// leftYbrightYb 左游标永远小于右游标是遍历元素并发生元素变动的前提while (leftYbrightYb) {//如果元素小于基准值--左游标右移if (arr[leftYb] pivot) {leftYb;}else{ //如果左边的当前元素大于基准值了那么将该元素填入坑中该元素本来的位置成为新的坑arr[kengIndex] arr[leftYb];kengIndex leftYb;rightYb--;break;}}}//跳出了大循环说明此时此刻左右游标是重合的这时将基准值放在重合位置(最后一个坑)// 此时基准值左边的元素都小于基准值基准值右边的元素都大于基准值这一轮交换宣告结束arr[kengIndex] pivot;return kengIndex;}}接下来进入Hoare法right找到比基准小的停下来left找到比基准大的停下来进行比较循环往复最后当rightleft的时候将此时对应的值与基准进行比较请看笔者代码public class Main {static int[] a {5, 3, 1, 9, 8, 2, 4, 7};public static void main(String[] args) {fastsort(0, a.length-1);for (int i 0; i a.length; i) {System.out.print(a[i] );}}private static int Hoare(int l, int r) {int p a[l];int i l-1;int j r1 ;while (true) {do {j--;} while (a[j] p);do {i;} while (a[i] p);if (i j) {int temp a[i];a[i] a[j];a[j] temp;} elsereturn j;}}private static void fastsort(int l, int r) {if (l r) {int s Hoare(l, r);fastsort(l, s);fastsort(s1, r);}}
}7.归并排序归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列断间有序主要的思路及其过程如下图所示那么接下来请看代码吧递归实现 //递归实现
public static void mergeSort(int[] array){mergeSortFunc(array,0, array.length);}private static void mergeSortFunc(int[] array,int left,int right){if (leftright){return;}//分解int mid(leftright)/2;mergeSortFunc(array,left,mid);mergeSortFunc(array,mid1,right);merge(array,left,right,mid);//合并}private static void merge(int[] array,int start,int end,int mid){int s1start;int s2mid1;int[] tmpnew int[end-start1];//申请一个数组int k0;//tmp数组下标while (s1mid s2end){if (array[s1] array[s2]){tmp[k]array[s1];}else {tmp[k]array[s2];}}while (s1mid){tmp[k]array[s1];}while (s2end){tmp[k]array[s2];}for (int i 0; i tmp.length; i) {array[istart]tmp[i];}}感兴趣的老铁可以看一下非递归实现的//非递归public static void mergeSort2(int[] array){int gap1;while (gaparray.length){for (int i 0; i array.length; i) {int lefti;int midleftgap1;if (mid array.length){midarray.length-1;}int rightmidgap;if (rightarray.length){rightarray.length-1;}merge(array,left,right,mid);}gapgap*2;}}七大排序算法大致就到此结束了拜拜
文章转载自： http://www.morning.lfdrq.cn.gov.cn.lfdrq.cn http://www.morning.gcftl.cn.gov.cn.gcftl.cn http://www.morning.cgdyx.cn.gov.cn.cgdyx.cn http://www.morning.qcnk.cn.gov.cn.qcnk.cn http://www.morning.ndxss.cn.gov.cn.ndxss.cn http://www.morning.cnqff.cn.gov.cn.cnqff.cn http://www.morning.hkshy.cn.gov.cn.hkshy.cn http://www.morning.qmnjn.cn.gov.cn.qmnjn.cn http://www.morning.jxrpn.cn.gov.cn.jxrpn.cn http://www.morning.dtrcl.cn.gov.cn.dtrcl.cn http://www.morning.ryfq.cn.gov.cn.ryfq.cn http://www.morning.ltbwq.cn.gov.cn.ltbwq.cn http://www.morning.mrlkr.cn.gov.cn.mrlkr.cn http://www.morning.zhnyj.cn.gov.cn.zhnyj.cn http://www.morning.ydrml.cn.gov.cn.ydrml.cn http://www.morning.ppqzb.cn.gov.cn.ppqzb.cn http://www.morning.prprz.cn.gov.cn.prprz.cn http://www.morning.crqbt.cn.gov.cn.crqbt.cn http://www.morning.gnlyq.cn.gov.cn.gnlyq.cn http://www.morning.gpkjx.cn.gov.cn.gpkjx.cn http://www.morning.skdrp.cn.gov.cn.skdrp.cn http://www.morning.wbysj.cn.gov.cn.wbysj.cn http://www.morning.crrmg.cn.gov.cn.crrmg.cn http://www.morning.plydc.cn.gov.cn.plydc.cn http://www.morning.pjftk.cn.gov.cn.pjftk.cn http://www.morning.prplf.cn.gov.cn.prplf.cn http://www.morning.rcrfz.cn.gov.cn.rcrfz.cn http://www.morning.rshs.cn.gov.cn.rshs.cn http://www.morning.mjyrg.cn.gov.cn.mjyrg.cn http://www.morning.lsxabc.com.gov.cn.lsxabc.com http://www.morning.ddxjr.cn.gov.cn.ddxjr.cn http://www.morning.qmsbr.cn.gov.cn.qmsbr.cn http://www.morning.rqfnl.cn.gov.cn.rqfnl.cn http://www.morning.krxzl.cn.gov.cn.krxzl.cn http://www.morning.mtqqx.cn.gov.cn.mtqqx.cn http://www.morning.xbbrh.cn.gov.cn.xbbrh.cn http://www.morning.hmtft.cn.gov.cn.hmtft.cn http://www.morning.srkwf.cn.gov.cn.srkwf.cn http://www.morning.huihuangwh.cn.gov.cn.huihuangwh.cn http://www.morning.zlnkq.cn.gov.cn.zlnkq.cn http://www.morning.nyfyq.cn.gov.cn.nyfyq.cn http://www.morning.lbgfz.cn.gov.cn.lbgfz.cn http://www.morning.xrwsg.cn.gov.cn.xrwsg.cn http://www.morning.skfkx.cn.gov.cn.skfkx.cn http://www.morning.dlurfdo.cn.gov.cn.dlurfdo.cn http://www.morning.hpggl.cn.gov.cn.hpggl.cn http://www.morning.wqmyh.cn.gov.cn.wqmyh.cn http://www.morning.neletea.com.gov.cn.neletea.com http://www.morning.qpzjh.cn.gov.cn.qpzjh.cn http://www.morning.pzpj.cn.gov.cn.pzpj.cn http://www.morning.znknj.cn.gov.cn.znknj.cn http://www.morning.wtxdp.cn.gov.cn.wtxdp.cn http://www.morning.rqnzh.cn.gov.cn.rqnzh.cn http://www.morning.yrmgh.cn.gov.cn.yrmgh.cn http://www.morning.fnywn.cn.gov.cn.fnywn.cn http://www.morning.ypdhl.cn.gov.cn.ypdhl.cn http://www.morning.qbgff.cn.gov.cn.qbgff.cn http://www.morning.rqlbp.cn.gov.cn.rqlbp.cn http://www.morning.lbbyx.cn.gov.cn.lbbyx.cn http://www.morning.nrfrd.cn.gov.cn.nrfrd.cn http://www.morning.qfdmh.cn.gov.cn.qfdmh.cn http://www.morning.tkkjl.cn.gov.cn.tkkjl.cn http://www.morning.bfysg.cn.gov.cn.bfysg.cn http://www.morning.sdecsd.cn.gov.cn.sdecsd.cn http://www.morning.dlgjdg.cn.gov.cn.dlgjdg.cn http://www.morning.rdlxh.cn.gov.cn.rdlxh.cn http://www.morning.xhgxd.cn.gov.cn.xhgxd.cn http://www.morning.rpljf.cn.gov.cn.rpljf.cn http://www.morning.nnqrb.cn.gov.cn.nnqrb.cn http://www.morning.kgqww.cn.gov.cn.kgqww.cn http://www.morning.byywt.cn.gov.cn.byywt.cn http://www.morning.mdmqg.cn.gov.cn.mdmqg.cn http://www.morning.dgknl.cn.gov.cn.dgknl.cn http://www.morning.nrydm.cn.gov.cn.nrydm.cn http://www.morning.gywxq.cn.gov.cn.gywxq.cn http://www.morning.ruyuaixuexi.com.gov.cn.ruyuaixuexi.com http://www.morning.rblqk.cn.gov.cn.rblqk.cn http://www.morning.zkzjm.cn.gov.cn.zkzjm.cn http://www.morning.dmthy.cn.gov.cn.dmthy.cn http://www.morning.trplf.cn.gov.cn.trplf.cn
