必须知道的排序算法—Java实现
1 冒泡排序
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
冒泡排序动画演示
冒泡排序的算法实现如下:
/**
* 冒泡排序
* 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
* 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。
* 在这一点，最后的元素应该会是最大的数。
*
* 针对所有的元素重复以上的步骤，除了最后一个。
* 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
* @param numbers 需要排序的整型数组
*/
public static void bubbleSort(int[] numbers)
{
int temp = 0;
int size = numbers.length;
for(int i = 0 ; i < size-1; i ++)
{
for(int j = 0 ;j < size-1-i ; j++)
{
if(numbers[j] > numbers[j+1]) // 交换两数位置
{
temp = numbers[j];
numbers[j] = numbers[j+1];
numbers[j+1] = temp;
}
}
}
}
2 快速排序
快速排序的基本思想： 通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序。
快速排序动画演示
RANDOM QUICK SORT动画演示
快速排序的算法实现如下:
/**
* 查找出中轴（默认是最低位low）的在numbers数组排序后所在位置
* @param numbers 待排序数组
* @param low 开始位置
* @param high 结束位置
* @return 中轴所在位置
*/
public static int getMiddle(int[] numbers, int low,int high)
{
int temp = numbers[low]; // 数组的第一个作为中轴
while(low < high)
{
while(low < high && numbers[high] > temp)
{
high--;
}
numbers[low] = numbers[high]; // 比中轴小的记录移到低端
while(low < high && numbers[low] < temp)
{
low++;
}
numbers[high] = numbers[low] ; // 比中轴大的记录移到高端
}
numbers[low] = temp ; // 中轴记录到尾
return low ; // 返回中轴的位置
}
/**
* 递归形式的分治排序算法
* @param numbers 待排序数组
* @param low 开始位置
* @param high 结束位置
*/
public static void quickSort(int[] numbers,int low,int high) {
if(low < high) {
int middle = getMiddle(numbers,low,high); // 将numbers数组进行一分为二
quickSort(numbers, low, middle-1); // 对低字段表进行递归排序
quickSort(numbers, middle+1, high); // 对高字段表进行递归排序
}
}
/**
* 快速排序提供方法调用
* @param numbers 待排序数组
*/
public static void quick(int[] numbers) {
// 查看数组是否为空
if(numbers.length > 0) {
quickSort(numbers, 0, numbers.length-1);
}
}
3 选择排序
基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换；然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。
选择排序动画演示
算法实现
/**
* 选择排序算法
* 在未排序序列中找到最小元素，存放到排序序列的起始位置;
* 再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。
* 以此类推，直到所有元素均排序完毕。
* @param numbers
*/
public static void selectSort(int[] numbers) {
int size = numbers.length; // 数组长度
int temp = 0 ; // 中间变量
for(int i = 0 ; i < size ; i++) {
int k = i; // 待确定的位置
// 选择出应该在第i个位置的数
for(int j = size -1 ; j > i ; j--) {
if(numbers[j] < numbers[k]) {
k = j;
}
}
// 交换两个数
temp = numbers[i];
numbers[i] = numbers[k];
numbers[k] = temp;
}
}
4 堆排序
堆排序（Heap Sort）是由J.Williams在1964年提出的，它是在选择排序的基础上发展起来的，比选择排序的效率要高，因此也可以说堆排序是选择排序的升级版。堆排序除了是一种排序方法外，还涉及到方法之外的一些概念：堆和完全二叉树。这里主要说说什么是堆？
如果将堆看成一棵完全二叉树，则这棵完全二叉树中的每个非叶子节点的值均不大于（或不小于）其左、右孩子节点的值。由此可知，若一棵完全二叉树是堆，则根节点一定是这棵树的所有节点的最小元素或最大元素。非叶子节点的值大于其左、右孩子节点的值的堆称为大根堆，反之则称为下小根堆。
堆排序动画演示
算法实现
/**
* 构建大顶堆
* @param R
* @param low
* @param high
*/
public static void sift(int[] R,int low,int high) {
int i=low,j=i*2;
int temp = R[i];
while(j<=high) {
if(j<high&&R[j]<R[j+1]) {
j++;
}
if(temp<R[j]) {
R[i]=R[j];
i=j;
j=2*i;
} else {
break;
}
}
R[i]=temp;
}
/**
* 堆排序
* @param R
*/
public static void heapSort(int[] R) {
int i,j;
int n = R.length-1;
int temp;
for(i=n/2;i>=1;--i) { //初始化（大根）堆
sift(R,i,n);
}
// 堆排序
for(j=n;j>=2;j--) {
temp=R[1];
R[1]=R[j];
R[j]=temp;
sift(R,1,j-1);
}
}
5 插入排序
基本思想：每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的字序列的合适位置（从后向前找到合适位置后），直到全部插入排序完为止。
插入排序动画演示
算法实现
/**
* 插入排序
*
* 从第一个元素开始，该元素可以认为已经被排序
* 取出下一个元素，在已经排序的元素序列中从后向前扫描
* 如果该元素（已排序）大于新元素，将该元素移到下一位置
* 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
* 将新元素插入到该位置中
* 重复步骤2
* @param numbers 待排序数组
*/
public static void insertSort(int[] numbers) {
int size = numbers.length;
int temp = 0 ;
int j = 0;
for(int i = 0 ; i < size ; i++) {
temp = numbers[i];
// 假如temp比前面的值小，则将前面的值后移
for(j = i ; j > 0 && temp < numbers[j-1] ; j --) {
numbers[j] = numbers[j-1];
}
numbers[j] = temp;
}
}
6 希尔排序
希尔排序是D.L.Shell于1959年提出来的一种排序算法，在这之前排序算法的时间复杂度基本都是O(
n *n)的，希尔排序算法是突破这个时间复杂度的第一批算法之一，它是直接插入排序的升级版。希尔排序的基本思想是：将待排序的记录分成几组，从而减少参与直接插入排序的数据量，当经过几次分组之后，记录的排列已经基本有序，这时再对所有记录实施直接插入排序。
希尔排序的主要特点是排序的每一趟均以不同的间隔数对子序列进行排序，当间隔数很大时，被移动的元素是以跳跃式进行的。而当间隔数=1时，序列则几乎已经有序，只需要进行很少的元素移动，就能最终达到排序的目的。
希尔排序动画演示
算法实现
/**
*
* 希尔排序是加强版的插入排序
*
* 希尔排序的原理:
* 根据需求，如果你想要结果从大到小排列，它会首先将数组进行分组，然后将较大值移到前面，较小值
* 移到后面，最后将整个数组进行插入排序，
* 这样比起一开始就用插入排序减少了数据交换和移动的次数，可以说希尔排序是加强版的插入排序
* 拿数组5, 2, 8, 9, 1, 3，4来说，数组长度为7，当increment为3时，数组分为两个序列
* 5，2，8和9，1，3，4，第一次排序，9和5比较，1和2比较，3和8比较，
* 4和比其下标值小increment的数组值相比较
* 此例子是按照从大到小排列，所以大的会排在前面，第一次排序后数组为9, 2, 8, 5, 1, 3，4
* 第一次后increment的值变为3/2=1,此时对数组进行插入排序，
* 实现数组从大到小排
*/
public static void shellSort01(int[] data) {
int j = 0;
int temp = 0;
// 每次将步长缩短为原来的一半
for (int increment = data.length / 2; increment > 0; increment /= 2) {
for (int i = increment; i < data.length; i++) {
temp = data[i];
for (j = i; j >= increment; j -= increment) {
/**
* 如想从小到大排只需修改这里
if(temp > data[j - increment]) {
data[j] = data[j - increment];
}
else {
break;
}
*/
if (temp < data[j]) {
data[j + increment] = data[j];
} else {
break;
}
}
data[j] = temp;
}
}
}
/**
* 希尔排序
* @param arr
*/
public static void shellSort02(int[] arr) {
int j;
int len = arr.length;
for(int val=len>>1; val>0; val>>=1) {
// 下面是对本次的所有分组做直接插入排序
for(int i=val; i<len; i++) {
/**
* 为什么每次都用temp比较呢？
* 因为直接插入就是找到temp的合适位置。
* 为什么temp<arr[j-val]这个条件可以放在for内呢？
* 因为原来的组内数据已经有序，找到位置就停止便是。
* 不甚理解的去看直接插入排序吧。
*/
int temp = arr[i];
for(j=i; j>=val&&temp<arr[j-val]; j-=val) {
/**
* 为什么是arr[j-val]不是arr[j]呢？
* 因为j=i开始的，而且条件是j>=val&&temp<arr[j-val]
*/
arr[j] = arr[j-val];
}
/**
* 注意不是arr[i] = temp
* 直接插入排序也是这样的。
* 为什么呢？
* 因为j是位置，i是待插入元素
*/
arr[j] = temp;
}
}
}
总结：Shell排序适用于待排序记录数量较大的情况，在此情况下，Shell排序一般要比直接插入排序要快（从直接插入排序结果的1061ms到希尔排序的21ms）。1971年，斯坦福大学的两位教授在大量实验的基础上推导出Shell排序的时间复杂度约为O(n1.3)，使得我们终于突破了慢速排序的时代（超越了时间复杂度为O(n2)）。
7 归并排序
基本思想：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序动画演示
算法实现
/**
* 将数组中low到high位置的数进行排序
* @param nums 待排序数组
* @param low 待排的开始位置
* @param mid 待排中间位置
* @param high 待排结束位置
*/
public static void merge(int[] nums, int low, int mid, int high) {
int[] temp = new int[high - low + 1];
int i = low; // 左指针
int j = mid + 1; // 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
/**
* 归并排序
* 将两个（或两个以上）有序表合并成一个新的有序表
* 即把待排序序列分为若干个子序列，每个子序列是有序的。
* 然后再把有序子序列合并为整体有序序列
* @param nums 待排序数组
* @param low 待排序数组的第一个元素索引
* @param high 待排序数组的最后一个元素索引
* @return 输出有序数组
*/
public static int[] sort(int[] nums, int low, int high) {
int mid = (low + high) / 2;
if (low < high) {
// 左边
sort(nums, low, mid);
// 右边
sort(nums, mid + 1, high);
// 左右归并
merge(nums, low, mid, high);
}
return nums;
}
/**
* 归并排序
* @param data 待排序数组
*/
public static void mergeSort(int[] data) {
sort(data,0,data.length-1);
}
8 桶排序
基数排序(radix sort)又称桶排序（bucket sort），相对于常见的比较排序，基数排序是一种分配式排序，即通过将所有数字分配到应在的位置最后再覆盖到原数组完成排序的过程。
桶排序适用数据范围
桶排序可用于最大最小值相差较大的数据情况，比如[9012,19702,39867,68957,83556,102456]。
但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。
过程分析
桶排序的基本思想是：把数组 arr 划分为n个大小相同子区间（桶），每个子区间各自排序，最后合并。
计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。
基数排序动画演示
- 找出待排序数组中的最大值max、最小值min；
- 我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1；
- 遍历数组 arr，计算每个元素 arr[i] 放的桶；
- 每个桶各自排序；
- 遍历桶数组，把排序好的元素放进输出数组。
算法实现
/**
* 桶排序
* @param arr 待排序数组
*/
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));
}
}
9 计数排序
计数排序适用数据范围
计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0100]，[1000019999] 这样的数据。
过程分析
计数排序的基本思想是：对每一个输入的元素arr[i]，确定小于 arr[i] 的元素个数。
所以可以直接把 arr[i] 放到它输出数组中的位置上。假设有5个数小于 arr[i]，所以 arr[i] 应该放在数组的第6个位置上。
计数排序动画演示
- 算法流程（1）
需要三个数组:
待排序数组 int[] arr = new int[]{4,3,6,3,5,1};
辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1
输出数组 int[] res = new int[arr.length];
- 求出待排序数组的最大值max=6， 最小值min=1
- 实例化辅助计数数组help，help数组中每个下标对应arr中的一个元素，help用来记录每个元素出现的次数
- 计算 arr 中每个元素在help中的位置 position = arr[i] - min，此时 help = [1,0,2,1,1,1]; （3出现了两次，2未出现）
- 根据 help 数组求得排序后的数组，此时 res = [1,3,3,4,5,6]
/**
* 计数排序
* @param arr 待排序数组
* @return
*/
public static int[] countSort1(int[] arr) {
if (arr == null || arr.length == 0) {
return null;
}
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]);
}
/**
* 辅助计数数组
* 该数组大小为待排序数组中的最大值减最小值+1
*/
int help[] = new int[max];
// 找出每个数字出现的次数
for(int i = 0; i < arr.length; i++){
int mapPos = arr[i] - min;
help[mapPos]++;
}
int index = 0;
for(int i = 0; i < help.length; i++) {
while(help[i]-- > 0) {
arr[index++] = i+min;
}
}
return arr;
}
- 算法流程（2）
需要三个数组:
待排序数组 int[] arr = new int[]{4,3,6,3,5,1};
辅助计数数组 int[] help = new int[max - min + 1]; //该数组大小为待排序数组中的最大值减最小值+1
输出数组 int[] res = new int[arr.length];
- 求出待排序数组的最大值max=6， 最小值min=1
- 实例化辅助计数数组help，help用来记录每个元素之前出现的元素个数
- 计算 arr 每个数字应该在排序后数组中应该处于的位置，此时 help = [1,1,4,5,6,7];
- 根据 help 数组求得排序后的数组，此时 res = [1,3,3,4,5,6]
/**
* 计数排序
* @param arr 待排序数组
* @return
*/
public static int[] countSort2(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[] help = new int[max - min + 1];
// 找出每个数字出现的次数
for(int i = 0; i < arr.length; i++){
int mapPos = arr[i] - min;
help[mapPos]++;
}
// 计算每个数字应该在排序后数组中应该处于的位置
for(int i = 1; i < help.length; i++){
help[i] = help[i-1] + help[i];
}
// 根据help数组进行排序
int res[] = new int[arr.length];
for(int i = 0; i < arr.length; i++){
int post = --help[arr[i] - min];
res[post] = arr[i];
}
return res;
}
各种算法的时间复杂度
排序对比
各种算法的时间复杂度
网友评论