排序算法
java语言代码
package com;
import java.util.Random;
/**
* user:tanjun
* date:2018/11/7
* desc:
*/
public class App {
public static void main(String[] args) {
int [] arr = new int[10000000];
Random rd = new Random(1);
for (int i = 0; i < arr.length; i++) {
int v = rd.nextInt(arr.length);
arr[i] = v;
}
//插入排序
int [] arr1 = arr.clone();
long start1 = System.currentTimeMillis();
//int [] nowArr1 = App.insertSort(arr1);
long end1 = System.currentTimeMillis();
System.out.println("insertSort 排序 随机数:" + arr.length + ",耗时:" + (end1 - start1) +"毫秒");
//希尔排序
int [] arr2 = arr.clone();
long start2 = System.currentTimeMillis();
//int [] nowArr2 = App.hillSort(arr2);
long end2 = System.currentTimeMillis();
System.out.println("hillSort 排序 随机数:" + arr.length + ",耗时:" + (end2 - start2) +"毫秒");
//二分插入排序
int [] arr3 = arr.clone();
long start3 = System.currentTimeMillis();
//int [] nowArr3 = App.insert2BranchSort(arr3);
long end3 = System.currentTimeMillis();
System.out.println("insert2BranchSort 排序 随机数:" + arr.length + ",耗时:" + (end3 - start3) +"毫秒");
//堆排序
int [] arr4 = arr.clone();
long start4 = System.currentTimeMillis();
int [] nowArr4 = App.heapSort(arr4);
long end4 = System.currentTimeMillis();
System.out.println("heapSort 排序 随机数:" + arr.length + ",耗时:" + (end4 - start4) +"毫秒");
//归并排序
int [] arr5 = arr.clone();
long start5 = System.currentTimeMillis();
int [] nowArr5 = App.mergeSort(arr5);
long end5 = System.currentTimeMillis();
System.out.println("mergeSort 排序 随机数:" + arr.length + ",耗时:" + (end5 - start5) +"毫秒");
//快速排序
int [] arr6 = arr.clone();
long start6 = System.currentTimeMillis();
int [] nowArr6 = App.fastSort(arr6);
long end6 = System.currentTimeMillis();
System.out.println("fastSort 排序 随机数:" + arr.length + ",耗时:" + (end6 - start6) +"毫秒");
for (int i = 0; i < arr.length; i++) {
//System.out.println("heapSort =" + nowArr4[i] + ",mergeSort =" + nowArr5[i] + ",fastSort =" + nowArr6[i]);
}
}
/**
* 插入排序(升序)
* 稳定算法：两个相同的值比较后不交换位置为稳定算法
* 解：
* 1.外层循环,遍历数组中所有的值，每次遍历的时候讲当前下标的值存入temp中
* 2.内存循环,遍历小于i的所有下标的值,将小于i的下标变量命名为j,每次将下标j中的值与temp比较
* 3.如果j下标的值大于了temp则将当前j下标的值存入j+1的下标中,往后移动一个位置。
* 4.j + 1 最大的值则是=i,这意思是如果发生移动，j下标中最大的值将会被移动到i的位置上
* 5.temp 值将会插入到最后一个值大于它的下标j中,因为最后会执行一次j--,所以最终是需要把temp存入j+1的位置上
* 优势：
* 1.直接找到不大于temp值下标位置,将这个位置后面的值都往后移动，再将temp插入到目标下标,减少了n次赋值给临时位置上的操作
* 2.因为j下标内所有的值都是有序的,所以可以将j部分的比较改成使用二分查找的方式,这可以提升一部分性能
* 3.插入排序在对几乎有序的数组排序效率高,因为减少了赋值操作,所以比冒泡排序要快一点,但时间复杂度还是一样的
* 时间复杂度：
* 最坏:O(n²)
* 最好:O(n)
* 平均:O(n²)
* 空间复杂度:
* 总共:O(n)
* @param arr
* @return
*/
public static int [] insertSort(int [] arr){
for (int i = 1; i < arr.length; ++i) {
int temp = arr[i];
int j = i - 1;
while (j > -1 && arr[j] > temp){
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = temp;
}
return arr;
}
/**
* 二分查找插入排序
* 解:
* 1.与插入排序主要的区别是,不是每个元素都去比较大小,也不是边比较边后移动位置
* 2.先使用二分查找找出下标(i)的元素应该被插入到哪个下标(left)
* 3.然后从这个位置开始把后面所有的元素后移一位,再将temp插入到left位置
* 4.不建议小数量使用二分查找插入排序,速度也许比插入排序更慢
* 优势:
* 相比插入排序,在数量较大的情况下因为缩小了比较次数,性能会随着数据量越大,缩小的次数越多提升速度
* @param arr
* @return
*/
public static int [] insert2BranchSort(int [] arr){
for (int i = 1; i < arr.length; ++i) {
int temp = arr[i];
int j = i - 1;
int left = 0;
int right = j;
while (left <= right){
// >> 1是 /2 的意思,当前搜索位置=起点位置 + ((结束位置-起点位置) / 2),结束位置-起点位置是去掉已经搜索过的长度 >>1 得到新的分开点,+ 起点位置是将下标位移到实际搜索下标上
int middle = ((right-left) >> 1) + left;
if (arr[middle] > temp){
right = middle - 1;//当搜索值大于指定值,则代表分开位置右边全都是大于制定值的,所以将最大范围指定到当前位置-1
}else{//如果附近都是几个一样的值,则找到最后一个的位置,这用于排序,如果只需要找,则找出第一个就可以返回了
left = middle + 1;//当搜索值小于指定值,则代表分开位置左边全是小于指定值,所以将最小范围指定到当前位置+1
}
}
--left;
while (j > left) {
arr[j + 1] = arr[j];
--j;
}
arr[++left] = temp;
}
return arr;
}
/**
* 希尔排序 or 缩减增量排序(升序)
* 不稳定算法:因为分组原因,会造成相同数据处于不同分组事会改变位置
* 解:
* 1.希尔排序在数据量较小的时候比插入排序要慢,至少要10万才能看得出
* 2.希尔排序是插入排序升级版,排序功能代码就是插入排序
* 3.从一开始分成了很多段数组,然后慢慢减少分段的数量
* 4.在不同的分段中都是有序的,慢慢的形成了几乎有序的情况,那么就满足了插入排序的优势了,直到增量参数变为1则最后再执行一次插入排序
* 5.不建议将内部的插入排序代码改成二分搜索,因为外层的分组导致每个数组的数据量很小,不具备二分搜索的优势,会更慢执行
* 优势:
* 1.对几乎有序的数据效率高
* 2.对最坏场景的数据能减少时间的损耗,因为分段排序时在不停的制造相对有序的数据.
* 时间复杂度:
* 最坏:O(n log2 n)
* 最好:O(n)
* 平均:O(n log2 n)
* 空间复杂度:
* 总共:O(n)
* @param arr
* @return
*/
public static int [] hillSort(int [] arr){
int section = arr.length >> 1;
while (section > 0){
for (int i = section; i < arr.length; ++i) {
int temp = arr[i];
int j = i - 1;
while (j > -1 && arr[j] > temp){
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = temp;
}
section = section >> 1;
}
return arr;
}
/**
* 堆排序部分代码
* 初始定义 i 为父节点,left = i * 2 + 1 为左子树,left + 1 为右子树
* 遵守左子树,右子树都要比父节点的值小
* 最终 0 下标的值是最大的,它的左子树1,右子树2中的值比它小,并且它的左右子树同样遵守小于它的直属父节点的规则
* @param arr
* @param i
* @param n
*/
private static void heapSort1(int [] arr,int i,int n){
int child;
int temp = arr[i];
while ((child = (i << 1) + 1) < n - 1){
//如果左子树小于右子树，则需要比较右子树和父节点,如果左子树大于右子树,则需要拿左子树和父节点比较
if(arr[child] < arr[child + 1]){
++child;//child目前指向的是i的左子树,现在右子树比左子树大,左子树不动,child 自增1 指向右子树
}
//child 有指向左子树,或右子树,无论指向谁,它一定要比另一个的值大,所以现在需要拿它与父节点比较,
//如果大于了父节点,则将值移动到父节点上,遵守父节点大于左右子树的值规则
if(temp < arr[child]){
arr[i] = arr[child];
}else{
break;//左右子树本身就小于父节点,遵守了规则,不需要做任何改变
}
i = child;//再将本次值最大的下标重新设置为父节点,检查它下面的左右子树是否遵守规则,以此类推
}
arr[i] = temp;
}
/**
* 堆排序(升序)
* 不稳定算法:因为处于不同的子节点项中,相同的值会改变位置
* 解:
* 1.将个数组分为两半,后半部分用来存储比较后遵守左右子树小于父节点规则的左右子树值,前半部分用来存储父节点
* 2.注意一根公式,假设父节点是 i 那么它的左子树 是 i * 2 + 1,右子树是 i * 2 + 2
* 3.初始的时候 将数组分为两半 父节点位置为 i,第一次找左子树,肯定会大于了数组的整个长度,所以这个时候i不能作为父节点,继续--i定义下一个父节点
* 4.由于公式问题,计算出来的左子树右子树位置到了后面肯定出现前面被当做父节点过,没关系,继续把它当左右子树来比较.
* 优势:
* 反正就是快,飞快
* 时间复杂度:
* 最坏:O(n log2 n)
* 最好:O(n log2 n)
* 平均:O(n log2 n)
* 空间复杂度:
* 总共:O(n)
* @param arr
* @return
*/
public static int[] heapSort(int [] arr){
//把数组分为两半,后半部分用来存储每次比较后的左右子树,前半部分用来存父节点的,将所有父节点循环结束,最终它们会变成一颗完全二叉树
for (int i = arr.length >> 1; i > -1; --i) {
heapSort1(arr,i,arr.length);
}
//循环每个元素,经过上面的组装完全二叉树,0下面的值是最大的
for (int i = arr.length - 1; i > 0; --i) {
//因为0坐标中始终是本次检查范围的最大值(注意不代表它是整个数组中最大的,这取决于i每次的最大范围是多少)
// 所以每次都需要将0与本次检查范围最大下标中的值交换位置,
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapSort1(arr,0,i);//每次交换后把0位置当做父节点,i当做最大检查范围
}
return arr;
}
/**
* 归并排序一部分代码
* 将传入进来的数组长度每次 / 2 再把分成的两份数组再传入当前方法中,递归至最后只剩一个长度
* 然后再将前部分数组与后部分数组比较,慢慢返回出递归方法,那么从最底层数组的长度为1,慢慢的退回长度2,4,6...等
* 直至最大长度/2的两段数组来比较,最终结束本次排序
* @param arr
* @param temp
* @param start
* @param end
*/
private static void mergeSort1(int[] arr, int[] temp, int start, int end) {
if (start >= end)
return;
int len = end - start; //总共剩余多少未检索
//每次需要将还未检索的部分分成两份,将前部分与后部分比较,分到最底层就是2长度
//前半部分
int l_start_1 = start;//前半部分起始位置
int l_end_1 = (len >> 1) + start;//前半部分结束位置
//后半部分
int l_start_2 = l_end_1 + 1;//后半部分起始位置
int l_end_2 = end;//后半部分结束位置
mergeSort1(arr, temp, l_start_1, l_end_1);
mergeSort1(arr, temp, l_start_2, l_end_2);
int k = start;
while (l_start_1 <= l_end_1 && l_start_2 <= l_end_2)//将前部分数组与后部分数组进行比较,谁小则赋值给临时存储数组
temp[k++] = arr[l_start_1] < arr[l_start_2] ? arr[l_start_1++] : arr[l_start_2++];
//因为上面的while只是把两个数组中比较小的值先存入temp里面,因此下面的两个while是把比较大的值存到temp后面,这样就形成了小的在前面大的在后面,一样大的不动
while (l_start_1 <= l_end_1)
temp[k++] = arr[l_start_1++];
while (l_start_2 <= l_end_2)
temp[k++] = arr[l_start_2++];
//将本次比较的数组段赋值到数组源中对应的位置
for (k = start; k <= end; k++)
arr[k] = temp[k];
}
/**
* 归并排序(升序)
* 稳定算法:相同的值不交换位置,虽然存在相同的值存在不同数组,但是并不会用本数组的值与本数组比较.再加上分成的数组最底层只要一个长度
* 解:
* 1.分治算法,将一个数组一直/2直到最终数组只剩一个元素,然后拿这个数组与另一个数组比较
* 2.它需要额外的内存空间来保存临时比较后的值
* 优势:
* 反正就是快,飞快
* 经过多次随机数测试,在100万以下是慢与堆排序,达到500万以上的时候比堆排序块很多,所以数据量大的时候使用归并排序,当然不考虑节约内存的情况
* 时间复杂度:
* 最坏:O(n log2 n)
* 最好:O(n log2 n)
* 平均:O(n log2 n)
* 空间复杂度:
* 总共:O(n),需要额外的n长度数组辅助空间
*/
public static int [] mergeSort(int[] arr) {
int len = arr.length;
int[] temp = new int[len];
mergeSort1(arr, temp, 0, len - 1);
return arr;
}
/**
* 快速排序部分代码
* 将每次传进来的数组取中间的值与两端进行比较,再把大于它却排在它前的值与小于它却排在它后面的值交换为止
* 然后再把检查范围缩小,采用分治法继续递归检查
* @param arr
* @param start
* @param end
*/
public static void fastSort1(int[] arr, int start, int end) {
if (start >= end) {
return;
}
int t_start = start;
int t_end = end;
int pivot = arr[(start + end) >> 1];//本次比较参数
while (t_start < t_end) {
while (arr[t_start] < pivot)//升序比较,直到比较出不小于本次比较参数为止
++t_start;
while (arr[t_end] > pivot)//降序比较,直到比较出不大于本次比较参数为止
--t_end;
if (t_start < t_end) {//把不小于比较参数和不大于比较参数的值交换位置,然后把检查范围各自都缩小1
int t = arr[t_start];
arr[t_start++] = arr[t_end];
arr[t_end--] = t;
}else if (t_end == t_start)
++t_start;
}
//经过上面的循环,会把大于比较参数的值却排在了比较参数前面的值 与 小于比较参数的值却排在了比较参数的后面的值 交换为止
//下面执行分治法,每次都缩小比较范围.
fastSort1(arr, start, t_end);
fastSort1(arr, t_start, end);
}
/**
* 快速排序(升序)
* 不稳定算法:被分在不同段中的相同的值会交换为止
* 解:
* 将数组冲中间取出一个比较基数,比较左分段,和有分段,碰到了不符合条件的数据就将左右分段这个不符合条件的值交换位置
* 再将左右分段还未比较过的位置设置为开始,结束,再进行分开比较,递归至都满足升序条件位置
* 快速排序在绝大部分的时候都是要比堆排序,和归并排序要快,尤其是数据量特别大的时候
* 优势:
* 不需要额外的空间也能达到在大量数据下,绝大部分时候比堆排序,归并排序快,在机器内存不足,数据量很大的时候是很好的选择.
* 时间复杂度:
* 最坏:O(n²)
* 最好:O(n log2 n)
* 平均:O(n log2 n)
* 空间复杂度:
* 总共:O(n)
* @param arr
* @return
*/
public static int [] fastSort(int[] arr){
fastSort1(arr,0,arr.length -1);
return arr;
}
}