数据结构基本排序-Java

1、二分法

public class binarySeach_1 {
    public static int recursionBinarySearch(int[] arr,int key,int low,int high) {
        //入口函数判断
        if (key<arr[low]||key>arr[high]||low>high){
            return  -1;
        }
        int mid=(low+high)/2;
        if(arr[mid]>key){
            return  recursionBinarySearch(arr,key,low,mid-1);
        }else  if(arr[mid]<key){
            return  recursionBinarySearch(arr,key,mid+1,high);
        }else {
            return  mid;
        }
    }
}

1.1、二分法测试用例

   public static void main(String[] args) {
        int [] arr= {1,2,5,9,10,40,50,90};
        int key=9;
        int position=recursionBinarySearch(arr,key,0,arr.length-1);
        if(position==-1){
            System.out.println("查找不存在");
        }else {
            System.out.println("查找的为"+position);
        }
    }

2、冒泡排序

public class bubbleSort {
    public static void BubbleSort(int[] a, int n) {
        int i, k = n;
        boolean flag;
        flag = true;
        while (flag) {
            flag = false;
            for (i = 1; i < k; i++) {
                if (a[i] < a[i - 1]) {
                    int temp;
                    temp = a[i];
                    a[i] = a[i - 1];
                    a[i - 1] =temp;
                    flag = true;
                }
            }
            k--;
        }
    }
}

2.2、冒泡排序测试用例

    public static void main(String[] args) {
        int[] arr = {1, 5, 6, 9, 4, 8, 2, 3};
        BubbleSort(arr, arr.length);
        /*for (int i = 0; i < a.length; i++) {
            System.out.print(a[i]+",");
        }*/

        for (int i : arr) {
            System.out.print(i + ",");
        }
    }

3、选择排序

public class selectSort {
    public static void SelectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
        for (int j = i + 1; j < arr.length; j++) {
                if (arr[j]<arr[minIndex])
                    minIndex=j;
            }

        if(i!=minIndex){
                int temp;
                temp=arr[i];
                arr[i]=arr[minIndex];
                arr[minIndex]=temp;
            }
        }
    }
}

3.1、选择排序测试用例

 public static void main(String[] args) {
        int[] arr={1,5,6,8,7,4,3,9};
        SelectSort(arr);
        for (int i : arr) {
            System.out.print(i+",");
        }
    }

4、直接插入排序

public class InsertSort {
    public static void main(String[] args) {
        int[]  arr={1,465,64,45,8,78,25,3,5};
        insertSort(arr);
        for (int i : arr) {
            System.out.print(i+",");
        }

    }
    public static  void  insertSort(int[] arr){
        for (int i=1;i<arr.length;i++){
            int temp=arr[i];
            int j=i-1;
            for(;j>0;j--){
                if (arr[j]>temp){
                    arr[j+1]=arr[j];
                }else {
                    break;
                }
            }
            arr[j+1]=temp;
        }
    }
}

5、快速排序

public class QuickSort {
    private static int partition(int[] arr, int low, int high) {
        int pivot = arr[low];     //枢轴记录
        while (low < high) {
            while (low < high && arr[high] >= pivot) --high;
            arr[low] = arr[high];             //交换比枢轴小的记录到左端
            while (low < high && arr[low] <= pivot) ++low;
            arr[high] = arr[low];           //交换比枢轴小的记录到右端
        }
        //扫描完成，枢轴到位
        arr[low] = pivot;
        //返回的是枢轴的位置
        return low;
    }
    private static void qsort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);        //将数组分为两部分
            qsort(arr, low, pivot - 1);                   //递归排序左子数组
            qsort(arr, pivot + 1, high);                  //递归排序右子数组
        }
    }
}

5.1、快速排序测试用例

 public static void main(String[] args) {
        int[] arr ={1,6,8,5,3,4,7,9,10};
        qsort(arr, 0, arr.length - 1);
        for (int i : arr) {
            System.out.print(i+",");
        }
    }