几个基本算法（二分查找、冒泡排序、插入排序、快速排序、希尔排序）

2021-12-21 145

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 几个基本算法（二分查找、冒泡排序、插入排序、快速排序、希尔排序）

二分查找

二分查找又叫折半查找，前提条件是待插入的数组必须是有序的，

原理：二分查找的每次都从中间查找，如果比中间小，就去左边，如果比中间大，就去右边。

普通实现

public class BinarySearch {
   public static void main(String[] args) {
   //测试一下
     int []a= {3,5,7,9,11,15};
     System.out.println("查找12："+biSearch(a, 12));
  }
   //折半查找方法
   public static int biSearch(int a[],int r) {
   int l=0;
   int h=a.length-1;
   int temp;
   while(l<=h) {
     int mid=(l+h)/2;           //中间位置
     if(r<a[mid]) {                 //向左寻找
       h=mid-1;
     }else if(r>a[mid]) {        //向右寻找
      l=mid+1;
     }else if(r==a[mid]) {
       return mid+1;               //返回值是数组的第几个数
     }
   }
  return -1;                              //未查到
   }
}

递归实现

 static int binSearch(int [] a,int low,int high,int r){
     int mid=(low+high)/2;
     if(low>high){
      return -1;
   }else if (r==a[mid]){
      return mid;
   }else if(r<a[mid]){
      return binSearch(a, low, mid-1, r);      //向左
   }else if(r>a[mid]){
      return binSearch(a, mid+1, high, r);    //向右
   }
     return -1;
   }

冒泡排序

冒泡排序的原理是循环遍历要排序的数列，每次遍历，从后往前比较两个相邻的数大小，如果前一个数比后一个数大的话，就交换两个数的位置，这样一来，最大的数就到了队列的后面，所以被称为冒泡排序。

一个数列{20,40,30,10,60,50}排序过程如下图：

实现：

public class BubbleSort {
/*冒泡排序：
 * 比较前后两个相邻的数据，如果前面的数据大于后面的数据，就将两个数据作交换
 *遍历一遍之后，就将最大的数据沉到了最后面
 *
 */
  public static void main(String[] args) {
    int []a= {8,5,9,4,3,6};
    int []n =bubbleSort(a);
    for (int i = 0; i < n.length; i++) {
      System.out.print(a[i]+"\t");
    }
  }
  static int [] bubbleSort(int [] a) {
     for(int i=0;i<a.length-1;i++) {
       for(int j=0;j<a.length-1-i;j++) {
         if(a[j]>a[j+1]) {
           int temp=a[j+1];
           a[j+1]=a[j];
           a[j]=temp;
         }
       }
     }
    return a;
  }
}

插入排序

原理：通过构建有序数列，对于未排序数列，从后往前扫描，取出，和有序数列对比，插入到相应的位置。

一个数列{20,40,30,10,60,50}排序过程如下图：

实现：

public class InsertSort {
  /*插入排序：
   * 假设有一组无序序列 R0, R1, ... , RN-1。
   (1) 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。
   (2) 然后，我们要依次把 R1, R2, ... , RN-1 插入到这个有序序列中。所以，
    我们需要一个外部循环，从下标 1 扫描到 N-1 。
   (3) 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。
    由前面所述，我们可知，插入Ri时，前 i-1 个数肯定已经是有序了。
    所以我们需要将Ri 和R0 ~ Ri-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1 开始向 0 进行扫描。
   *
   */
  public static void main(String[] args) {
    int []a= {4,7,5,3,8,6};
    for (int i : insertSort(a)) {
      System.out.print(i+"\t");
    }
  }
  public static int [] insertSort(int [] arr) {
    for(int i=1;i<arr.length;i++) {       //第一个数视为有序，所以从第二个数开始
      int j=0;
      int insertVal=arr[i];                      //取下标为i的数，和前面的有序数作比较，插入适当位置
       //因为前i-1个数都是从小到大的有序序列，所以只要当前比较的数(a[j])比insertVal大，就把这个数后移一位
      for(j=i-1;j>=0&&insertVal<arr[j];j--) {
        arr[j+1]=arr[j];
      }
      arr[j+1]=insertVal;
    }
    return arr;
  }
}

快速排序

原理：快速排序采用分治的策略，选择一个基准值，比基准值小的都在左边序列，比基准值大的都在右边序列。·

一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有

继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比

较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的

值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值

来说，左右两边就是有序的了。

觉得参考【4】的说法更好理解，快速排序就是挖萝卜，填萝卜的过程。

实现

/*
  快速排序：
  基本方法：
  1．先从数列中取出一个数作为基准数。
  2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
  3．再对左右区间重复第二步，直到各区间只有一个数。
  步骤：
  1、选取一个基准数
  2、从后往前比较，没有继续找，找到比基准数小的就交换位置
  3、找到比基准数小的数以后，从前往后比较，找到比基准数大的就交换位置
  4、重复执行2、3两步
 */
public class QuickSort {
    public static void main(String[] args) {
      int [] a={3,5,2,8,5,4,12,9,7};
      sort(a,0,a.length-1);
        for (int i = 0; i <a.length ; i++) {
            System.out.print(a[i]+"\t");
        }
    }
    public static void sort(int []a,int low,int high){
        int start = low;
        int end = high;
        int key = a[low];      //选择基准值
        while(end>start){
           //从后往前比较
            while(end>start&&a[end]>=key)
           //如果没有比关键值小的，比较下一个，直到有比关键值小的交换位置，然后又从前往后比较
                end--;
            if(a[end]<=key){
                int temp = a[end];
                a[end] = a[start];
                a[start] = temp;
            }
        //从前往后比较
            while(end>start&&a[start]<=key)
        //如果没有比关键值大的，比较下一个，直到有比关键值大的交换位置
                start++;
            if(a[start]>=key){
                int temp = a[start];
                a[start] = a[end];
                a[end] = temp;
            }
            //此时第一次循环比较结束，关键值的位置已经确定了。左边的值都比关键值小，右边的
            //值都比关键值大，但是两边的顺序还有可能是不一样的，进行下面的递归调用
        }
        //递归
        if(start>low) sort(a,low,start-1);//左边序列。第一个索引位置到关键值索引-1
        if(end<high) sort(a,end+1,high);//右边序列。从关键值索引+1 到最后一个
    }
}

希尔排序

原理：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

它本质上是一种一种分组插入方法。

以数列{80,30,60,40,20,10,50,70}为例：

第一趟：

第二趟：

第三趟：

实现

public class ShellSort {
    /*
      希尔排序：
      思路：
      先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列
       中的记录“基本有序”时，再对全体记录进行依次直接插入排序。
       步骤：
       1、选择一个增量序列t1,t2,……tk（递减，tk=1）
       2、按照选定的增量k,对序列进行k次排序
       3、每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进
      行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长
       度。
     */
    public static void main(String[] args) {
       int[]a={11,32,23,45,12,15};
       sheelSort(a);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+"\t");
        }
    }
    static void sheelSort(int[] a){
       int dk=a.length/2;         //增量
        while( dk >= 1 ){
            shellInsertSort(a, dk);
            dk = dk/2;
        }
    }
    /*
      给希尔排序用的插入排序
     */
     static void shellInsertSort(int [] a,int dk){
       //和插入排序差不多，插入排序增量是1，这里的增量自定义的值dk
       for(int i=dk;i<a.length;i++){
           int insertVal=a[i];
           int j=0;
           for(j=i-1;a[j]>insertVal&&j>0;j--){            //只要当前比较的数(a[j])比insertVal大，就把这个数后移一位
               a[j+1]=a[j];
           }
           a[j+1]=insertVal;                     //在最终的位置插入
       }
    }
}