冒泡、插入、选择、希尔、归并

xiaoxiao2021-02-28  21

排序算法概览:

    

排序算法之起泡排序

   起泡排序是最简单的排序算法,它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误(大于或小于)就把它们交换过来。这样数组中最大或最小的元素会一步一步的浮到数组的最后。直到重复执行 n-1次起泡循环,数组变成一个有序数组。

图解:

描述:第一步到第三步index总是小于index+1 所以不选择置换,当第四步 97 > 45 置换元素,置换后继续遍历,第五步

97 > 11置换元素。此时已遍历到数组末尾,所以无需继续遍历。最大值97已经遍历到数组末尾完成一次循环起泡动作。

整个数组一共需要完成 (数组长度 - 1) 次起泡动作。

java源代码:

/** * 起泡排序,返回一个排好序的数组 * i i+1 * 7 16 9 11 16 18 7 - 16 不换 * i i+1 * 7 16 9 11 16 18 16 - 9 换 * i i+1 * 7 9 16 11 16 18 16 - 11 换 * i i+1 * 7 9 11 16 16 18 16 - 16 不换 * ------------------------------ 准备从7执行下一个起泡的循环 * 7 9 11 16 16 18 * @param array * @return */ public static Integer[] bubbleOrder(Integer[] array){ for(Integer i = 0;i<array.length-1;i++) { for (Integer j = 0; j < array.length - (i + 1); j++) { if (array[j] > array[j + 1]) { Integer temp = array[j + 1]; array[j + 1] = array[j]; array[j] = temp; } } } return array; }

排序算法之插入排序

    插入排序是一整直观的,易理解的排序算法。即一个元素再元素前找位置插入进去,不断的通过找寻位置插入移位,使得整个数组变得有序。虽然简单易懂,但是不断的移位插入使得算法时间复杂度基本保持在O(n2)。

图解:

描述:设置p遍历指针 q查位指针,在遍历时,q找寻比p的合适位置,既大于左边又小于右边的位置。找到一个key用来保存当前p指针的值。接着q从p的前一位开始向前遍历,这里的判断条件为如果q的值大于key那么q+1位置上的值就变成q的位置上的值,直到q找到比key值小的元素,使q+1位的值等于key值。

因为原位置值改变了,所以我们需要用key记录下原位置的初始值,也是在为初始值找到一个合适的插入位置。

源代码:

/** * 插入排序,返回一个排序好的数组 * 提出key = array[i] = 13 * j i j与key比较 j大把j给j+1然后j-- * 7 16 18 13 11 8 2 16 1 * j i j再与key比较 j大把j给j+1然后j-- * 7 16 18 18 11 8 2 16 1 * j i j再与key比较 key大跳出循环 把key给j+1 然后插入成功 * 7 16 16 18 11 8 2 16 1 * ----------------i------------- 准备执行下一个i 的插入 * 7 13 16 18 11 8 2 16 1 * @param array * @return */ public static Integer[] insertOrder(Integer[] array){ Integer key = 0; for(int i = 1 ; i<array.length ; i++){ key = array[i]; int j; for(j = i-1 ; (j >= 0 && array[j] > key ) ; j--){ array[j+1] = array[j]; } array[j+1] = key; } return array; }

 

 

 

排序算法之选择排序

    选择排序算法也是很容易思考的排序算法,即里层遍历选择一个数组中最大或最小的元素,与当前外层遍历位的元素交换。每选择一次,就会确定一个排序位,数组排序成功一共需要选择n-1次。

图解:

描述:p是遍历的工作指针,min是查找数组中最小元素的指针,当第一步min为0,第二步13小于21,min为1,第三步9小于13,min为2 。 第四步 88大于9,所以min不变,总之就是记录最小的元素的下标。循环结束后,使min和外层遍历位index位交换元素位置。也就是图中 9 和 21 交换。外层继续循环 从index+1开始继续遍历。直到数组排序完成。

源代码:

/** * 选择排序,找到最小的,记录下标 * index = i //index记录最小的下标 * j 如果array[j]小于array[index] 那么就用index记录最小的下标 index = 1 * (3) 2 7 6 8 9 * j //7大不记录 * 3 (2) 7 6 8 9 * 知道j走完了 有小的就用index记录下标 * 3 (2) 7 6 8 9 * 最后把array[index]和array{i}换位置 * (2) 3 7 6 8 9 * @param array * @return */ public static Integer[] selectOrder(Integer[] array){ Integer index,temp; Integer time = array.length - 1; for(int i = 0 ; i < time ; i++){ index = i; for(int j = i+1;j<array.length;j++){ if(array[index] > array[j]){ index = j; } } temp = array[index]; array[index] = array[i]; array[i] = temp; index++; } return array; }

排序算法之希尔排序

    希尔排序是由1959年Shell发明,第一个打破了O(n^2)的魔咒,是简单插入排序的改进版。与插入排序不同的是,希尔排序事先设置好了增量,即把序列按照一定的间隔分组,对每组分别进行插入排序。希尔排序的核心在于间隔序列的设定也就是增量值的设定,一个好的增量序列会给希尔排序带来质的变化。

图解:

描述:这时一个简单的长度为6的数组,动态定义间隔序列,算法为从1不断向上找最大的间隔序列 gap = gap*2 +1 一直向上找直到找到 gap < A.length/2为止。这里gap最大值为3 , 也就是说最多分成三组,两两一组。,我们分别对每组元素进行排序。然后进行下一轮的gap计算分组,这时我们gap = gap /2 ,gap = 1 。整个序列分为一组做一次插入排序这时数组就变的有序了。

源代码:

/** * 希尔排序 传入数组和增量序列倍数 * @param array * @param addNum * @return */ public static Integer[] shellOrder(Integer[] array,Integer addNum){ Integer temp; Integer gap = 1; while(gap < array.length/addNum) { //计算最大的gap值 gap =gap*addNum+1; } while (gap> 0){ // 荡循环,维护gap for (Integer i = gap; i < array.length; i++) { //因gap位之前的元素都是每个组的第一位 temp = array[i]; // 从gap位开始 那么我们就从gap位开始对个元素做插入排序 Integer j; // 可能会问 每个元素所在的组不一样,怎么就插入了 for (j = i-gap; j >= 0 && array[j]> temp; j-=gap) { //正是因为每个元素所在的组不一样 那么我们在对每个元素做插入排序的时候 array[j+gap] = array[j]; //遍历的都是相隔gap位的元素,所以相隔gap位的元素都是一组的 } //做插入排序 array[j+gap] = temp; } gap = (int)Math.floor(gap/addNum); } return array; }

排序算法之归并排序

归并排序是一种采用了分而治之的概念,一变二,二变四,四变八,不断的分治数组,直到数组为1不能再分了之后。返回当前的元素 采用两数组两指针合并的办法,不断的聚合收拢直至数组完成聚合,排序也随之完成。归并排序使用递归的话对程序的开销非常大,尤其是java会造成内存溢出的异常。由于在不断分裂又聚合的过程中开辟了太多数组资源,造成内存溢出。这里可以普及一下jvm内存管理,这里导致内存溢出的原因可能会有两种,一种是堆没有完成实例分配导致报内存溢出异常,另一种是java虚拟机栈无法扩展报内存溢出异常。

图解:

描述:上方图片描述了递归的分解和合并的过程,一分为二,向下取整留给左其余留给右。不断分解直到数组元素为1个时,不继续向下分解改为向上聚合。聚合 两个数组 看作两个栈 两个栈顶元素对比小的出去,不断加入到新数组中。完成聚合此时聚合后的数组是有序的。直到整个数组完成聚合,数组排序成功。

源代码:

/** * 归并排序入口 * 不需要设置其边界值的入口 * @param array * @return */ public static Integer[] defaultRecursionMergeOrder(Integer[] array){ if (array != null) array = Order.recursionMergeOrder(array,0,array.length-1); return array; } /** * 归并排序 * 传入待排序数组,以及待排序的左边界和右边界 * @param array * @param left * @param right * @return */ public static Integer[] recursionMergeOrder(Integer[] array,Integer left,Integer right){ if(left == right) { //如果数组左边界和右边界相同的话就不用继续递归归并了 并返回这个唯一的一个元素的数组 return new Integer[]{ array[right] }; } Integer mid = (right + left) / 2; //如果还可以二分归并那么算出中间值 Integer[] lArray = Order.recursionMergeOrder(array,left,mid); //左的给左 右的给右依次递归 Integer[] rArray = Order.recursionMergeOrder(array,mid+1,right); return leftMergeRight(lArray,rArray); //合并俩数组的值 } /** * 归并排序:和并两个有序数组 * @param leftArray * @param rightArray * @return */ public static Integer[] leftMergeRight(Integer[] leftArray,Integer[] rightArray){ Integer newLength = leftArray.length + rightArray.length; Integer[] newArray = new Integer[newLength]; //申请一个长度为左右数组长度之和的新数组 Integer point = 0,leftPoint = 0,rightPoint = 0; //数组元素比较和记录指针 while (leftPoint < leftArray.length && rightPoint < rightArray.length) { //两个引用分别指向两个数组 从0开始比较大的计入新数组中 新数组指针 比较者大的数组指针+1 newArray[point++] = leftArray[leftPoint] < rightArray[rightPoint] ? leftArray[leftPoint++] : rightArray[rightPoint++]; } //一旦左右数组有一个指针不能继续比较了,那么就对剩下的单个数组进行合并 while (leftPoint < leftArray.length) { //左面数组没合并玩 依次合并入新数组 newArray[point++] = leftArray[leftPoint++]; } while (rightPoint < rightArray.length) { //右边数组没合并完 依次合并入新数组 newArray[point++] = rightArray[rightPoint++]; } return newArray; }

 

总结

    前面讲的五种排序算法应用的场景比较少,我们一般不会使用这些排序算法为一组数据排序,当然还有更为快捷的算法,如快速排序和堆排序,时间复杂度低空间利用率低,排序效果块,都能进行原址排序。详情请见下一篇  易解排序算法 - 中 。

 

 

 

 

 

 

转载请注明原文地址: https://www.6miu.com/read-2800174.html

最新回复(0)