一、冒泡排序

????????冒泡排序的基本思想是：从数组下标数值小开始，依次比较相邻元素的值，使较大的数逐渐从前往后移动，像水底的气泡往上移动一样逐渐往上冒。

public void bubbleSort(int[] arr) {
    int temp;//设置临时变量用于交换数组两个元素的数据
    boolean flag;//表示里层的for循环是否让数组元素发生交换
    for (int i = arr.length - 1; i > 0; i--) {
        flag = false;
        for (int j = 0; j < i; j++) {
            if (arr[j] > arr[j + 1]) {
                flag = true;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        if (!flag) {
            break;
        }
    }
}

二、选择排序

??????选择排序的基本思想：从数组中找出较小的元素，依次放在数组的前面，从而完成排序。

public void selectSort(int[] arr) {
    int minValue;//表示一定范围的最小值
    int temp = 0;//存储最小元素对应的元素下标
    for (int i = 0; i < arr.length - 1; i++) {
        minValue = arr[i];
        for (int j = i; j < arr.length; j++) {
            if (arr[j] < minValue) {
                temp = j;
                minValue = arr[j];
            }
        }
        arr[temp] = arr[i];
        arr[i] = minValue;
    }
}

三、插入排序

? ? ? ? 插入排序便是将数组分为两个部分，左边部分为有序表，右边部分为无序表。最先开始将第一个元素设置为有序表，接着从第二个元素开始，依次与前面有序表里面的元素进行比较大小并插入有序表当中。

public void insertionSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int value = arr[i];
        int index = i - 1;
        //将value与其他下标比i小的元素比较，再将value插入有序数组相应的位置
        while (index >= 0 && value < arr[index]) {
            arr[index + 1] = arr[index];
            index--;
        }
        arr[index + 1] = value;
    }
}

四、希尔排序

????????希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。基本思想：将数组按下标的一定增量分组（增量逐渐减少），并对每组使用插入排序算法进行排序。当增量减至为1时，整个数组被分为一组，排序后便终止算法。

public void shellSort(int[] arr) {
    int count;
    int index;
    // 增量 gap, 并逐步的缩小增量
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 从第 gap 个元素，逐个对其所在的组进行直接插入排序
        for (int j = gap; j < arr.length; j++) {
            index = j;//用于表示j的位置，并对对应的元素进行改动
            count = arr[index];//用于将原先的index位置的元素的数据储存起来
            while (index - gap >= 0 && count < arr[index - gap]) {
                arr[index] = arr[index - gap];
                index -= gap;
            }
            //当退出 while 后，就给 count 找到插入的位置
            arr[index] = count;
        }
    }
}

五、快速排序

????????快速排序是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

????????推荐观看此视频学习，单击此处可查看

public void quickSort(int[] arr, int left, int right) {

    //设置两个指针，L表示左指针，R表示右指针
    int L = left;
    int R = right;

    if (L > R) {
        return;
    }

    //设置代理数值，通过该数值比较大小进行排序
    int pioxy = arr[left];

    //设置一个锁，表示指针L是否能移动
    boolean Llock = true;
    //设置一个锁，表示指针L是否能移动
    boolean Rlock = true;


    while (R >= left && L <= right) {
        if (arr[R] < pioxy && Rlock) {
            arr[L] = arr[R];
            Rlock = false;
            Llock = true;
            L++;
        } else if (Rlock) {
            Llock = false;
            R--;
        }
        if (L == R) {
            arr[L] = pioxy;
            break;
        }
        if (arr[L] > pioxy && Llock) {
            arr[R] = arr[L];
            Llock = false;
            Rlock = true;
            R--;
        } else if (Llock) {
            Rlock = false;
            L++;
        }
    }

    //分别对代理数值proxy两端执行递归排序操作
    quickSort(arr, left, R - 1);
    quickSort(arr, L + 1, right);
}

六、归并排序

????????归并排序是利用归并的思想实现的排序方法，该算法采用经典的分治策略（分治法将问题分成一些小的问题然后递归求解），而治的阶段则得到的各答案“修补”在一起，即分而治之）。

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

public void mergeSeparate(int[] arr, int left, int right, int[] temp) {
    if (left < right) {
        int mid = (right + left) / 2;
        //分
        mergeSeparate(arr, left, mid, temp);
        mergeSeparate(arr, mid + 1, right, temp);
        //治
        merge(arr, left, mid, right, temp);
    }
}

/**
 * 合并
 */
public void merge(int[] arr, int left, int mid, int right, int[] temp) {
    int l = left;
    int r = mid + 1;
    int t = 0;

    while (l <= mid && r <= right) {
        if (arr[l] > arr[r]) {
            temp[t++] = arr[r++];
        } else {
            temp[t++] = arr[l++];
        }
    }

    while (l <= mid) {
        temp[t++] = arr[l++];
    }
    while (r <= right) {
        temp[t++] = arr[r++];
    }

    int arrIndex = left;
    t = 0;
    while (arrIndex <= right) {
        arr[arrIndex++] = temp[t++];
    }
}

七、基数排序

????????基数排序属于“分配式排序”，又称“桶子法“ （bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些”桶“中，达到排序的作用。

????????基本思想：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一个排序。这样从最低位排序一直到最高位排序完成以后，数列就变成个有序序列。

public void radixSort(int[] arr) {
    /*
    设置行数表示桶，列数表示被放入桶里的数值
    十个桶分别表示各个位数上的0~9数值，
    为了保险起见，每个桶的容量为arr的长度
     */
    int[][] bucket = new int[10][arr.length];

    //设置该数组用于记录储存到各个桶对应的数据的数量
    int[] bucketElementCounts = new int[10];

    //找出arr仲的最大元素是几位数
    int maxValue = arr[0];
    for (int i : arr) {
        if (maxValue < i) {
            maxValue = i;
        }
    }
    int maxLength = (maxValue + "").length();

    int digitOfElement;
    for (int i = 0, n = 1; i < maxLength ; i++, n*=10) {
        //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
        //开始存放数据
        for (int value : arr) {
            //找出相应位数上的数值
            digitOfElement = value / n % 10;

            //放入到对应的桶中
            //bucketElementCounts[digitOfElement]表示对应桶上所持有的数据数量
            bucket[digitOfElement][bucketElementCounts[digitOfElement]++] = value;
        }

        //将桶的数据依次取出，并重新存放到arr数组中
        int index = 0;
        for (int k = 0; k < bucket.length; k++) {
            //循环该桶即第 k 个桶(即第 k 个一维数组), 放入
            for (int j = 0; j < bucketElementCounts[k]; j++) {
                //取出元素放入到 arr
                arr[index++] = bucket[k][j];
            }
            //第 i+1 轮处理后，需要将每个 bucketElementCounts[k] = 0
            bucketElementCounts[k] = 0;
        }
    }
}