Java算法——排序算法
文章目录
排序的分类
-
内部排序
将需要处理的所有数据都加载到内部存储器中进行排序。 -
外部排序
数据量过大，无法全部加载到内存中，需要借助外部存储进行排序。内部排序分类：
插入排序（直接插入排序、希尔排序）
选择排序（简单选择排序、堆排序）
交换排序（冒泡排序、快速排序）
归并排序
基数排序
| 排序法 | 平均时间 | 最差情况 | 稳定度 | 额外空间 | 备注 |
|---|---|---|---|---|---|
| 冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
| 交换 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
| 选择 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
| 插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
| 基数 | O(logRB) | O(logRB) | 稳定 | O(n) | B是真数（0-9）R是基数（个十百） |
| shell | O(nlogn) | O(n^s)1<s<2 | 不稳定 | O(1) | s是所选分组 |
| 快排 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
| 归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
| 堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
测试代码
public static void main(String[] args) {
//测试速度
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int)(Math.random()*8000000);
}
Date date1 = new Date();
SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
String date1Str = simpleDateFormat.format(date1);
System.out.println("排序前时间"+date1Str);
//测试
具体的算法
Date date2 = new Date();
String date2Str = simpleDateFormat.format(date2);
System.out.println("排序后时间"+date2Str);
//System.out.println(Arrays.toString(arr));
}
冒泡排序(Bubble Sorting)
基本思想：通过对待排序序列从前往后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前往后移动。如果一趟下来没有进行交换，说明序列有序，可以设置flag标志判断元素是否进行过交换，从而减少不必要的比较。
例子：
原始数组：5，2，4，1，3
第一趟排序
（1）2，5，4，1，3
（2）2，4，5，1，3
（3）2，4，1，5，3
（4）2，4，1，3，5
第二趟排序
（1）2，4，1，3，5
（2）2，1，4，3，5
（3）2，1，3，4，5
第三趟排序
（1）1，2，3，4，5
（2）1，2，3，4，5
第四趟排序
（1）1，2，3，4，5
排序规则：
（1）一共进行数组的大小-1次大的循环
（2）每一趟排序的次数在逐渐的减小
（3）如果我们发现在某趟排序中，没有发生一次交换，可以提前结束冒泡排序。（优化）
代码实现
private static void Bubble(int[] arr){
int temp = 0;
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;
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
if (flag == false) {
//在一趟排序中，一次交换都没有发生
break;
} else {
flag = false;
}
}
}
分析：处理8万个数据的时间大概是9s左右。
选择排序(Select Sorting)
基本思想：第一次从arr[0]-arr[n-1]中选择最小值，与arr[0]交换，第二次从arr[1]-arr[n-1]中选择最小值，与arr[1]交换，以此类推，得到一个按排序码从小到大的有序序列。
例子：
原始数组：101，52，124，24
第一轮：24，52，124，101
第二轮：24，52，124，101
第二轮：24，52，101，124
排序规则：
（1）一共进行数组的大小-1次大的排序
（2）每一轮排序，又是一个循环，循环规则：先假定自己是最小数，与后面比较，若有更小的数，重新确定最小数，并得到下标，一轮结束后得到最小数及其下标，进行交换。
代码实现
private static void seleceSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
int min = arr[i];
for (int j = i + 1; j < arr.length; j++) {
if (min > arr[j]) {
min = arr[j];//找到最小值
minIndex = j;//找到最小值下标
}
}
//将最小值放在arr[0],即完成交换
if (minIndex != i) {
arr[minIndex] = arr[i];
arr[i] = min;
}
}
}
分析：处理8万个数据的时间大概是2-3s，比冒泡要快很多。
插入排序(Insert Sorting)
基本思想：把n个待排序的元素看为一个有序表和一个无序表，开始时有序表中只有一个元素，无序表里面有n-1个元素，排序过程中每次从无序表中取出一个元素，依次与有序表中的元素进行比较，插入适当的位置。
代码实现
private static void insertSort(int[] arr){
for (int i = 1; i < arr.length; i++) {
//定义待插入的数
int insertVal = arr[i];
int insertIndex = i - 1;
//insertIndex>=0保证给insertVal找插入位置，不越界
//insertVal<arr[insertIndex]待插入的数，还没有找到插入的位置
//就需要将arr[insertIndex]后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
//当退出循环时，说明找到了插入的位置，insertIndex+1
arr[insertIndex + 1] = insertVal;
}
}
分析：处理8万个数据的时间大概是1s，比冒泡、选择要快。当插入的数据较小的时候，后移的次数明显增多，对效率有影响。
希尔排序(Shell Sorting)
基本思想：把记录按下标的一定增量分组，对每组使用直接插入排序算法排序，随着增量减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分为一组，算法终止。
代码实现：
（1）交换法
/**
* 交换法
*
* @param arr
*/
public static void shellSort(int[] arr) {
int temp = 0;
for(int gap = arr.length/2;gap>0;gap/=2){
for (int i = gap; i < arr.length; i++) {
//遍历各组中所有的元素(共gap组，每组有个元素)
for (int j = i - gap; j >= 0; j -= gap) {
//如果当前元素大于加上步长后的那个元素，说明交换
if (arr[j] > arr[j + gap]) {
temp = arr[j];
arr[j] = arr[j + gap];
arr[j + gap] = temp;
}
}
}
}
}
（2）移位法
public static void shellSort(int[] arr) {
for(int gap = arr.length/2;gap>0;gap/=2){
for (int i = gap; i < arr.length; i++) {
int j=i;
int temp = arr[j];
if(arr[j]<arr[j-gap]){
while(j-gap>=0&&temp<arr[j-gap]){
arr[j] = arr[j-gap];
j-=gap;
}
}
}
}
}
分析：交换法时间为7s左右，移位法时间为2s左右。
快速排序(Quick Sorting)
基本思想：通过一趟排序，将要排序的数据分割成独立的两个部分，其中一部分的所有数据都比另外一部分的所有睡觉要小，递归得到有序序列。