写点什么

JAVA 九种排序算法详解(下)

用户头像
加百利
关注
发布于: 2021 年 07 月 06 日
JAVA 九种排序算法详解(下)

八、快速排序:

1.基本思想:

选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素,此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

2.实现过程:

  • 原数组值:

  • 32 , 43, 23, 13, 5

  • 第一轮比较:选择第一个数为 p,小于 p 的数放在左边,大于 p 的数放在右边,结果如下:


​ 32 , 13, 5, 32, 43


​ 如图所示:


  • 第二轮比较:递归的将 p 左边和右边的数都按照第一步进行,直到不能递归,结果如下:

  • 13 , 5, 23, 32, 43

  • 如图所示:



  • 第三轮比较:递归的将 p 左边和右边的数都按照第一步进行,直到不能递归,结果如下:

  • 5 , 13, 23, 32, 43

  • 如图所示:



  • 3.实现代码:

    package cn.hz.demo2;
    /** * @author hz * @version 1.0 * * 快速排序 * 需求分析: * 选择第一个数为p,小于p的数放在左边,大于p的数放在右边。 * 递归的将p左边和右边的数都按照第一步进行,直到不能递归。 * */public class Demo8 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1}; //定义需要排序数组 System.out.println("快速排序前"); for (int ia:a){ System.out.print(ia+"t"); } //快速排序 quickSort(a,0,a.length-1); System.out.println("n快速排序后"); for (int ia:a){ System.out.print(ia+"t"); }
    } public static void quickSort(int[] numbers, int start, int end) { if (start < end) { int base = numbers[start]; // 选定的基准值(第一个数值作为基准值) int temp; // 记录临时中间值 int i = start, j = end; do { while ((numbers[i] < base) && (i < end)) i++; while ((numbers[j] > base) && (j > start)) j--; if (i <= j) { temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; i++; j--; } } while (i <= j); if (start < j) quickSort(numbers, start, j); if (end > i) quickSort(numbers, i, end); } }}
    复制代码


    实现效果:



    4.分析:

    快速排序是不稳定的排序。


    快速排序的时间复杂度为 O(nlogn)。


    当 n 较大时使用快排比较好,当序列基本有序时用快排反而不好。

    5.稳定性总结:

    快速排序有两个方向,左边的 i 下标一直往右走(当条件 a[i] <= a[center_index]时),其中 center_index 是中枢元素的数组下标,一般取为数组第 0 个元素。


    而右边的 j 下标一直往左走(当 a[j] > a[center_index]时)。


    如果 i 和 j 都走不动了,i <= j, 交换 a[i]和 a[j],重复上面的过程,直到 i>j。交换 a[j]和 a[center_index],完成一趟快速排序。


    在中枢元素和 a[j]交换的时候,很有可能把前面的元素的稳定性打乱,比如序列为 5 3 3 4 3 8 9 10 11


    现在中枢元素 5 和 3(第 5 个元素,下标从 1 开始计)交换就会把元素 3 的稳定性打乱。


    所以快速排序是一个不稳定的排序算法,不稳定发生在中枢元素和 a[j]交换的时刻。

    九、归并排序:

    1.基本思想:

    归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

    2.实现过程:

    • 原数组值:

    • 32 , 43, 23, 13, 5

    • 第一轮比较:选择相邻两个数组成一个有序序列,结果如下:

    • 32 , 43, 13, 23, 5

    • 如图所示:



    • 第二轮比较:选择相邻的两个有序序列组成一个有序序列,结果如下:

    • 13, 23, 32, 43, 5

    • 如图所示:



    • 第三轮比较:选择相邻的两个有序序列组成一个有序序列,结果如下:

    • ​ 5, 13, 23, 32, 43,

    • 如图所示:



  • 3.实现代码:

    package cn.hz.demo2;
    /** * @author hz * @version 1.0 * * 归并排序 * 需求分析: * 选择相邻两个数组成一个有序序列。 * 选择相邻的两个有序序列组成一个有序序列。 * 重复第二步,直到全部组成一个有序序列。 */public class Demo9 { public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println("归并排序之前:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } //归并排序 mergeSort(a,0,a.length-1); System.out.println(); System.out.println("排序之后:"); for (int i = 0; i < a.length; i++) { System.out.print(a[i]+" "); } } private static void mergeSort(int[] a, int left, int right) { if(left<right){ int middle = (left+right)/2; //对左边进行递归 mergeSort(a, left, middle); //对右边进行递归 mergeSort(a, middle+1, right); //合并 merge(a,left,middle,right); } }
    private static void merge(int[] a, int left, int middle, int right) { int[] tmpArr = new int[a.length]; int mid = middle+1; //右边的起始位置 int tmp = left; int third = left; while(left<=middle && mid<=right){ //从两个数组中选取较小的数放入中间数组 if(a[left]<=a[mid]){ tmpArr[third++] = a[left++]; }else{ tmpArr[third++] = a[mid++]; } } //将剩余的部分放入中间数组 while(left<=middle){ tmpArr[third++] = a[left++]; } while(mid<=right){ tmpArr[third++] = a[mid++]; } //将中间数组复制回原数组 while(tmp<=right){ a[tmp] = tmpArr[tmp++]; } }}
    复制代码


    实现效果:



    4.分析:

    归并排序是稳定的排序方法。


    归并排序的时间复杂度为 O(nlogn)。


    速度仅次于快速排序,为稳定排序算法,一般用于对总体无序,但是各子项相对有序的数列

    5.稳定性总结:

    归并排序是把序列递归地分成短序列,递归出口是短序列只有 1 个元素(认为直接有序)或者 2 个序列(1 次比较和交换),


    然后把各个有序的段序列合并成一个有序的长序列,不断合并直到原序列全部排好序。


    可以发现,在 1 个或 2 个元素时,1 个元素不会交换,2 个元素如果大小相等也没有人故意交换,这不会破坏稳定性。


    那么,在短的有序序列合并的过程中,稳定是是否受到破坏?


    没有,合并过程中我们可以保证如果两个当前元素相等时,我们把处在前面的序列的元素保存在结果序列的前面,这样就保证了稳定性。


    所以,归并排序也是稳定的排序算法。

    十、基数排序:

    1.基本思想:

    将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。

    2.实现过程:

    该排序方式比较麻烦,换一个值较多的数组进行讲解:


    • 原数组值:

    • 135, 242, 192, 93, 345, 11, 24, 19

    • 第一轮比较:将所有的数的个位数取出,按照个位数进行排序,构成一个序列,结果如下:

    • 11, 242, 192, 93, 24, 135, 345, 19

    • 如图所示:



    • 第二轮比较:将新构成的所有的数的十位数取出,按照十位数进行排序,构成一个序列,结果如下:

    • 11, 19, 24, 135, 242,345, 192, 93

    • 如图所示:



    • 第三轮比较:将新构成的所有的数的百位数取出,按照百位数进行排序,构成一个序列,结果如下:

    • 11, 19, 24, 93, 135, 192, 242, 345

    • 如图所示:


    3.实现代码:

    package cn.hz.demo2;
    import java.util.ArrayList;import java.util.List;
    /** * @author hz * @version 1.0 * * 基数排序 * 需求分析: * 将所有的数的个位数取出,按照个位数进行排序,构成一个序列。 * 将新构成的所有的数的十位数取出,按照十位数进行排序,构成一个序列。 */public class Demo10 { public static void main(String[] args) { int[] array={49,38,65,97,76,13,27,49,78,34,12,64,1,8}; System.out.println("基数排序之前:"); for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); } //基数排序 //首先确定排序的趟数; int max = array[0]; for (int i = 1; i < array.length; i++) { if (array[i] > max) { max = array[i]; } } int time = 0; //判断位数; while (max > 0) { max /= 10; time++; } //建立10个队列; List<ArrayList> queue = new ArrayList<ArrayList>(); for (int i = 0; i < 10; i++) { ArrayList<Integer> queue1 = new ArrayList<Integer>(); queue.add(queue1); } //进行time次分配和收集; for (int i = 0; i < time; i++) { //分配数组元素; for (int j = 0; j < array.length; j++) { //得到数字的第time+1位数; int x = array[j] % (int) Math.pow(10, i + 1) / (int) Math.pow(10, i); ArrayList<Integer> queue2 = queue.get(x); queue2.add(array[j]); queue.set(x, queue2); } int count = 0;//元素计数器; //收集队列元素; for (int k = 0; k < 10; k++) { while (queue.get(k).size() > 0) { ArrayList<Integer> queue3 = queue.get(k); array[count] = queue3.get(0); queue3.remove(0); count++; } } }
    System.out.println("n基数排序之后:"); for (int i = 0; i < array.length; i++) { System.out.print(array[i]+" "); }

    }}
    复制代码


    实现效果:



    4.分析:

    基数排序是稳定的排序算法。


    基数排序的时间复杂度为 O(d(n+r)),d 为位数,r 为基数。

    5.稳定性总结:

    基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。


    有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序,最后的次序结果就是高优先级高的在前,高优先级相同的情况下低优先级高的在前。


    基数排序基于分别排序,分别收集,所以其是稳定的排序算法。

    总结:

    1.稳定性:

    • 稳定:冒泡排序、插入排序、归并排序和基数排序

    • 不稳定:选择排序、快速排序、希尔排序、堆排序

    2.平均时间复杂度

    O(n^2):直接插入排序,简单选择排序,冒泡排序。


    在数据规模较小时(9W 内),直接插入排序,简单选择排序差不多。当数据较大时,冒泡排序算法的时间代价最高。性能为 O(n^2)的算法基本上是相邻元素进行比较,基本上都是稳定的。


    O(nlogn):快速排序,归并排序,希尔排序,堆排序。


    其中,快排是最好的, 其次是归并和希尔,堆排序在数据量很大时效果明显。

    3.排序算法的选择:

    规模较小:


    • 待排序列基本序的情况下,可以选择直接插入排序

    • 对稳定性不作要求宜用简单选择排序,对稳定性有要求宜用插入或冒泡


    数据规模不是很大:


    • 完全可以用内存空间,序列杂乱无序,对稳定性没有要求,快速排序,此时要付出 log(N)的额外空间。

    • 序列本身可能有序,对稳定性有要求,空间允许下,宜用归并排序


    数据规模很大:


    • 对稳定性有求,则可考虑归并排序

    • 对稳定性没要求,宜用堆排序


    序列初始基本有序(正序),宜用直接插入,冒泡

    用户头像

    加百利

    关注

    还未添加个人签名 2021.06.08 加入

    还未添加个人简介

    评论

    发布
    暂无评论
    JAVA 九种排序算法详解(下)