美文网首页Android开发Android技术知识
算法入门（一)

算法入门（一)

作者: 拨云见日aaa | 来源:发表于2019-09-28 20:24 被阅读0次

一、冒泡排序

（1）排序规则

冒泡排序，顾名思义肯定是像冒泡一样，那么冒泡到底是怎么冒得是关键，假如有一个数组｛3，5，6，9，5，7，2，8｝有八个数，冒泡排序第一趟排序是从第一个数与第二个数比如果第一个数大于第二个数则二者互换位置否则不变，接下第二个数与第三个数比，以此类推直达比到第八个数，这样就把最大的数换到了最后，也就是冒到了最后（正所谓枪打出头鸟，你冒泡那你就换到最后位置吧）结果为，｛3，5，6，5，7，2，8，9｝，第二趟排序时忽略已经冒到最后的数（1－7），从一个数比到第七个数将第二大的数冒到倒数第二个位置，以此类推，直到把所有数冒完。


冒泡算法第一趟排序

（2）代码示例

public class BubbleSort{

   public static  void sort(int[] arr){
   if(arr==nullIIarr.length<2){
       return;
      }
    for(int i=arr.length-1;i>=0;i--){
          for(int j=0;j<i;j++){
           if(arr[j]>arr[j+1]){
            swap(arr,j,j+1);
            } 
         }
     }
  }
  public static void swap(int[] arr,int a,int b){
   int temp;
   temp=arr[a];
   arr[a]=arr[b];
   arr[b]=temp; 
   }
}

（3）时间复杂度

  • 平均时间复杂度：O(n2)
  • 额外空间复杂度O(1)
  • 最坏情况时间复杂度O(n2)

(4)稳定性

具有稳定性

二、插入排序

（1）排序规则

插入排序，其实在我看来，它和冒泡的排序很像，只不过换了个动作，为什么这么说呢，插入这回是比谁小了，谁小谁往前挪，好像一个数插到两个数之间，而这个数比左边的数大，比右边的数小。

我来说一下他详细的排序规则，首先第一个数和第二个数比，如果第二个数比第一个数小，那么将一二个数换一下这就是第一趟排序，第二趟排序，第二个数与第三个数比，如果第三个数比第二个数小，两个数换一下，注意不是换完就完了，换到第二个位置的数要和第一个位置的数接着比较，如果它比第一个数要小要接着往前换。 插入的第一第二趟排序过程

（2）代码示例

public class InsertSort{
  public void insertSort(int[] arr){
    if(arr==null&&arr.length){
     return;
    }
     for(int i=0;i<arr.length-1;i++){
        while(i>=0&&arr[i]>arr[i+1]){
           swap(arr,i,i+1);
            i=i-1;
        } 
    }
  }
   public static void swap(int[] arr,int i,int j){
         int temp=arr[i];
         arr[i]=arr[j];
         arr[j]=temp;
      }
}

(3)时间复杂度

  • 平均时间复杂度：O(n2)
  • 额外空间复杂度 O(1)
  • 最坏情况时间复杂度O(n2)

（4）稳定性

具有稳定性

三、希尔排序（插入排序升级版）

（1）排序过程

希尔排序是插入排序的升级版,插入排序适合小样本量，或者基本有序的，当遇到大样本量和完全无序的时候效率就非常低，希尔排序就解决了这个问题，他将样本分块，由小块逐渐变成大块。希尔排序有一个变量gap表示步长的意思，最开始步长（gap）等于样本量的一半，然后每相隔步长的为一组，再把每个小组进行插入排序。然后再把gap除二，再进行分组插入排序。


希尔排序根据步长分组

（2）代码示例

public class ShellSort {
public static void sort(int[] arr) {
    int n=arr.length;
    for(int gap=n/2;gap>0;gap/=2) {
        for(int i=0;i<gap;i++) {
            for(int j=i;j<n-gap;j=j+gap) {
                while(j>=0&&arr[j]>arr[j+gap]) {
                    swap(arr,j,j+gap);
                    j=j-gap;
                }   
                }
        }
    }
}

private static void swap(int[] arr, int i, int j) {
    int temp;
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}
}

(3)时间复杂度

  • 平均时间复杂度O(n1.3)
  • 额外空间复杂度O(1)
  • 最坏情况时间复杂度O(n2)

（4）稳定性

不具有稳定性

四、选择排序

（1）排序规则

选择排序非常简单，设置一个变量用来记录数组最小值的位置，排序第一趟从第一个位置开始进行遍历找出数组中的最小值，然后然后让最小值和第一个位置进行交换。第二趟从第二个位置开始遍历，找出最小值把最小值和第二个位置进行交换，之后重复上面操作，直到开始位置到n。

（2）代码示例

public class SelectSort {
public static void sort(int[] arr) {
    
    if(arr==null||arr.length<2) {
        return;
    }
    
    for(int i=0;i<arr.length;i++) {
        int min=i;
        for(int j=i;j<arr.length;j++) {
            min=arr[min]<arr[j]?min:j;
        }
        swap(arr,i,min);
    }
}
public static void swap(int[] arr,int a,int b) {
    int temp;
    temp=arr[a];
    arr[a]=arr[b];
    arr[b]=temp;
}

(3)时间复杂度

  • 平均时间复杂度：O(n2)
  • 额外空间复杂度O(1)
  • 最坏情况时间复杂度O(n2)

（4）稳定性

不具有稳定性

五、归并排序

（1）排序规则

归并排序的思想是把一个数组从中间一分为二，先把左边排号再把右边排好最后再整体排好，利用递归不断分下去，直至数组左边界和右边界相等即不可再分。排序采用外部排序，申请一个数组，有两个指针第一个指向排好左部分的的第一个数，第二个指向排好右部分的第一个数，比较两个指针指向的数的大小，谁小进数组里，指针向下移动一个位置。左右部分哪一部分的指针指向自己部分的右边界外排结束，如果有没放进数组中的数按顺序拷贝进数组，最后将辅助数组里的数拷贝进原数组。


归并排序思想
外部排序过程

（2）代码示例

public class GuiBing {
public static void guiBingSort(int[] arr) {
    if(arr==null||arr.length<2) {
        return;
    }
    sort(arr,0,arr.length-1);
}
public static void sort(int[] arr,int l,int r) {
    if(l==r) {
        return;
    }
    int mid=l +(r-l)/2;
    sort(arr,l,mid); 
    sort(arr,mid+1,r);
    menage(arr,l,mid,r);
}
private static void menage(int[] arr, int l, int mid, int r) {
    int[] help=new int[r-l+1];
    int curl=l;
    int curr=mid+1;
    int i=0;
    while(curl<=mid&&curr<=r) {
        help[i++]=arr[curl]<arr[curr]?arr[curl++]:arr[curr++];
    }
    while(curl<=mid) {
        help[i++]=arr[curl++];
    }
    while(curr<=r) {
        help[i++]=arr[curr++];
    }
    for(int j=0;j<help.length;j++) {
        arr[l++]=help[j];
    }
}
}

（3）时间复杂度

  • 平均时间复杂度O(n*logn)
  • 额外空间复杂度O(n)
  • 最坏情况时间复杂度O(n*logn)

(4)稳定性

不具有稳定性

六、快速排序

(1)排序规则

此处我说的是优化后的随机快排，随机快排是从数组中随机选取一个位置上的数然后将这个数和最后一个数交换，然后以选择出来出来的数为标准，大于这个数的放左边，等于这个数的放中间，小于这个数的放右边。
至于这个过程，有三个指针（less，more，cur分别代表小于区域，大于区域，位置指针），第一个指向数组第一个位置的前一个位置，第二指向数组最后一个位置，cur指针指向数组第一个位置，比较cur指向的数与当初选出来的数大小，如果小，与less指针指的下一个位置的数交换，less++，cur++，如果等于cur++,如果大于与more指针指的上一个数交换交换完后继续比较交换出来的数与选出来的数的大小，重复上面操作。


快排过程

（2）代码示例

public class QuickSort {
     public static void quickSort(int[] arr) {
         if(arr==null||arr.length<2) {
             return;
         }
         sort(arr,0,arr.length-1);
     }

    private static void sort(int[] arr, int l, int r) {
        if(l<r) {
        int p=(int) ((r-l+1)*Math.random())+l;
        swap(arr,r,p);
        int[] flag=partation(arr,l,r);
        sort(arr,l,flag[0]-1);
        sort(arr,flag[1]+1,r);
        }
    }

    private static int[] partation(int[] arr, int l, int r) {
        int less=l-1;
        int more=r;
        int cur=l;
        while(cur<more) {
            if(arr[cur]<arr[r]) {
                swap(arr,cur,++less);
                cur++;
            }else if(arr[cur]==arr[r]) {
                cur++;
            }else {
                swap(arr,cur,--more);
            }
            
        }
        swap(arr,more,r);
        int[] p=new int[2];
        p[0]=less+1;
        p[1]=more;
        return p;
    }

    private static void swap(int[] arr, int r, int p) {
        int temp;
        temp=arr[r];
        arr[r]=arr[p];
        arr[p]=temp;
    }
}

（3）时间复杂度

  • 平均时间复杂度O(n*logn)
  • 额外空间复杂度O(logn)
  • 最坏情况时间复杂度O(n2)

(4)稳定性

不具有稳定性

七、堆排序

（1）排序规则

堆是一种结构类似完全二叉树但是实质为数组，一个数的位置i他的左孩子为2i+1,右孩子为2i+2,它的父亲为i-1/2；堆排序先构建大顶堆（大顶堆：每个结点的值都大于或等于其左右孩子结点的值），设置一个size等于数组的长度，然后将第一个位置的数和最后一个位置换位置，将size减一，然后调整0到size为大顶堆（调整过程为换到第一个位置的数与他左右孩子中最大的比，如果小，和他孩子换位置），再重复上面的操作，第一个位置和size位置交换，直到size为一。

（2）代码示例

public class HeapSort {
public static void srot(int[] arr) {
    if(arr==null||arr.length<2) {
        return;
    }
    for(int i=0;i<arr.length;i++) {
    heapIsert(arr,i);
    }
    int size=arr.length;
    swap(arr,0,--size);
    while(size>0) {
    heapify(arr,0,size);
    swap(arr,0,--size);
    }
}

private static void heapify(int[] arr, int i, int size) {
    int index=i;
    int left=2*index+1;
    while(left<size) {
    int bigChild=left+1<size&&arr[left+1]>arr[left]?left+1:left;
    int flag=arr[index]>arr[bigChild]?index:bigChild;
    if(flag==index) {
        break;
    }
    swap(arr,flag,index);
    index=flag;
    left=2*index+1;
    }
    
}

private static void heapIsert(int[] arr, int index) {
    while(arr[(index-1)/2]<arr[index]) {
        swap(arr,(index-1)/2,index);
        index=(index-1)/2;
    }
    
}

private static void swap(int[] arr, int i, int index) {
    int temp;
    temp=arr[i];
    arr[i]=arr[index];
    arr[index]=temp;
} 
public static void main(String[] args) {
    int[] arr= {2,5,3,7,3,8,4,5,3,1,8,6,4,3,7};
    srot(arr);
    for(int i=0;i<arr.length;i++) {
        System.out.print(arr[i]+" ");
    }
}
}

(3)时间复杂度

  • 平均时间复杂度O(n*logn)
  • 额外空间复杂度O(1)
  • 最坏情况时间复杂度O(n*logn)

(4)稳定性

不具备稳定性

八、桶排序

(1)排序规则

桶排序是一个概念，把数据放到一个一个桶中，桶排序是不用比较大小的排序，例如有一个数组，里面的数据的范围是0到10的，那么就建11个桶，对应0到10十一个数，然后把数组遍历一遍，把对应的数放到桶中，最后把桶里不为空的复制回数组中就排好了。桶排序分为两个，一个为计数排序一个为基数排序。

  1. 计数排序
    计数排序就是申请一个数组代表桶，遍历一遍给定的数组，然后把对应桶（对应数组位置）里的数加一，每有一个就加一。最后数组里的数不为零的位置，里面的数是几就复制几个角标到数组中。
代码示例
public class CountSort{
    
public static void countSort(int[] arr){
    
if(arr==null||arr.length<2){
return;
}
int max=0;
for(int i=0;i<arr.length;i++){
max=Math.max(arr[i],arr[i+1]);
}
int[] help=new int[max+1];
for(int j=0;j<arr.length;j++){
help[arr[j]]++;
}
for(int m=0;m<help.length;m++){
int index=0;
if(help[m]!=0){
for(int n=0;n<index+help[m];n++){
arr[n]=m;
}
}
}
}
public void mian(String[] args) {
    int[] arr= {3,2,8,4,6,4,5,9};
    countSort(arr);
    for(int i=0;i<arr.length;i++) {
        System.out.print(arr[i]+" ");
    }
}
}

2.基数排序

（2）时间复杂度

  • 平均时间复杂度O(n)
  • 额外空间复杂度O(n)
  • 最坏情况时间复杂度O(n)

（3）稳定性

具备稳定性

相关文章

网友评论

    本文标题：算法入门（一)

    本文链接：https://www.haomeiwen.com/subject/jbxductx.html

    延伸阅读

    深度阅读

    • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

    栏目导航

    热点阅读

    Android开发

    Android技术知识

    关于我们|服务条款|联系我们|算法入门（一)|投稿指南|网站地图|RSS订阅|排版工具|手机版

    提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

    Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

    备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

    本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

    所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！