本文共 4272 字，大约阅读时间需要 14 分钟。
Java四大排序
三、交换排序 (1)冒泡排序 冒泡排序顾名思义就是将数组中相应的元素通过每一次两两比较达到最顶，类似于冒泡称之为冒泡排序 排序过程描述： 1.依次拿到每一个数组中的元素 依次遍历 2.拿到的数字与之后的每一位数字比较 如果小于数组中的数字则交换位置 3.当数组的每一个元素都被排完之后数组按照要求拍好 算法描述 1.一个外层循环遍历整个要排序的数组 2.内层循环将拿到的数字依次向后比较 3.始终将最大的元素向后交换 代码实现public static void bubbleSort(int[] array){ long start = System.nanoTime(); int len = array.length; for(int i = 0;i 总结：
1.冒泡排序规则简单 2.特别耗费时间 时间复杂度 O(N²) 3.空间复杂度 O(1) 4.稳定性 稳定 没有交换 有序 冒泡排序的时间4364775394纳秒 无序 冒泡排序的时间10826013855纳秒 （2）快速排序 快速排序就是一种不断找中轴线的办法 非递归排序过程描述： 1.在第一次时在数组中选取一个数字记为 par 存入临时tmp中 2.将之后的数字依次与这个数进行比较比这个数字小存放到左边大的放到右边 3.第一次整个数组无形中分为两个数组 4.在这两个小数组再次继续进行排序 5.直到不能分组为止 非递归算法描述： 1.partion方法 通过传入数组的最小 low 与 最大 high (1)本质上是随机取出 在这里为 tmp=array[low] 存放到 tmp中作为标志中轴线 (2)依据中轴线 左侧存放小于中轴线的值右侧存放大于中轴线的值 交换过程 [1]从high 当high>=tmp high-- 结束此次循环拿到从high开始第一个小于的值 array[high] [2]如果此时low==high 则证明此时的high就是low也就无需交换 [3]如果不是 将array[high]的值 赋给array[low] [4]再从左侧开始寻找array[low]>=tmp的值 结束循环 记为 low [5]在交换位置 当low>=high时结束循环 将tmp返回array[low] 2.通过第一次传入整个数组完成第一次分组 将此时的low high 压入栈 符合情况的数组至少两个值 a.当par>low+1 证明左侧符合情况 压入 low par-1 b.当par<high-1 证明右侧符合情况压入 par+1 high 3.利用栈的特性top>0 从栈内弹出两个元素high low 循环传入partion中 直到栈内没有元素完成排序 代码实现public static void quickSort_Un(int[] array){ long start = System.nanoTime(); //使用数组模拟栈 int[] stack = new int[array.length*2]; int top=0; int low=0; int high=array.length-1; int par = partion(array,low,high); //先执行一次找出第一次的par if(par>low+1){ //判断左边 符合情况入栈 判断左边是否有两个值 stack[top++] = low; //先存左边后存右边 stack[top++] = par-1; } if(par 0){ //判断右边是否有两个值 high = stack[top--]; //第一个元素为high par= stack[top--]; par= partion(array,low,par); if(par>low+1){ //判断左边 符合情况入栈 判断左边是否有两个值 stack[top++] = low; //先存左边后存右边 stack[top++] = par-1; } if(par =tmp) { //进入的条件当前面的值比目标小 从后面拿到比par小的值 high--; } if(low==high){ break; }else{ array[low]=array[high]; } while((low <=tmp){ //进入条件找目标值大 low++; } if(low==high){ break; }else{ array[high]=array[low]; } } array[low]=tmp; return low;} 总结：
1.非递归的方式利用栈的特性存放low 于 high 有序 快速排序非递归时间1921777毫秒 无序 快速排序非递归时间1779999毫秒 递归排序过程描述 1.将栈的功能使用递归的思想去解决替代 递归排序算法描述 1.递归截止的条件为 start==end 此时return 2.在进行递归之前，先进行第一次排序完成简单分组 调用partion返回第一次调用时的 基准值移动后的 下标low 3.当par>start+1 整理左侧调用 quickSort2 4.当par<end-1 整理右侧调用 quickSort2 代码实现public static void quickSort2(int[] array,int start,int end){ if(start==end){ return; } int par =partion(array,start,end); if(par>start+1){ quickSort2(array,start,par-1); } if(par 1.在进行有序排序时 StackOverflowError 的异常是因为虚拟机栈溢出 函数在调用时太深为了解决这个问题 我们尽可能的避免调用方法太深
优化代码（三数取中）public static void quick(int[] array,int low,int high){ if(low==high) { return; } if(high-low+1 <= 10){ insertSort(array,low,high); } takeThreadNumber(array,low,high); int par = partion(array, low, high); //递归左边 if(par>low+1){ quick(array,low,par-1); } //递归右边 if(par >>1; if(array[mid]>array[low]){ swap(array,low,mid); } if(array[mid]>array[high]){ swap(array,mid,high); } if(array[low]>array[high]){ swap(array,low,high); }} 1.为了避免在调用时过于深而导致的栈溢出问题
（1）在排序中选取基准值时采用三数取中 就是在每一次在数组中前中后选取三个数拿出最小的一个 （2）在当数数组元素足够小时采用插入排序 有序 快速排序时间11051995纳秒 无序 快速排序时间24288878纳秒 优化代码（随机选取） 在partion函数中 选取基准值之前 swap(array,low,(int)(Math.random()*(high-low+1)+low)); 目的就是在每一次选取基准值时达到随机 在解决近似随机的数组是提高效率，但是对于无序的数组影响不大 有序 快速排序时间14744882纳秒 无序 快速排序时间24763989纳秒 优化代码（两路快排） 双路快排是通过对partion函数的优化达到提高效率的目的public static int partion2(int[] array,int low,int high){ swap(array,low,(int)(Math.random()*(high-low+1)+low)); int tmp = array[low]; int i=low+1; int j =high; while(i =low&&array[j]>tmp){ j--; } if(i>=j){ break; }else{ swap(array,i++,j--); } } swap(array,low,j); return i;} 有序
快速排序时间11253772纳秒 无序 快速排序时间19635102纳秒 总结： 1.快速排序就是不停的选取基准值然后以基准值为分界线划分数组，通过不断划分数组越来越小最后到达排序的目的 2.时间复杂度 O（N*logN） 3.空间复杂度O（logN） 4.不稳定转载地址：http://fuza.baihongyu.com/