荐 详解8大排序算法——Java实现

一、分类

二、实现

2.1 冒泡排序

2.1.1 介绍

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始）,依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。

2.2.2 优化

因为排序的过程中，各元素不断接近自己的位置，如果一趟比较下来没有进行过交换，就说明序列有序，因此要在排序过程中设置一个标志flag 判断元素是否进行过交换。从而减少不必要的比较。(这里说的优化，可以在冒泡排
序写好后，在进行)

2.2.3 代码实现

package com.czn.sort;
 
import java.util.Arrays;
 
public class Sort1BubbleSort {
 
  public static void main(String[] args) {
   int[] arr = { 9, 8, 7, 6, 5, 5, 4, 3, 2, 1 };
   bubbleSort(arr);
   System.out.println(Arrays.toString(arr));
 
  }
 
  public static void bubbleSort(int[] arr) {
   // 打标记进行优化，如果arr本来就是有序的，那么在进行一次比较之后flag没有改变
   // 通过判断flag的状态可以选择因为arr有序而直接退出或者arr无序继续进行比较
   boolean flag = false;
   // 控制外部循环的次数，每循环一次就确定一个有序数
   for (int i = 0; i < arr.length - 1; i++) {
     // 控制每趟循环内部的比较次数
     for (int j = 0; j < arr.length - 1 - i; j++) {
       if (arr[j] > arr[j + 1]) {
        flag = true;
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
       }
     }
     // 通过判断flag的状态决定退出还是继续
     if (!flag) {
       break;
     } else {
       flag = false;
     }
   }
  }
}
 

2.2简单选择排序

2.2.1 基本介绍

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

2.2.2 基本思想

选择排序（select sorting）也是一种简单的排序方法。它的基本思想是：第一次从arr[0] ~ arr[n-1]中选取最小值，与arr[0]交换，第二次从arr[1] ~ arr[n-1]中选取最小值，与arr[1]交换，第三次从arr[2]~arr[n-1]中选取最小值，与arr[2]交换，…，第i 次从arr[i-1]~arr[n-1]中选取最小值，与arr[i-1]交换，…, 第n-1 次从arr[n-2]~arr[n-1]中选取最小值，与arr[n-2]交换，总共通过n-1 次，得到一个按排序码从小到大排列的有序序列。

2.2.3 思路分析图

2.2.4 代码实现

package com.czn.sort;

import java.util.Arrays;

public class Sort2SelectSort {

	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, };
		selectSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void selectSort(int[] arr) {
		// 控制外部循环的次数，每循环一次就确定一个有序数
		for (int i = 0; i < arr.length - 1; i++) {
			// 假设最小值是arr[i]
			int min = arr[i];
			// 最小值的索引
			int minIndex = i;
			// 遍历i之后的每个索引，找到arr的最小值及其索引
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < min) {
					min = arr[j];
					minIndex = j;
				}
			}
			// 交换，实现从前向后依次有序
			arr[minIndex] = arr[i];
			arr[i] = min;
		}
	}
}

2.3 直接插入排序

2.3.1 基本介绍

插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

2.3.2 基本思想

插入排序（Insertion Sorting）的基本思想是：把n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

2.3.3 思路分析图

2.3.4 代码实现

package com.czn.sort;

import java.util.Arrays;

public class Sort3InsertionSort {

	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
		insertionSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void insertionSort(int[] arr) {
		// 控制外部循环的次数，假设arr[0]已是有序，所以从i=1开始
		for (int i = 1; i < arr.length; i++) {
			// 记录当前值
			int temp = arr[i];
			// 当前索引的前一个索引
			int preIndex = i - 1;
			// preIndex>=0的目的是保证不会发生数组越界异常
			// while循环的目的是为当前值找到一个适合自己插入的位置
			while (preIndex >= 0 && temp < arr[preIndex]) {
				// 向后挪一个位置
				arr[preIndex + 1] = arr[preIndex];
				// preIndex索引前移一个位置，以便继续判断插入的位置是否还要在前面一点
				preIndex--;
			}
			// 退出while循环，说明找到了属于自己的位置
			arr[preIndex + 1] = temp;
		}
	}
}

2.4 希尔排序

2.4.1 简单排序存在的问题

我们看简单的插入排序可能存在的问题.
数组arr = {2,3,4,5,6,1} 这时需要插入的数1(最小), 这样的过程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
结论: 当需要插入的数是较小的数时，后移的次数明显增多，对效率有影响。

2.4.2 基本介绍

希尔排序是希尔（Donald Shell）于1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

2.4.3基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1 时，整个文件恰被分成一组，算法便终止

2.4.4 示意图

2.4.5 代码实现

package com.czn.sort;

import java.util.Arrays;

public class Sort3InsertionSort {

	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
		insertionSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void insertionSort(int[] arr) {
		// 控制外部循环的次数，假设arr[0]已是有序，所以从i=1开始
		for (int i = 1; i < arr.length; i++) {
			// 记录当前值
			int temp = arr[i];
			// 当前索引的前一个索引
			int preIndex = i - 1;
			// preIndex>=0的目的是保证不会发生数组越界异常
			// while循环的目的是为当前值找到一个适合自己插入的位置
			while (preIndex >= 0 && temp < arr[preIndex]) {
				// 向后挪一个位置
				arr[preIndex + 1] = arr[preIndex];
				// preIndex索引前移一个位置，以便继续判断插入的位置是否还要在前面一点
				preIndex--;
			}
			// 退出while循环，说明找到了属于自己的位置
			arr[preIndex + 1] = temp;
		}
	}
}

2.5 快速排序

2.5.1 基本介绍:

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

2.5.2 基本思想:

将待排序数组分为两部分，比如分为左半部分和右半部分，在左半部分找比基准值（比如中间索引mid对应的值）大的数，在右半部分找比基准值小的数，再把找到的两个值进行交换，直到两个索引的标记重合，退出循环，得到一个数组具有以下特征：

• 基准值的左子数组都比基准值小
• 基准值的右子数组都比基准值大

再分别对左子数组和右子数组进行递归

2.5.3 代码实现:

package com.czn.sort;

import java.util.Arrays;

public class Sort5QuickSort {

	public static void main(String[] args) {
		int[] arr = { -9, 78, 0, 23, -567, 70 };
		quickSort(arr, 0, 5);
		System.out.println(Arrays.toString(arr));
	}

	public static void quickSort(int[] arr, int left, int right) {
		// start是数组的左索引
		int start = left;
		// end是数组的右索引
		int end = right;
		// mid是中间索引
		int mid = (left + right) / 2;
		while (start < end) {
			// 从[start,mid]之间找比mid大的数的索引
			while (arr[start] < arr[mid]) {
				start++;
			}
			// 从[mid,end]之间找比mid小的数的索引
			while (arr[end] > arr[mid]) {
				end--;
			}
			// 退出while循环的条件：start和end重合
			if (start == end) {
				break;
			}
			// 如果不退出，那么就进行交换
			int temp = arr[start];
			arr[start] = arr[end];
			arr[end] = temp;

			// 当数组是[0,1,2,0,1,2]的情况，arr[start]=2和arr[end]=2
			// 进行交换的话还是[0,1,2,0,1,2]，所以下面的代码是防止进入死循环
			if (arr[start] == arr[mid]) {
				end--;
			}
			if (arr[end] == arr[mid]) {
				start++;
			}
		}
		// 退出while循环说明start和end重合了
		// 以重合点分为左半部分和右半部分，准备进行递归
		start++;
		end--;
		// 向右半部分递归
		if (start < right) {
			quickSort(arr, start, right);
		}
		// 向左半部分递归
		if (end > left) {
			quickSort(arr, left, end);
		}
	}
}

2.6 归并排序

2.6.1 介绍:

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

2.6.2 示意图:

• 基本思想示意图
  

• 合并相邻有序子序列示意图：
  

2.6.3 代码实现:

package com.czn.sort;

import java.util.Arrays;

public class Sort6MergeSort {

	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		int[] temp = new int[arr.length];
		mergeSort(arr, 0, 8, temp);
		System.out.println(Arrays.toString(temp));
	}

	public static void mergeSort(int[] arr, int left, int right, int[] temp) {
		// 只要left<right的情况下，就继续分下去
		if (left < right) {
			// 中间的索引
			int mid = (left + right) / 2;
			// 向左半部分分
			mergeSort(arr, left, mid, temp);
			// 向右半部分分
			mergeSort(arr, mid + 1, right, temp);
			// 对左右俩部分进行合并，使得合并后是有序的
			merge(arr, left, mid, right, temp);
		}
	}

	// 合并的实现方法
	private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		// 左半部分从left开始，用i做标记
		int i = left;
		// 右半部分从mid+1开始，用j做标记
		int j = mid + 1;
		// 临时数组的索引值
		int index = 0;
		// 将左半部分和右半部分的元素按照由小到大的顺序添加到temp数组
		// 直到有一边的数据被添加完
		while (i <= mid && j <= right) {
			// 将两部分小的元素添加到temp数组
			if (arr[i] < arr[j]) {
				temp[index++] = arr[i++];
			} else {
				temp[index++] = arr[j++];
			}
		}
		// 上面只是一边的元素被添加完，还有另一边的元素没有添加完
		while (i <= mid) {
			temp[index++] = arr[i++];
		}
		// 与上面同理
		while (j <= right) {
			temp[index++] = arr[j++];
		}
		// 给left边界做标记
		int start = left;
		// temp索引值置为0
		index = 0;
		// 将temp中的left到right的值复制到arr数组中
		while (start <= right) {
			arr[start++] = temp[index++];
		}
	}

}

2.7 基数排序

2.7.1 基本介绍：

1. 基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用
2. 基数排序法是属于稳定性的排序，基数排序法的是效率高的稳定性排序法
3. 基数排序(Radix Sort)是桶排序的扩展
4. 基数排序是1887 年赫尔曼·何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

2.7.2 基本思想：

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

2.7.3 代码实现：

package com.czn.sort;

import java.util.Arrays;

public class Sort7RadixSort {
	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		radixSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void radixSort(int[] arr) {

		// 假定数组的第一个数是最大值
		int max = arr[0];
		// 遍历数组，找到最大值
		for (int n = 1; n < arr.length; n++) {
			if (max < arr[n]) {
				max = arr[n];
			}
		}
		// 获取数组中最大数的长度
		int maxLength = (max + "").length();
		// System.out.println("maxLength =" + maxLength);

		// 最大数有几位就需要遍历多少次
		for (int m = 0; m < maxLength; m++) {
			// 创建一个二维数组，行表示桶，列表示桶的大小
			int[][] bucket = new int[10][arr.length];

			// 创建一个一维数组，用来代表每个桶有效数据的个数
			int[] bucketElementsCounts = new int[10];

			// 对原始数组进行处理
			for (int i = 0; i < arr.length; i++) {
				// 获取个位数的值，放到对应的桶中去
				int digit = (int) (arr[i] / Math.pow(10, m)) % 10;
				bucket[digit][bucketElementsCounts[digit]] = arr[i];
				bucketElementsCounts[digit]++;
			}

			int index = 0;
			// 对每个桶进行遍历
			for (int j = 0; j < bucket.length; j++) {
				// 说明桶里面有有效数据
				if (bucketElementsCounts[j] != 0) {
					// 对桶里面的数据进行遍历
					for (int k = 0; k < bucketElementsCounts[j]; k++) {
						arr[index] = bucket[j][k];
						index++;
					}
				}
				// 注意最后要把bucketElementsCounts数组的记录清空，不然里面的值会影响下一轮循环
				bucketElementsCounts[j] = 0;
			}
		}
	}
}

2.8 堆排序

2.8.1 基本介绍：

1. 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
2. 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆, 注意: 没有要求结点的左孩子的值和右孩子的值的大小关系。
3. 每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆
4. 大顶堆举例说明
   
5. 小顶堆举例说明
   
6. 一般升序采用大顶堆，降序采用小顶堆

2.8.2 基本思想：

将待排序序列构造成一个大顶堆
2) 此时，整个序列的最大值就是堆顶的根节点。
3) 将其与末尾元素进行交换，此时末尾就为最大值。
4) 然后将剩余n-1 个元素重新构造成一个堆，这样会得到n 个元素的次小值。如此反复执行，便能得到一个有序序列了。

可以看到在构建大顶堆的过程中，元素的个数逐渐减少，最后就得到一个有序序列了.

2.8.3 示意图：

2.8.4 代码实现：

package com.czn.sort;

import java.util.Arrays;

public class Sort8HeapSort {
	public static void main(String[] args) {
		int[] arr = { 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		heapSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void heapSort(int[] arr) {
		// 将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆
		for (int i = arr.length / 2 - 1; i >= 0; i--) {
			adjustHeap(arr, i, arr.length);
		}

		/*
		 * 2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
		 * 3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
		 */
		for (int j = arr.length - 1; j > 0; j--) {
			// 交换
			int temp = arr[j];
			arr[j] = arr[0];
			arr[0] = temp;
			adjustHeap(arr, 0, j);
		}
	}

	// 将一个数组(二叉树), 调整成一个大顶堆
	/**
	 * 功能： 完成 将 以 i 对应的非叶子结点的树调整成大顶堆 举例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 =>
	 * adjustHeap => 得到 {4, 9, 8, 5, 6} 如果我们再次调用 adjustHeap 传入的是 i = 0 => 得到 {4, 9,
	 * 8, 5, 6} => {9,6,8,5, 4}
	 * 
	 * @param arr    待调整的数组
	 * @param i      表示非叶子结点在数组中索引
	 * @param lenght 表示对多少个元素继续调整， length 是在逐渐的减少
	 */
	public static void adjustHeap(int arr[], int i, int lenght) {

		int temp = arr[i];// 先取出当前元素的值，保存在临时变量
		// 开始调整
		// 说明
		// 1. k = i * 2 + 1 k 是 i结点的左子结点
		for (int k = i * 2 + 1; k < lenght; k = k * 2 + 1) {
			if (k + 1 < lenght && arr[k] < arr[k + 1]) { // 说明左子结点的值小于右子结点的值
				k++; // k 指向右子结点
			}
			if (arr[k] > temp) { // 如果子结点大于父结点
				arr[i] = arr[k]; // 把较大的值赋给当前结点
				i = k; // !!! i 指向 k,继续循环比较
			} else {
				break;// !
			}
		}
		// 当for 循环结束后，我们已经将以i 为父结点的树的最大值，放在了 最顶(局部)
		arr[i] = temp;// 将temp值放到调整后的位置
	}
}

2.8.5 堆排序小总结：

1).将无序序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
2).将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;
3).重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

三、总结

3.1 排序算法的比较图

3.2 相关术语解释

1. 稳定：如果a 原本在b 前面，而a=b，排序之后a 仍然在b 的前面；
2. 不稳定：如果a 原本在b 的前面，而a=b，排序之后a 可能会出现在b 的后面；
3. 内排序：所有排序操作都在内存中完成；
4. 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
5. 时间复杂度： 一个算法执行所耗费的时间。
6. 空间复杂度：运行完一个程序所需内存的大小。
7. n: 数据规模
8. k: “桶”的个数
9. In-place: 不占用额外内存
10. Out-place: 占用额外内存

参考资料：尚硅谷_韩顺平_图解Java数据结构和算法 视频地址

本文地址：https://blog.csdn.net/Beyondczn/article/details/107356181