目录
一、【前言】排序的稳定性：
二、七大排序总览
三、插入排序
1.1直接插入排序
1.2直接插入排序优化版——折半插入排序：
2.希尔排序
四、选择排序
1.1选择排序
1.2进阶版选择排序
2.堆排序
五、交换排序
1.冒泡排序
六、归并排序
1.1归并排序(递归）
1.2归并排序非递归写法
一、【前言】排序的稳定性：
稳定性：两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。
如下面这个例子，未排序前，5(a)是在5(b)前面的，因为5=5，所以如果排序后5(a)仍然是在5(b)前面，保证了相等的数排完序之后的相对位置仍然未变，我们就说这种排序是稳定的
那么，为什么有时候需要保证稳定性呢，来看一个典型的现实例子：
某商城订单默认是按时间顺序排列，现需要按照订单金额大小从小到大排序，而对于金额大小一样的订单，排序后保证其时间顺序不变，这就一定是需要具有稳定性的算法来排序了
二、七大排序总览
稳定性：两个相等的数据，如果经过排序后，排序算法能保证其相对位置不发生变化，则我们称该算法是具备稳定性的排序算法。
如下面这个例子，未排序前，5(a)是在5(b)前面的，因为5=5，所以如果排序后5(a)仍然是在5(b)前面，保证了相等的数排完序之后的相对位置仍然未变，我们就说这种排序是稳定的
那么，为什么有时候需要保证稳定性呢，来看一个典型的现实例子：
某商城订单默认是按时间顺序排列，现需要按照订单金额大小从小到大排序，而对于金额大小一样的订单，排序后保证其时间顺序不变，这就一定是需要具有稳定性的算法来排序了
三、插入排序
1.1直接插入排序
算法思想：
将数据分为已排序区间【0，i）和待排序区间【i，length - 1】，遍历待排序区间，将一个一个元素插入到已排序区间的合适位置，直至待排序区间为空
算法思想：
将数据分为已排序区间【0，i）和待排序区间【i，length - 1】，遍历待排序区间，将一个一个元素插入到已排序区间的合适位置，直至待排序区间为空
代码实现：
public static void insert(int[] arr) {
int n = arr.length;
// i是待排序去插入已排序区间的元素
for (int i = 1; i < n; i++) {
// 从i开始向前不断交换，直至i大于等于前一个元素
for (int j = i; j > 0; j--) {
// 这里的等号一定要取到，相等了也不交换，保持稳定性
if (arr[j] >= arr[j - 1]) {
break;
} else {
swap(arr, j, j - 1);
}
}
}
}
private static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
1.2直接插入排序优化版——折半插入排序：
所谓优化版，就是在找插入位置时，不似刚才的逆序遍历找位置，而是用二分法，查找待插入元素的插入位置
public static void midInsert(int[] arr){
int n = arr.length;
for (int i = 1; i < n; i++) {
int left = 0;
int right = i;
int cur = arr[i];
while(left < right){
int mid = left + (right - left) / 2;
if(arr[mid] > cur){
right = mid;
}else{
left = mid + 1 ;
}
}
// 此时，left位置就是待插入位置，需要将【left，i）之间的元素后移一位
for (int j = i; j > left; j--) {
arr[j] = arr[j - 1];
}
arr[left] = cur;
}
}
2.希尔排序
前面的插入排序我们可以看出，当一组数据近乎有序时，插入排序的时间复杂度近乎为O（N），所以当数组近乎有序时，插入排序效率还是很高的，希尔排序正是借助了这一点。
【注】因为希尔排序在分组交换中会改变数组中元素相对位置，故而希尔排序无稳定性
整体思路：
数组长度为N,先将数组分为N/2组，保证各小组里的数据是有序的（插入排序），每排序一次就将组数/2，并保证组内元素有序，直至最后组数为1；
当组数为1时，此时数组是近乎有序的，故而最后再使用一次插入排序，至此，数组排序结束
代码实现：
public static void shellSort(int[] arr){
int n = arr.length;
int gap = n >> 1;
// 先分组排序
while(gap >= 1){
shell(arr,gap);
gap = gap >> 1;
}
// 最后插入排序
// insert(arr);
}
// 数组中相隔gap个单位的元素为一组，保证组内元素有序
private static void shell(int[] arr, int gap) {
for (int i = gap; i < arr.length; i++) {
int val = arr[gap];
for (int j = i; j - gap >= 0; j -= gap) {
if(arr[j] >= arr[j - gap]){
break;
}else{
swap(arr,j,j - gap);
}
}
}
}
四、选择排序
1.1选择排序
选择排序，顾名思义，就是一个个把合适位置的元素挑起来放在其合适的位置。那么合适的元素怎么选呢
两种方法，一种是找最大，一种是找最小；
以找最大元素为例，第一次遍历数组，找到最大元素，该元素应当放在最后一个索引位置处，然后找次大的元素，放在倒数第二处位置，……直至全部选择放置结束
代码实现：
public static void selectMax(int[] arr){
int n = arr.length;
// 只需n-1趟
for (int i = n - 1; i > 0; i--) {
int max = Integer.MIN_VALUE;
int index = 0;
// 遍历一遍，找最大
for (int j = 0; j <= i; j++) {
if(arr[j] >= max){
index = j;
max = arr[j];
}
}
// 交换最大值和正确的位置元素
swap(arr,index,i);
}
}
1.2进阶版选择排序
每次遍历找最大或最小，需要遍历n - 1次，那么我们思考，可不可以一次遍历同时找到最大和最小，并将这两个元素各自放在最前和最后，这样，效率至少提高了一倍
【唯一需要注意的是，如若先交换较小元素，在交换较大元素时，需注意看是否大元素恰好在上一步交换时已经被改变了索引】
每次遍历找最大或最小，需要遍历n - 1次，那么我们思考，可不可以一次遍历同时找到最大和最小，并将这两个元素各自放在最前和最后，这样，效率至少提高了一倍
【唯一需要注意的是，如若先交换较小元素，在交换较大元素时，需注意看是否大元素恰好在上一步交换时已经被改变了索引】
代码实现：
public static void selectMaxMin(int[] arr){
int n = arr.length;
int left = 0;
int right = arr.length - 1;
// 当left和right中间只有一个元素是，数组已经有序
while(left < right){
int min = left;
int max = left;
// 遍历中间区间，找最大和最小
for (int i = left + 1; i <= right; i++) {
if(arr[min] > arr[i]){
min = i;
}
if(arr[max] < arr[i]){
max = i;
}
}
// 先把最小的交换
swap(arr,min,left);
// 然后交换最大，此时需注意有可能最大恰好在上一步被交换了
if(max == left){
max = min;
}
swap(arr,max,right);
// 最后记得让左右区间各扩大一个
left ++;
right --;
}
}
private void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
2.堆排序
堆排序也是选择排序的一种，它也是在找最大或最小元素实现排序，在堆的笔记中我们已经详细介绍过，这里不再赘述。堆排序也不具有稳定性
代码附上：
public static void heapSort(int[] arr) {
// 先将数组arr堆化,从第一个非叶子节点开始下沉操作
for (int i = (arr.length - 1 - 1) / 2; i >= 0; i--) {
siftDown(arr, i, arr.length);
}
// 此时已是最大堆
for (int i = arr.length - 1; i > 0; i--) {
// 将最大的元素移至最后一个位置，次大的元素移至倒数第二个位置……
swap(arr, 0, i);
// 每次换好一个位置后，将其余元素下沉重新堆化
siftDown(arr, 0, i);
}
}
// 交换
private static void swap(int[] arr, int index1, int index2) {
int temp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = temp;
}
public static void siftDown(int[] arr, int i, int length) {
// 当还有子节点时
while ((2 * i + 1) < length) {
int j = 2 * i + 1;
if (j + 1 < length && arr[j + 1] > arr[j]) {
j = j + 1;
}
if (arr[i] < arr[j]) {
swap(arr, i, j);
i = j;
} else {
break;
}
}
}
五、交换排序
1.冒泡排序
冒泡排序思路这里简单说下，冒泡就是一趟趟将最大的元素交换至最后的位置，将次大的元素交换至倒数第二位，直至走完n趟
仅注意一点:
冒泡的优化：当进行到某趟时，发现无可交换的元素，说明这时整个数据已经有序，无需继续后面的趟数，可以提前break
冒泡排序思路这里简单说下，冒泡就是一趟趟将最大的元素交换至最后的位置，将次大的元素交换至倒数第二位，直至走完n趟
仅注意一点:
冒泡的优化：当进行到某趟时，发现无可交换的元素，说明这时整个数据已经有序，无需继续后面的趟数，可以提前break
代码实现：
public static void bubbleSort(int[] arr){
int n = arr.length;
// i控制趟数
for (int i = 0; i < n; i++) {
boolean a = true;
for (int j = 0; j < n - i - 1; j++) {
// 不取等保证稳定性
if(arr[j + 1] < arr[j]){
swap(arr,j + 1,j);
a = false;
}
}
// 如果走至某趟已经无交换，可提前结束循环
if(a == true){
break;
}
}
}
六、归并排序
1.1归并排序(递归）
归并：先分再合
整体思路：
先将数组逐次拆分，直至其拆分为一个个元素；然后依据拆分步骤倒着往回合并
【注】这种方法是具有稳定性的
两个地方可以优化：
没必要一直拆分到一个元素，当区间已经较小时，可以选择使用插入排序来完成排序，一般，当拆分区间小于15个元素时，我们就可以采用插入排序在进行区间两两合并时，可以先判断一下两个区间里的元素是否需要重新排序；我们知道，当左区间最后一个元素小于右区间第一个元素时，说明整个左区间都比右区间小，说明这两个区间合并时无需重新排序
归并：先分再合
整体思路：
先将数组逐次拆分，直至其拆分为一个个元素；然后依据拆分步骤倒着往回合并
【注】这种方法是具有稳定性的
两个地方可以优化：
没必要一直拆分到一个元素，当区间已经较小时，可以选择使用插入排序来完成排序，一般，当拆分区间小于15个元素时，我们就可以采用插入排序在进行区间两两合并时，可以先判断一下两个区间里的元素是否需要重新排序；我们知道，当左区间最后一个元素小于右区间第一个元素时，说明整个左区间都比右区间小，说明这两个区间合并时无需重新排序
代码实现：
public static void mergeSort(int[] arr){
merge(arr,0,arr.length - 1);
}
// 将l到r区间内的元素进行归并排序
public static void merge(int[]arr,int l,int r){
// 一般如果区间元素已经小于15个，就可以不再归并，直接插入排序即可
if(r - l <= 15){
insertHelpMerge(arr,l,r);
return;
}
int mid = l + ((r - l) >> 1);
// 递归左
merge(arr,l,mid);
// 递归右
merge(arr,mid + 1,r);
// 当左右合起来仍无序时，才需要左右合并
if(arr[mid] > arr[mid + 1]){
mergeHelp(arr,l,mid,r);
}
}
// 合并以mid为界的两个子数组
private static void mergeHelp(int[] arr, int l, int mid, int r) {
// 辅助数组暂存l到r间的元素
int[] res = new int[r - l + 1];
for (int i = 0; i < res.length; i++) {
res[i] = arr[l + i];
}
int left = l;
int right = mid + 1;
// 按照排序结果修改arr区间元素
for (int index = l; index <= r; index++) {
// 如果左边已全部入序，剩余的直接为右边的
if(left > mid){
arr[index] = res[right - l];
right ++;
}else if(right > r){
arr[index] = res[left - l];
left ++;
}else if(res[left - l] <= res[right - l]){
arr[index] = res[left - l];
left ++;
}else{
arr[index] = res[right - l];
right ++;
}
}
}
//l到r区间内的元素进行插入排序
private static void insertHelpMerge(int[] arr, int l, int r) {
for (int i = l + 1; i <= r; i++) {
for (int j = i; j > l; j--) {
if(arr[j] >= arr[j - 1]){
break;
}else{
swap(arr,j,j - 1);
}
}
}
}
1.2归并排序非递归写法
public static void mergeSortNoRecursion(int[] arr){
// 第一层for循环指示合并元素的个数
for (int i = 1; i <= arr.length; i += i) {
// j + i 就是右区间开始的索引
for (int j = 0; j + i < arr.length; j += i + i) {
mergeHelp(arr,j,j + i - 1,Math.min(arr.length - 1,j + i + i - 1));
}
}
}
// 合并以mid为界的两个子数组
private static void mergeHelp(int[] arr, int l, int mid, int r) {
// 辅助数组暂存l到r间的元素
int[] res = new int[r - l + 1];
for (int i = 0; i < res.length; i++) {
res[i] = arr[l + i];
}
int left = l;
int right = mid + 1;
// 按照排序结果修改arr区间元素
for (int index = l; index <= r; index++) {
// 如果左边已全部入序，剩余的直接为右边的
if(left > mid){
arr[index] = res[right - l];
right ++;
}else if(right > r){
arr[index] = res[left - l];
left ++;
}else if(res[left - l] <= res[right - l]){
arr[index] = res[left - l];
left ++;
}else{
arr[index] = res[right - l];
right ++;
}
}
}
七大排序这一篇归总了六种，还剩交换排序的一种：快排，快排易考又内容较多，下一篇再详细总结！
