四种排序算法+二分法查找算法

客官°小女子只卖身不卖艺 2024-02-17 19:52 61阅读 0赞

## 1 四种排序算法 ##

### ①快速排序 ###

![这里写图片描述][SouthEast]

/**
     * 快速排序（二分法排序）
     */
    class QuickSort{
        /*
         * 交换并返回分界点
         */
        private int boundary(int[] array, int startIndex, int endIndex) {
            int standard = array[startIndex]; // 定义标准
            int leftIndex = startIndex; // 左指针
            int rightIndex = endIndex; // 右指针
    
            while(leftIndex < rightIndex) {
                while(leftIndex < rightIndex && array[rightIndex] >= standard) {
                    rightIndex--;
                }
                array[leftIndex] = array[rightIndex];
    
                while(leftIndex < rightIndex && array[leftIndex] <= standard) {
                    leftIndex++;
                }
                array[rightIndex] = array[leftIndex];
            }
    
            array[leftIndex] = standard;
            return leftIndex;
        }
        public void sort(int left, int right, int[] array) {
            if(left>=right) {
                return;
            }
            int boundary = boundary(array, left, right);
    
            sort(left, boundary-1, array);
            sort(boundary+1, right, array);
        }
    }

### ②插入排序 ###

class InsertSort {
        
        public void sort(int a[]) {
            for(int i=0;i<a.length;i++) {
                int insertVal = a[i];
                int index = i-1;
                while(index>=0 && insertVal<a[index]) {
                    a[index+1] = a[index];
                    index--;
                }
            }
        }   
    }

### ③ 选择排序 ###

*  找到最小的，和第一个位置交换
 *  找到次小的，和第二个位置交换
 *  以此类推，排序完成

class Select {
        public void sort(int a[]) {
    
            int temp=0;
            for(int i=0; i<a.length-1; i++) {
                int min = a[i];
                int minIndex = i;
                for(int j=i+1; j<a.length; j++) {
                    if(min>a[j]) {
                        min = a[j];
                        minIndex=j;
                    }
                }
                temp = a[i];
                a[i] = a[minIndex];
                a[minIndex]=temp;
            }
    
        }
    }

### ④ 冒泡排序 ###

class Bubble {
        public void sort(int a[]) {
            int temp = 0;
            for(int i =0; i<a.length-1; i++) {
                for (int j=0; j<a.length-i-1; j++) {
                    if(a[j] > a[j+1] ) {
                        temp = a[j];
                        a[j] = a[j+1];
                        a[j+1] = temp;
                    }
                }
            }
        }
    }

## 2 二分查找算法 ##

/**
     * 二分查找
     */
    class BinaryFind{
        public void find(int leftIndex, int rightIndex, int val, int arr[]) {
            int midIndex  = (rightIndex + leftIndex) / 2;
            int midVal = arr[midIndex];
    
            if(rightIndex>=leftIndex) {
                if(midVal>val) {
                    find(leftIndex, midIndex-1, val, arr);
                } else if(midVal < val) {
                    find(midIndex+1, rightIndex, val, arr);
                } else if(midVal==val) {
                    System.out.println("找到下标:" + midIndex);
                }
            }
        }
    }

[SouthEast]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/a92997dea4b646829dd4225cd796a111.png