排序算法

2021-12-15 15:48:57   0  举报





AI智能生成

白话一下：对排序算法的理解附相对应的代码，每行代码都有相应的解释

排序算法

归并排序

插入排序

冒泡排序

选择排序

模板推荐

作者其他创作

大纲/内容

时间复杂度

每种输入的运行时间，乘以那种输入出现的概率 一个有关输入的统计分布的假设

舍去低阶项和常数项，n趋于无限大，最里层执行的时间

O(1)   一次查询即可得到答案。这种是最优的。比如nio的epoll的回调事件，有了事件直接回调通知selector，selector直接就可以定位到这个通道来获取事件。

O(N) 代表这个方法：N个元素最慢就需要N次查询才能定位到目标。比如NIO的select方法，数组的遍历这类，如果要查最后一个元素，直接遍历就是需要N次查询。

O(logn) 基础知识：log默认以10为底，n的对数。logn的结果就是10的多少次方=n。比如log10=1。以2为底，n的对数。 代表这个方法：复杂度随着元素数量增多，增速却在慢慢降低。比如二分查找法，时间复杂度就是O(log(n)) 算法时间复杂度为O(log(n))时，不同底数对应的时间复杂度的倍数关系为常数，不会随着底数的不同而不同，因此可以将不同底数的对数函数所代表的时间复杂度，当作是同一类复杂度处理，即抽象成一类问题。 推论：比如N个元素，最多需要查询N/2次，设最多需要查询X次。第一次，元素总共N个，最多查询N/2次。第二次查询，元素就剩N/2个了，那此时最多查询次数就是(N/2)/2，最后就是只需要一次查询(也及时次数是1)。即二分查找在最坏的情况下是n/(2的1次方),n/(2的2次方)，n/n/(2的3次方)。。。。 一直到查询n/(2的x次方)为止。这样经过了x次查询定位到了数据，n/(2的x次方)=1经过x次查询才能查到目标元素，n=2的x次方，x=log(n)

白话算法+代码demo

冒泡排序

/**  * 冒泡排序，每进行一次大循环，最值就会冒泡一样出来  * @param args  */ public static void main(String[] args) {  int[] arr={5,4,9,2,1};  //i为每次循环比较时的，冒泡后剩余元素的最大索引值  //比如第二次，已经冒泡出一个，剩下四个元素，那就是0-4中间的比较，最大索引值为4  //最后一次，那就是冒泡出了三个，剩下俩元素，那就是0-1中间的比较，最大索引值为1  for (int i = arr.length-1; i >0; i--) {   //里面层，依次比较临近元素，比较的最大值放在右边，这样最后冒泡出的最大值就在最右边。   //每次就是索引0和1比，1和2比，。。。最后就是i-1和i比。因此j最大为i-1   for (int j = 0; j < i; j++) {    if (arr[j]>arr[j+1]){     int temp=arr[j+1];     arr[j+1]=arr[j];     arr[j]=temp;    }   }  } }

O(n*n)

选择排序

/**  * 选择排序，每进行一次大循环就选择出当前数组最小(或最大)的数。  * @param args  */ public static void main(String[] args) {  int[] arr={5,4,9,2,1};  //每执行一次循环，就把最小的元素放到最左边。  //外层是核心元素索引,  for (int i = 0; i <= arr.length-2; i++) {   //里层是每次循环要比的元素，最小就是核心元素后面那个，最大就是数组最后一个元素   for (int j = i+1; j <= arr.length-1; j++) {    if (arr[j]<arr[i]){     int temp=arr[i];     arr[i]=arr[j];     arr[j]=temp;    }   }  } }

O(n*n)

插入排序

/**  * 插入排序：就是从数组目前的第二个元素开始，依次和前面的比较后再插入的。  * 就像数组原来就一个元素，后面的元素插入前都与已存在的元素进行了比较。  * {5,4,22,1,9,13};就当做当前只有一个元素5，后面的元素依次取出，并与已插入的元素(也就是前面的元素)进行比较大小来确定插入新数组所在的索引位置  * 4，5==》4,5,22==》1,4,5,22==》1,4,5,9,22==》1,4,5,9,13,22  * @param arr  */ //此次是从小到大排序 public static void main(String[] args) {  int[] arr={5,4,9,6,1};  //外层循环意义：新插入元素的老索引.i从1开始，因为第一个元素直接插入不用比较  for (int i = 1; i <= arr.length-1; i++) {   //新插入元素需要与已插入的所有元素进行依次比较，   //比如插入的是第四个元素6，此时数组为{4,5,9,6,1}那就要6和9比，交换，6再和5比，不交换，5再和4比，不交换。   for (int j = i-1; j >= 0; j--) {    if (arr[j+1]<arr[j]){     int temp=arr[j+1];     arr[j+1]=arr[j];     arr[j]=temp;    }else{//因为是依次进行比较的，当不进行交换时，前面的元素都是已经排序插入的，就不需要再比较了     j=0;    }   }  } }

O(n*n)

归并排序

/**  * @ClassName T3  * @description:$将数组当做二叉树，思考会更简单  * @author: 李杰  * @create: 2021-12-01 00:27  * @Version 1.0  **/ public class T {     /**      * 归并排序：先把数组依次拆分，拆分到每个组只有一个，再进行合并。类似于树的递归运算。      * @param args      */     public static void main(String[] args) {         int[] arr={5,4,22,1,9,13};         sortArr(arr,0,arr.length-1);         for (int i = 0; i < arr.length; i++) {             System.out.println(arr[i]);         }     }     private static void sortArr(int[] arr, int start, int end) {         //首先判断是否已经不用再拆分了         if (end>start){             //拆分             int mid=(start+end)/2;             sortArr(arr, start, mid);             sortArr(arr, mid+1, end);             merge(arr,start,mid,mid+1,end);         }else{             //不用拆分了             System.out.println("拆分到最小了，反转向上合并");         }     }     private static void merge(int[] arr, int start1, int end1, int start2, int end2) {         //定义一个临时数组：存放俩数组合并后的所有元素         int[] temp=new int[end2-start1+1];         //定义左数组的未比较元素的最小索引         int left=start1;         //定义右数组的未比较元素的最小索引         int right=start2;         //依次取出每个数组的最小索引元素来比较,将最小元素放到temp         for (int i = 0; i < temp.length; i++) {             if (left>end1){                 //左数组已经没有元素了，不用比较，直接将右数组元素放入temp                 temp[i]=arr[right];                 right++;             }else if (right>end2){                 //右数组已经没有元素了，不用比较，直接将左数组元素放入temp                 temp[i]=arr[left];                 left++;             }else{//左右数组都有元素，则进行比较                 if (arr[left]>arr[right]){                     temp[i]=arr[right];                     right++;                 }else{                     temp[i]=arr[left];                     left++;                 }             }         }         //将排序归并的数组temp覆盖掉原数组         int index=start1;         for (int i = 0; i < temp.length; i++) {             arr[index]=temp[i];             index++;         }     } }

O(nlogn)