选择排序
定义
一种最简单的排序算法是这样的：假定我们对一个数组进行排序那么，我们可以找到数组中最小的元素，然后与数组的第一个经行交换，如果第一个已经是最小的，那就和自己交换。然后在剩下的元素中找到最小的和第二个进行交换。以此类推，最终得到一个升序的数组。这种方式就叫做选择排序。
冒泡排序的升级版本。
代码实现
@Test
void select() {
int nums[] = new int[]{
9,8,7,6,5,4,3,2,1,0};
//经行选择排序
selectSort(nums);
for (int num : nums) {
System.out.println(num);
}
}
private void selectSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
//这种排序需要一个变量来记录当前最小值的位置
int min = i;
for (int j = i+1; j < nums.length; j++) {
if(nums[j] < nums[min]){
//当前元素比这个小，min指向这个小的
min = j;
}
//把最小的放在剩余元素的最前面
int tmp = nums[i];
nums[i] = nums[min];
nums [min] = tmp;
}
}
}
时间复杂度
这里只考虑最坏的情况。
对于一个长度为N的数组，第一次就需要遍历整个数组，这个时候就是N次，接下来就是N-1，N-2……直到比较完成。所以最多比较次数就是把这些加起来等于N（N-1）/ 2，与就是O（N^2）。
插入排序
定义
斗地主都玩过，摸起来的牌都会一张一张的插入到一个合适的位置，然后正副牌看起来就是井然有序。这种插入的方式就是插入排序。
就比如这个，3比9小，于是插入到9的左边，然后发现，3比7小，又插入到7的左边，直到左边没有比这数小的，总的来说就是一趟过后，左边的都是有序的。
代码实现
@Test
void select() {
int nums[] = new int[]{
9,8,7,6,5,4,3,2,1,0};
//经行选择排序
insertSort(nums);
for (int num : nums) {
System.out.println(num);
}
}
private void insertSort(int[] nums){
//外层循环
for (int i = 1; i < nums.length; i++) {
for (int j = i;j > 0;j--) {
//当前比前面的小，插入
if (nums[j] < nums[j-1]){
//交换
int tmp = nums[j];
nums[j] = nums[j-1];
nums [j-1] = tmp;
} else {
break; //没有就后移再次进入循环比较
}
}
}
}
时间复杂度为：N2/4，就是O(N2)，比选择排序好那么一点。
希尔排序
上面的排序每次都是相邻的元素进行比较，导致每次都需要大量的移动，而希尔排序的特点就是，每次使数组变得大致上有序，然后变得有序。每次使一个组有序，总体上就是大致有序，然后缩小这个组直到最后有序。
比如这个，1，7一组，6，5一组，然后这每一个组排个序，整个数组就整体上变得有序很多，然后缩小这个分组，直到最后有序。
代码实现
@Test
void select() {
int nums[] = new int[]{
9,8,7,6,5,4,3,2,1,0};
//经行选择排序
insertSort(nums);
for (int num : nums) {
System.out.println(num);
}
}
private void shellSort(int[] nums){
//选择一个增量
int n = nums.length/2;
//增量不等于1排序，数组只能大致有序，所以会逐步缩小到1
while (n > 0) {
for (int i = n; i < nums.length; i++) {
for (int j = i; j >= n; j -= n) {
//比较这两个大小
if (nums[j] < nums[j-n]){
//交换
int tmp = nums[j];
nums[j] = nums[j-n];
nums [j-n] = tmp;
}
}
}
//缩小增量
n = n / 2;
}
}
对于这种排序，怎么选择增量就是一个最复杂的问题。
归并排序
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：
- 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）；
- 自下而上的迭代；
用一张图演示归并的过程：
分割归并：
递归
既然是一个分割合并的过程，必然需要两个指针来对着两边进行归并。
public static void main(String[] args) {
//归并排序，定义一个数组
int arr[] = new int[]{
1,5,3,8,7,4,9,2};
//需要递归的方法
sort(arr,0,arr.length-1);
for (int i : arr) {
System.out.print(i + " ");
}
}
//方法含义，根据数组进行排序
public static void sort(int arr[], int left, int right){
//递归结束条件，左指针大于或者等于右指针
if (left >= right) return;
//二分的中间值
int mid = left + (right - left) / 2;
//否则进行分割
sort(arr,left, mid);
sort(arr,mid+1,right);
//最后才是排序
merge(arr,left,mid, right);
}
private static void merge(int[] arr, int left, int mid, int right) {
//先复制这个数组，这样为了保证原来的数组不被打乱
int tmp[] = new int[right-left+1];
int k=0;
int l = left;
int r = mid+1;
//左右指针
while (l <= mid && r <= right){
if(arr[l] < arr[r]){
//左边数组小于右边，把左边的放在临时数组中
tmp[k] = arr[l];
l++;
} else {
tmp[k] = arr[r];
r++;
}
k++;
}
//然后把上面没排完的全部放在这个新数组里面
while (l <= mid) tmp[k++] = arr[l++];
while (r <= right) tmp[k++] = arr[r++];
//最后把数组赋值给原来的数组
for (int i = 0; i < tmp.length; i++) {
arr[left+i] = tmp[i];
}
}
其实这是有一点像树的后续遍历，先找到叶子节点（这里先分割成最小单位）。然后在做一个排序处理。
快速排序
快排的性能在所有排序算法里面是最好的，数据规模越大快速排序的性能越优。快排在极端情况下会退化成O(n^2)的算法，因此假如在提前得知处理数据可能会出现极端情况的前提下，可以选择使用较为稳定的归并排序。
一张图解释快排：
仔细看，发现这个过程跟归并排序貌似是一个相反的过程，归并是先分割成最小两个单位，在逐步向上。而快排是先排序成两个分割好的再递进下去。
总结规律：
- 选择待排序（A）中的任意一个元素pivot，该元素作为基准
- 将小于基准的元素移到左边，大于基准的元素移到右边（分区操作）
- A被pivot分为两部分，继续对剩下的两部分做同样的处理
- 直到所有子集元素不再需要进行上述步骤
public static void main(String[] args) {
//归并排序，定义一个数组
int arr[] = new int[]{
1,5,3,8,7,4,9,2};
//需要递归的方法
sort(arr,0,arr.length-1);
for (int i : arr) {
System.out.print(i + " ");
}
}
//方法含义，根据数组进行排序
public static void sort(int arr[], int left, int right){
int index = 0;
//递归结束条件，左指针大于或者等于右指针
if (left < right) {
//将第一趟排序后的地址拿到
index = merge(arr, left, right);
//然后根据这个下标分割这个数组
sort(arr, left, index - 1);
sort(arr, index + 1, right);
}
}
private static int merge(int[] arr, int left, int right) {
//主要的逻辑代码，双指针左右前进
int tmp = arr[left]; //保存中轴
while (left < right) {
while (left < right && arr[right] >= tmp) {
//比中轴小，则需要交换到低端，否则直接这个下标后移
right--;
}
//进行交换
arr[left] = arr[right];
while (left < right && arr[left] <= tmp) {
//比中轴大就交换到高端,否则就这个下标前移
left++;
}
arr[right] = arr[left];
}
//最后更新这个中轴
arr[left] = tmp;
return left;
}
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：
同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射（层序遍历的一种结构）到数组中就是下面这个样子：
这个数组中蕴含的一个数学公式：
大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]
小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]
至此就可以开始着手了解这个堆排序。
基本思想：将待排序构造成一个大顶堆（或者小堆）结构，此时，整个序列的最大值（最小值）一定是堆顶的这个节点，或者说是这个数组的第一个元素。然后把这个值和最后的一个节点交换，这个时候最大或者最小值不久直接搞到最后了嘛，然后把除了最后一个节点的剩下节点再构造成一个堆结构，如此反复，一个有序的数组就得到了。
public static void main(String[] args) {
int[] nums = {
16,7,3,20,17,8};
headSort(nums);
for (int num : nums) {
System.out.print(num + " ");
}
}
/**
* 堆排序
*/
public static void headSort(int[] list) {
//构造初始堆，i一定是倒数第二层的一个节点，并且这个节点的右边的节点一定没有孩子节点。
for (int i = (list.length) / 2 - 1; i >= 0; i--) {
headAdjust(list, list.length, i);
}
//排序，将最大的节点放在堆尾，然后从根节点重新调整
for (int i = list.length - 1; i >= 1; i--) {
int temp = list[0];
list[0] = list[i];
list[i] = temp;
headAdjust(list, i, 0);
}
}
/**
* 调整这个节点与左右孩子的关系
* @param list
* @param len
* @param i
*/
private static void headAdjust(int[] list, int len, int i) {
//tem 是父节点，index是左孩子，k 父节点的位置
int k = i, temp = list[i], index = 2 * k + 1;
while (index < len) {
//index < len 表示有左孩子
if (index + 1 < len) {
//找到孩子节点中较大值的下标
if (list[index] < list[index + 1]) {
index = index + 1;
}
}
//这个较大的孩子节点比父节点大，交换。
if (list[index] > temp) {
list[k] = list[index];
k = index;
index = 2 * k + 1;
} else {
break;
}
}
//更新这个孩子节点的值，如果上面没有发生交换，就保持父节点不动
list[k] = temp;
}
计数排序
现在假设一种场景，高考一般考生在几百万，有这么多的数据，但是这个数据值的分布呢，0到750这个数据，也就是不论哪个人，分数一定是在这个范围。那么如何知道一个人的排名呢？这个时候就可以统计每个分数的人数，而不是非要把几百万个数据进行一个排序！
核心思想：统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引
public static void main(String[] args) {
//归并排序，定义一个数组
int arr[] = new int[]{
1,5,3,8,7,4,0,0,9,2,4,5,1,7,8,9,7,4,4,5,1,2,3,2,6,5,6,9,8,7};
//需要递归的方法
int[] sort = sort(arr);
for (int i : sort) {
System.out.print(i + " ");
}
System.out.println();
for (int i : arr) {
System.out.print(i+" ");
}
}
//方法含义，根据数组进行排序
public static int[] sort(int arr[]){
//既然是计数，我们需要一个数组来记录每个数据出现的次数
int count[] = new int[10];
//然后遍历这个数组，每个数据当作下标使用
for (int i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
int index = 0; //这个数组的下标，i表示这个数值
//根据这个计数器得到数据
for (int i = 0; i < count.length; i++) {
int tmp = count[i]; //得到这个值的次数
while (tmp > 0){
arr[index++] = i;
tmp--;
}
}
return count;
}
前面的排序都是比较大小人后交换位置，这种排序算得上另辟蹊径，直接统计数量然后重新赋值整个数组。但是这种排序大部分只针对这种数字。
基数排序
计数排序是一种很容易理解的算法，适用的领域也比较小。这里给出的基数排序也用到了桶这个概念，也就是统计个数。一张动图如下：假如我们现在数组的元素是：1221, 15, 20, 3681, 277, 5420, 71, 1522, 4793。
在上面的例子中，我们先对个位进行count排序，然后对十位进行count排序，然后是百位和千位。最后生成最终的排序结果。
public static void main(String[] args) {
int[] arr = new int[] {
23, 6, 9, 287, 56, 1, 789, 34, 65, 653 };
System.out.println(Arrays.toString(arr));
radixSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void radixSort(int[] arr) {
// 存数组中最大的数字,为了知道循环几次
int max = Integer.MIN_VALUE;// (整数中的最小数)
// 遍历数组，找出最大值
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
// 计算最大数是几位数,,此方法计较绝妙
int maxLength = (max + "").length();
// 用于临时存储数据的数组
int[][] temp = new int[10][arr.length];
// 用于存储桶内的元素位置
int[] counts = new int[arr.length];
// 第一轮个位数较易得到余数，第二轮就得先除以十再去取余，之后百位除以一百
// 可以看出，还有一个变量随循环次数变化，为了取余
// 循环的次数
for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
// 每一轮取余
for (int j = 0; j < arr.length; j++) {
// 计算余数
int ys = (arr[j] / n) % 10;
// 把数据放在指定数组中，有两个信息，放在第几个桶+数据应该放在第几位
temp[ys][counts[ys]] = arr[j];
// 记录数量
counts[ys]++;
}
// 记录取的数字应该放到位置
int index = 0;
// 每一轮循环之后把数字取出来
for (int k = 0; k < counts.length; k++) {
// 记录数量的数组中当前余数记录不为零
if (counts[k] != 0) {
for (int l = 0; l < counts[k]; l++) {
// 取出元素
arr[index] = temp[k][l];
index++;
}
// 取出后把数量置为零
counts[k] = 0;
}
}
}
}
桶排序
一句话总结：划分多个范围相同的区间，每个子区间自排序，最后合并。
桶排序是计数排序的扩展版本，计数排序可以看成每个桶只存储相同元素，而桶排序每个桶存储一定范围的元素，通过映射函数，将待排序数组中的元素映射到各个对应的桶中，对每个桶中的元素进行排序，最后将非空桶中的元素逐个放入原序列中。
public static void bucketSort(int[] arr){
// 计算最大值与最小值
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
for(int i = 0; i < arr.length; i++){
max = Math.max(max, arr[i]);
min = Math.min(min, arr[i]);
}
// 计算桶的数量
int bucketNum = (max - min) / arr.length + 1;
ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);
for(int i = 0; i < bucketNum; i++){
bucketArr.add(new ArrayList<Integer>());
}
// 将每个元素放入桶
for(int i = 0; i < arr.length; i++){
int num = (arr[i] - min) / (arr.length);
bucketArr.get(num).add(arr[i]);
}
// 对每个桶进行排序
for(int i = 0; i < bucketArr.size(); i++){
Collections.sort(bucketArr.get(i));
}
// 将桶中的元素赋值到原序列
int index = 0;
for(int i = 0; i < bucketArr.size(); i++){
for(int j = 0; j < bucketArr.get(i).size(); j++){
arr[index++] = bucketArr.get(i).get(j);
}
}
}
转载：https://blog.csdn.net/weixin_55086330/article/details/115409165