刷题过程中对常用的排序算法有遗忘，所以写一篇笔记。

一、冒泡排序

一种简单的排序算法，重复地走过要需要排序的序列，比较相邻两个元素的大小。依次将较大的元素放到数组的末尾，或是依次将较小的元素放到数组的首部，直到走访工作全部结束。

1、算法过程

比较相邻的元素，如果顺序错误就交换

对每一对相邻元素都做相同的工作，从第一对比到最后一对

已经放到最后的元素在下一轮就不需要比较了，因为它已经是当前轮次最大的元素

2、代码

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

二、选择排序

简单直观的排序算法，算法过程是在未排序的序列中，找到最大/最小的元素，将其放到队尾/队首。依次循环

1、算法描述

n个元素的排序经过n-1次排序得到最终结果，以找到最大元素为例

初始状态：全都是无序

排序时：数组后方元素是有序的，是一个递增序列。前半部分元素还是无序的状态

2、代码

public class SelectionSort {public int[] selectionSort(int[] nums){for(int i = 0; i < nums.length; i++){int minIndex = i;for(int j = i+1; j < nums.length; j++){if(nums[j] < nums[minIndex]){minIndex = j;}}int temp = nums[i];nums[i] = nums[minIndex];nums[minIndex] = temp;}return nums;}
}

三、插入排序

逐步构建有序序列，对于未排序的数据，在已排序的序列中扫描，找到对应的位置插入

1、算法描述

从第一个元素开始，默认已经排序

取出下一个元素，在已排序的元素中从后往前扫描

如果该元素大于新元素，就将元素移到下一个位置

找到新元素对应的位置，把该位置设置为新元素即可

2、代码

public static int[] insertSort(int[] nums){for(int i = 1; i < nums.length; i++){//当前i位置的元素为新元素//在已排序的序列中依次判断，大于新元素就后移，否则就插入int pre = i - 1;int cur = nums[i];//这里一定用cur保存nums[i]的值，因为nums[pre+1]的值可能会被修改while(pre >= 0 && nums[pre] > cur){nums[pre + 1] = nums[pre];pre--;}nums[pre+1] = cur;}return nums;}

四、希尔排序

希尔排序比一般O(n²)排序的速度要快很多，适用于中小规模的排序。

1、算法描述

将要排序的序列按照一定的间隔分组，先进行组内排序。

每轮完成之后缩小间隔，继续在组内排序

初始间隔大小gap = nums.length / 2，这是希尔推荐的

2、代码

代码部分还是值得思考的。

public static void shellSort(int[] nums){for(int gap = nums.length / 2; gap > 0; gap = gap / 2) {//大循环是进行一次各组内的排序for (int i = gap; i < nums.length; i++) {int j = i;int temp = nums[j];//开始各组内排序while (j - gap >= 0 && temp < nums[j - gap]) {nums[j] = nums[j - gap];j -= gap;}nums[j] = temp;}}}

五、归并排序

归并的核心思想就是分治。不断地将要排序的数组分为若干小分组。当小分组的大小为1，直接合并即可。

1、算法描述

把长度为n的序列分为长度为n/2的两个子序列

在子序列中进行归并

两个子序列归并后成为一个完整的有序序列

2、代码

public class MergeSort {public static void main(String[] args) {}public static void sort(int[] nums){int[] temp = new int[nums.length];sort(nums,0,nums.length - 1,temp);}public static void sort(int[] nums,int left,int right,int[] temp){if(left < right){int mid = (left + right) / 2;sort(nums,left,mid,temp);sort(nums,mid+1,right,temp);merge(nums,left,mid,right,temp);}}private static void merge(int[] nums, int left, int mid, int right, int[] temp) {int i = left;int j = mid + 1;int t = 0;if(i <= mid && j <= right){if(nums[i] <= nums[j]){temp[t++] = nums[i++];}else{temp[t++] = nums[j++];}}while(i <= mid){temp[t++] = nums[i++];}while(j <= right){temp[t++] = nums[j++];}t = 0;//将temp中的元素拷贝到原数组中while (left <= right){nums[left++] = temp[t++];}}
}

（）