八大经典排序算法的代码实现

冒泡排序：

插入排序：

选择排序：

归并排序：

快速排序:

import java.util.Arrays;

//快排
//时间复杂度最好为O(NlogN). 数组逆序的时候最差，时间复杂度为O(N^2),可以通过随机快排的方式使得其长期时间复杂度期望为O（N*logN）
//空间复杂度最好为O（logN）,数组逆序的时候最差，空间复杂度为O(N)，额外空间主要是每次partition函数返回的二元数组造成的。
//通过随机快排的方式使得其长期时间复杂度期望为O（logN）
//所有递归函数都可以改为非递归版本，因为递归的本质行为是系统在帮我们压栈。改为非递归就是改成我们自己来压栈
// 在工程上是不允许递归行为存在的，因为递归过深可能会导致系统栈爆满，系统不稳定。因此工程上的快排都是非递归版本实现的。
//库函数都是高度优化过的
public class QuickSort {

    static void quickSort(int[] arr, int L, int R) {
        if (L < R) {
//            随机快排， 每次将中间随机一个数和数列最后一个元素交换位置，放置逆序数列产生差的结果
            swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
            int[] p = partition(arr, L, R);
            quickSort(arr, L, p[0] - 1);
            quickSort(arr, p[1] + 1, R);
        }
    }

    static int[] partition(int[] arr, int L, int R) {
        int less = L - 1;
        int more = R;
        int cur = L;
//        以arr[R]作为基准，有了随机快排，这里的arr[R]被重新洗牌
//        这里一次性处理了大于基准等于基准和小于基准的三种情况，速度比传统快排要快
        while (cur < more) {
            if (arr[cur] < arr[R]) {
                // cur++,因为换到cur位置上的一定是比基准arr[R]小的数，直接将其扩到less范围去，且cur指向下一位置
                swap(arr, ++less, cur++);
            } else if (arr[cur] > arr[R]) {
                //交换到cur位置上的数大小位置，交换过去的数一定大于基准arr[R]， 故more--,将其扩到more区域， 但cur位置不变
                swap(arr, --more, cur);
            } else {
                //当前位置和基准arr[R]相等，不扩到less区域和more区域，放在相等区域
                cur++;
            }
        }
        //最后将基准交换到more区域的下一位置
        swap(arr, more, R);
       // 返回相等区域下标,注意此时more位置上是交换过来的基准值，不用加1
        return new int[]{less + 1, more};
    }

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

    public static void main(String[] args) {
        int a[] = {49, 38, 65, 97, 76, 13, 27, 49};
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

堆排序：

import java.util.Arrays;

//堆排序
//堆是完全二叉树
//二叉树的底层可以用线性的结构来储存，也就是说可以用数组来储存一个二叉树，通过数组中下标的关系来表示这个堆。设完全二叉树的一个节点在数组中的下标为i,
//则其父节点的下标应该为(i-1)/2,其左孩子节点应该是2*i+1, 其右孩子节点应该为2*i+2
public class HeapSort {
    static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        else
            for (int i = 0; i < arr.length; i++)
                heapInsert(arr, i);

        int heapSize = arr.length;//堆的大小等于数组的长度
        //交换堆顶和最后一个元素
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);
        }
    }

    static void heapInsert(int[] arr, int index) {
        while (arr[(index - 1) / 2] < arr[index]) {//如果index=0, -1/2=0是根节点
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }

    }

    //    如果堆中有某个元素变小了，将这个元素下沉以保持大根堆的过程heapify
    static void heapify(int[] arr, int index, int heapSize) {
        int left = index * 2 + 1;//在用数组存储的堆中，节点i的左孩子节点是2*i+1, 右节点是2*i+2;
        //这里heapSize是最后一个元素，做堆排的时候，因为是从堆顶交换来的最大值，所以重新heapify要把它排除在外；
        while (left < heapSize) {
            int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            largest = arr[index] > arr[largest] ? index : largest;
            if (largest == index) {
                break;
            }
            swap(arr, largest, index);
            index = largest;
            left = index * 2 + 1;
        }
    }

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

    public static void main(String[] args) {
        int a[] = {49, 38, 65, 97, 76, 13, 27, 49};
        heapSort(a);
        System.out.println(Arrays.toString(a));
    }
}

希尔排序：

基数排序：