JavaSE - 排序算法

JavaSE - 排序算法

Scroll Down

数组与排序

杨辉三角

Scanner m = new Scanner(System.in);
        int s = m.nextInt();
        int[][] str = new int[s][s];
        for (int i=0;i<str.length;i++){
            for (int j = 0;j<=i;j++){
                if(j == 0||j==i){
                    str[i][j] = 1;
                }
                else{
                    str[i][j] = str[i-1][j]+str[i-1][j-1];
                }
            }
        }
        //点睛之笔 j<=i ----> 解决了数组的列会越界的问题
        for (int i = 0;i < str.length;i++){
            for (int j=0;j<=i;j++){
                System.out.print(str[i][j]+" ");
            }
            System.out.println();
        }
    }

二分查找

前提是数组有序

static
    int BinarySearch(int[] arr, int ele) {
        int minIndex = 0;
        int maxIndex = arr.length - 1;
        int centerIndex = (minIndex + maxIndex) / 2;
        while (minIndex <= maxIndex) {
            if (ele == arr[centerIndex]) {
                return centerIndex;
            } else if (ele > arr[centerIndex]) {
                minIndex = centerIndex + 1;
            } else {
                maxIndex = centerIndex - 1;
            }
            centerIndex = (minIndex + maxIndex) / 2;
        }
        return -1;
    }

冒泡排序

package com.sukai;

import java.util.Arrays;

/**
 * 解决冒泡排序算法
 */
public class Main {
    private static int[] arr = {4,3,2,1,7,5,6};
    public static void change(int a,int b){
        int temp = 0;
        temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
    public static void main(String[] args) {
        for (int i = 0;i < arr.length;i++){
            for (int j = 0;j<arr.length-i-1;j++){
                if(arr[j]>arr[j+1]) {
                change(j, j + 1);
                }
            }
        }
        //使用Arrays.toString()方法
//        for (int i = 0;i<arr.length;i++)
//        System.out.println(arr[i]);
        System.out.println(Arrays.toString(arr));
    }
}

选择排序

public class Main {
    public static void FastSort() {
        int[] arr = {4, 3, 2, 5, 7, 6, 8};
        for (int i = 0; i < arr.length; i++) {
            int pos = 0;
            for (int j = 1; j < arr.length-i; j++) {
                if (arr[pos] < arr[j]) {
                    pos = j;
                }
            }
            int temp = 0;
            temp = arr[pos];
            arr[pos] = arr[arr.length-i-1];
            arr[arr.length-i-1] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void main(String[] args)
    {
        Main.FastSort();
    }
}

插入排序

public void Select_Sort(){
        int[] array = new int[]{2,7,6,4,8,5,3};
        for(int i = 1;i<array.length;i++){
            int pos = array[i];
            for(int j=i;j>0;--j){
                if(array[j-1]>array[j]){
                    array[j] = array[j-1];
                    array[j-1] = pos;
                }else{
                    array[j] = pos;
                    break;
                }
            }
        }
        System.out.print(Arrays.toString(array));
    }

快速排序

public static void quickSort(int[] arr,int low,int high){
        if(low>high){
            return;
        }
        int t;
        int i = low;
        int j = high;
        //temp就是基准位
        int temp = arr[low];
        while (i<j) {

            while (temp<=arr[j]&&i<j) {
                j--; }

            while (temp>=arr[i]&&i<j) {
                i++; }

            if (i<j) {
            t = arr[j]; arr[j] = arr[i]; arr[i] = t;
        }
    }

    arr[low] = arr[i];
    arr[i] = temp;
    quickSort(arr, low, j-1);
    quickSort(arr, j+1, high);

归并排序