【2023】java实现常见排序算法

清疚 2023-10-13 12:46 103阅读 0赞

### 1、二分查找法 ###

1.  前提：需要已经排好序的数组
2.  定义左边界L、右边界R，确认搜索范围，循环执行二分查找（3、4）
3.  获取中间索引 M = Floor((L+R)/2)
4.  中间索引的值的值A\[M\] 与待搜索的值T进行比较，
    
    1.  A\[M\] == T表示找到，返回中间索引
    2.  A\[M\]>T ,中间值右侧的其他元素都大于T(查找的值)，无需比较，就把中间索引M-1设置为右边界，重新查找；
    3.  A\[M\]>T ,中间值左侧的其他元素都小于T(查找的值)，无需比较，就把中间索引M-1设置为右边界，重新查找；

使用二分查找时，奇数二分取中间值，

偶数二分取中间靠左值

/**
         *二分查找
    *@parama查找数组
    *@paramt查找的值
    *@return
    */
    private static int binarySearch1(int[] a,int t) {
        
    //        l:左边索引，r右边索引，中间索引
            int l = 0 ,r=a.length -1,m;
            int i=1;
            while (l<=r){
        
                m=(l+r)>>>1;
                System.out.println("第"+i+"轮：左边下标--"+l+",右边下标--"+r+",中间下标--"+m+"中间下标的值--"+a[m]);
                if (a[m] == t){
        
                    return m;  //表示查找到了
                }else if (a[m] >t){
        
                    r=m-1;   //把右边界设置为中间索引-1
                }else {
        
                    l=m+1;   //把左边界设置为中间索引+1
                }
                i++;
            }
            return -1;
        }

### 2、冒泡排序 ###

*  概念：
    
    1.  每次比较相邻的两个数，若a\[j\]>a\[j+1\]的元素，则交换两个元素，两两都比较一遍，称为一轮冒泡，结果是让最大的元素排至最右边
    2.  重复上面的步骤直到整个数组有序
 *  优化方式：
    
     *  每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为0，代表整个数组有序，直接退出外曾循环
 *  方案一：
    
        /**
             *冒泡排序
        *@parama
        */
        public static void bubble(int[] a){
              
        //        循环次数
                for (int j = 0; j < a.length-1; j++) {
              
                    boolean swapped = false;
        //          比较次数
        //            因为每次都会有一位排好序的数，所有比较次数可以设置为每次都比上一次少1，以此减少比较次数
                    for (int i = 0; i < a.length-1-j; i++) {
              
                        System.out.println("比较次数："+i);
        
        //             每一次交换，把swapped改为true
                        if (a[i] > a[i+1]){
              
        										swap(a,i,i+1);
                            swapped = true;
                        }
                    }
                    System.out.println("第"+j+"轮，循环"+Arrays.toString(a));
        //          没产生交换时退出循环
                    if (!swapped){
              
                        break;
                    }
                }
            }
 *  方案二：
    
        /**
             *冒泡排序
        *@parama
        */
        public static void bubble(int[] a){
              
        //        每一轮交换次数
                int n = a.length-1;
        //        循环次数
                while (true){
              
                    boolean swapped = false;
                    int last = 0;  //表示最后异常交换的下标
        
        //          比较次数
        //            因为每次都会有一位排好序的数，所有比较次数可以设置为每次都比上一次少1，以此减少比较次数
                    for (int i = 0; i < n; i++) {
              
                        System.out.println("比较次数："+i);
                        if (a[i] > a[i+1]){
              
        swap(a,i,i+1);
                            last = i;  //每一轮比较的交换次数
                        }
                    }
                    n = last;  //把最后一轮比较的下标赋给n
        
                    System.out.println("第n轮，循环"+Arrays.toString(a));
        //            当最后一轮比较的下标是0时，代表比较完毕，没有产生交换，退出循环
                    if (n == 0){
              
                        break;
                    }
                }
            }

### 3、选择排序 ###

*  概述：
    
     *  将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序子集
     *  重复以上步骤，直到整个数组有序
 *  与冒泡排序比较
    
     *  两者平均复杂度都是 O ( n 2 ) O(n^2) O(n2)
     *  选择排序一般要快于冒泡，因为其交换次数少
     *  但如果集合有序度高，冒泡则会优于选择，因为冒泡比较时，可以记录是否有交换，来判断集合是否已经有序，而选择排序则不行
     *  冒泡属于稳定排序，不会出现数值相同时出现交换的情况，而选择属于不稳定的排序

### 4、快速排序 ###

*  概述
    
    1.  每一轮排序选择一个基准点进行分区
        
        1.  让小于基准点的元素进入一个分区，大于基准点的元素进入另外一个分区
        2.  当分区完成时，基准点元素的位置就是其最终位置
    2.  在子分区内重复以上过程，直至子分区元素个数少于等于1，代表排序完成。这主要体现了一个分而治之的思想
 *  分类：
    
    1.  单边循环快排
        
        1.  选择最右元素作为基准点元素
        2.  j 指针负责找到比基准点小的元素，一旦找到则与 i 进行交换
        3.  i 指针维护小于基准点元素的边界，也是每次交换的目标索引
        4.  最后基准点与 i 交换，i 即为分区位置
    2.  双边循环快排
        
        1.  选择最左元素作为基准点元素
        2.  j 指针负责从右向左找比基准点小的元素，i 指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至 i，j 相交
        3.  最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置
        4.  要点
            
            1.  基准点在左边，并且要先 j 后 i
            2.  while( **i** **< j** && a\[j\] > pv ) j-- //都必须加 **i** **< j**
            3.  while ( **i** **< j** && a\[i\] **<=** pv ) i++ //必须加≤

#### 1、单边快排代码实现 ####

public static void quick(int[] a,int l,int h){
        
                 if (l>=h){
        
                     return;
                 }
         //        p:索引值 ，用于做子分区的左右边界
                 int p =partition(a, l, h);
         quick(a, l,p-1); //         左边分区的范围确认
         quick(a, p+1,h); //        右边分区的范围确认
         
             }
         
         /**
              *@Description//TODO单边快排
         *@param:a数组
         *@param:l左边界
         *@param:h右边界
         *@return:int表示基准点元素所在的正确索引，用它确认下一轮分区的边界
         **/
         private static int partition(int[] a,int l,int h){
        
         
                 int pv = a[h];  //      基准点的值
                 int i = l;
                 for (int j = l;j < h; j++){
        
                     if(a[j] < pv){
        
         
                         if (i != j){
          //当i和j指向的是同一个元素时，代表没必要交换，
         swap(a,i,j);
                         }
                         i++;
                     }
                 }
                 if (i != h){
        
         swap(a,h,i);
                 }
                 System.out.println("比较后的值："+Arrays.toString(a)+" 基准点下标="+i);
                 return i;
             }

#### 2、双边快排代码实现 ####

public static void quick(int[] a,int l,int h){
        
                   if (l>=h){
        
                       return;
                   }
           //        p:索引值 ，用于做子分区的左右边界
                   int p =partition(a, l, h);
           quick(a, l,p-1); //         左边分区的范围确认
           quick(a, p+1,h); //        右边分区的范围确认
           
               }
           
           /**
                *@Description//TODO双边快排
           *@param:a数组
           *@param:l左边界
           *@param:h右边界
           *@return:int表示基准点元素所在的正确索引，用它确认下一轮分区的边界
           **/
           private static int partition(int[] a,int l,int h){
        
                   int pv = a[l];
                   int i = l;
                   int j = h;
                   while (i < j){
        
           //          寻找的顺序也不能更改，必须先执行j从右向左，再执行i从左向右寻找
           
            //            j从右向左找小的 ，必须加i < j 条件，因为不加会出现i走过头，跑到比j大的位置取拿取元素
                       while (i < j && a[j] > pv){
        
                           j--;
                       }
           //            i从左向右找大的  ，a[i] <= pv必须加等于，因为a[i]最开始是从左边界开始，就是等于pv
                       while (i < j && a[i] <= pv){
        
                           i++;
                       }
           
           swap(a,i,j);
                   }
           //          基准点和j交换位置，j代表分区位置
           swap(a,l,j);
                   System.out.println(Arrays.toString(a)+" j="+j);
                   return j;
           
               }
           ```