常见排序算法

冒泡排序：

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个；
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最3.后的元素应该会是最大的数；
4.针对所有的元素重复以上的步骤，除了最后一个；
5.重复步骤1~3，直到排序完成。

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

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

选择排序

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

public static int[] selectSort(int[] arr){
        int minIndex = 0;
        for (int i = 0; i < arr.length; i++) {
            minIndex = i;
            //找到最小索引并交换
            for (int j = i; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }

最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

插入排序

1.从第一个元素开始，该元素可以认为已经被排序；
2.取出下一个元素，在已经排序的元素序列中从后向前扫描；
3.如果该元素（已排序）大于新元素，将该元素移到下一位置；
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
5.将新元素插入到该位置后；
6.重复步骤2~5。

public static int[] insertSort(int[] arr){
        if (arr == null) {
            return arr;
        }
        for (int i = 0; i < arr.length-1; i++) {
            int current = arr[i+1];
            int preIndex = i;
            while(preIndex >=0 && current < arr[preIndex]){
                arr[preIndex+1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
        return arr;
    }

快速排序

image.png
image.png
image.png
image.png image.png

//4快速排序
    public static void quicksort(int[] arr, int left, int right){
        if (left > right) {
            return;
        }
        //指向最左边
        int i = left;
        //指向最右边
        int j = right;
        //保存基准数
        int base = arr[left];
        
        //i和j未相遇继续遍历
        while(i != j){
            //先由j从右向左遍历，找到比基准数小的就停下
            while (arr[j] >= base && j > i) {
                j--;//向左移动
            }
            
            //i从左往右移动,找到比基准数大的停下
            while (arr[i] <= base && j > i) {
                i++;
            }
            
            //交换ij位置的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //i = j时，交换基准数与ij相遇位置的元素
        arr[left] = arr[i];
        arr[i] = base;
        //递归排基准数的左边
        quicksort(arr, left, i-1);
        //递归排基准数的右边
        quicksort(arr, j+1, right);
    }

最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)

希尔排序

image.png
image.png

public static int[] ShellSort(int[] array) {
        int len = array.length;
        int temp, gap = len / 2;
        while (gap > 0) {
            for (int i = gap; i < len; i++) {
                temp = array[i];
                int preIndex = i - gap;
                while (preIndex >= 0 && array[preIndex] > temp) {
                    array[preIndex + gap] = array[preIndex];
                    preIndex -= gap;
                }
                array[preIndex + gap] = temp;
            }
            gap /= 2;
        }
        return array;
    }