常见的排序算法(1)

要点

• 冒泡排序
• 选择排序
• 插入排序
• 希尔排序

1. 冒泡排序

public static int[] bubbleSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                if (arr[j] > arr[i]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        return arr;
    }

    public static int[] bubbleSort2(int[] arr) {
        int len = arr.length;
        boolean flag = false;
        for (int i = 0; i < len; i++) {
            for (int j = 0; j < len - i - 1; j++) {
                if (arr[j + 1] > arr[j]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = true;
                }
            }
            if (!flag) {
                break;
            }
        }
        return arr;
    }

2.选择排序

    public static int[] selectedSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int m = i;
            int j = i + 1;
            for (; j < len; j++) {
                if (arr[j] > arr[m]) {
                    m = j;
                }
            }

            int max = arr[m];
            arr[m] = arr[i];
            arr[i] = max;
        }
        return arr;
    }

3. 插入排序

    public static void insertSort(int[] arr) {

        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int j=i;
            int temp=arr[j];
            while(arr[j-1]>temp) {
                arr[j]=arr[j-1];
                j--;
                if(j==0) {
                    break;
                }
            }
            arr[j]=temp;
        }

    }

4.希尔排序

public static void shellSort(int[] arr) {
        int len = arr.length;
        int gap = len / 2;

        do {
            for (int i = gap; i < len; i++) {
                int k = i;
                int value = arr[i];
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (value > arr[j]) {
                        arr[j + gap] = arr[j];
                        k = j;
                    }
                }
                if (k != i) {
                    arr[k] = value;
                }
            }
            gap = gap / 2;
        } while (gap > 0);

    }