手撕算法---常见排序算法java实现

冒泡排序

是一种比较并交换排序方式。两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。

private void sort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = i+1; j < arr.length; j++) {
                if (arr[i] > arr[j]){
                    swap(arr,i,j );
                }
            }
        }
    }

protected void swap(int[] arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

private void sort2(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            for (int j = arr.length - 2; j >= i ; j--) {
                if (arr[j] > arr[j+1]){
                    swap(arr,j,j+1);
                }
            }
        }
    }

选择排序

每一趟从待排序的记录中选出最小的元素，顺序放在已排好序的序列起始位置，直到全部记录排序完毕。

public void sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int index = i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[index] > arr[j]){
                    index = j;
                }
            }
            swap(arr,index,i);
        }
    }

直接插入排序

将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据。

public void sort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i -1]){
                int tmp = arr[i];
                int j;
                for (j = i-1; j >=0 && arr[j] > tmp ; j--) {
                    arr[j+1] = arr[j];
                }
                arr[j+1] = tmp;
            }
        }
    }

希尔排序

又称为缩小增量排序。把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

public void sort(int[] arr) {
        //增量插入排序
        int increment = arr.length;
        do {
            increment = increment / 3 + 1;
            for (int i = increment; i < arr.length; i+=increment) {
                if (arr[i] < arr[i - increment]){
                    int tmp = arr[i];
                    int j;
                    for (j = i - increment; j >= 0 && arr[j] > tmp; j-=increment) {
                        arr[j + increment] = arr[j];
                    }
                    arr[j+increment] = tmp;
                }
            }

        }while (increment > 1);
    }

堆排序

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便得到一个有序序列。

public void sort(int[] arr) {
        int n = (arr.length - 1)/2;
        for (int i = n; i >= 0 ; i--) {
            maxHeap(arr,i,arr.length - 1);
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr,0,i);
            maxHeap(arr,0,i);
        }
    }

    private void maxHeap(int[] arr, int i, int count) {

        int j = 2 * i + 1;
        int tmp = arr[i];
        while (j < count){
            if (j + 1 < count && arr[j] < arr[j + 1]){
                j++;
            }
            if (arr[j] <= tmp){
                break;
            }
            arr[i] = arr[j];
            i = j;
            j = 2 * i + 1;
        }
        arr[i] = tmp;
    }

归并排序

将待排序的数列分成若干个长度为1的子数列，然后将这些数列两两合并；得到若干个长度为2的有序数列，再将这些数列两两合并；得到若干个长度为4的有序数列，再将它们两两合并；直接合并成一个数列为止。

public void sort(int[] arr) {
        int[] tmp = new int[arr.length];
        mergeSort(arr,tmp,0,arr.length - 1);
    }

    private void mergeSort(int[] arr,int[] tmp, int start, int end) {
        if (start < end){
            int middle = (start + end)/2;
            mergeSort(arr,tmp,start,middle);
            mergeSort(arr,tmp,middle + 1,end);
            merge(arr,tmp,start,middle,end);
        }
    }

    private void merge(int[] arr,int[] tmp,int start, int middle, int end) {
        int m = middle + 1;
        int s = start;
        int k = 0;
        while (start <= middle && m <= end){
            if (arr[start] < arr[m]){
                tmp[k++] = arr[start++];
            }else {
                tmp[k++] = arr[m++];
            }
        }
        while (start <= middle){
            tmp[k++] = arr[start++];
        }
        while (m <= end){
            tmp[k++] = arr[m++];
        }
        for (int i = 0; i < k; i++) {
            arr[s + i] = tmp[i];
        }
    }

快速排序

选择一个基准数，通过一趟排序将要排序的数据分割成独立的两部分；其中一部分的所有数据都比另外一部分的所有数据都要小。然后，再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

public void sort(int[] arr) {
        quickSort(arr,0,arr.length-1);
    }

    private void quickSort(int[] arr, int start, int end) {
        if (start < end){
            int index = quickSortPartition(arr,start,end);
            quickSort(arr,start,index);
            quickSort(arr,index + 1,end);
        }
    }

    private int quickSortPartition(int[] arr, int start, int end) {

        int sentry = arr[start];
        while (start < end){
            //从右边开始
            while (start < end && arr[end] >= sentry){
                end--;
            }
            if (start < end){
                arr[start] = arr[end];
                start++;
            }
            while (start < end && arr[start] <= sentry){
                start++;
            }
            if (start < end){
                arr[end] = arr[start];
                end--;
            }
        }
        arr[start] = sentry;

        return start;
    }

算法复杂度

算法的复杂度