vlambda博客
学习文章列表

java常见排序算法--选择排序、冒泡排序、插入排序分析与比较


0 1
选择排序


核心思想:依次拿当前元素和其后面的元素比较大小,满足条件就互换值。

代码:

public static int[] shunxu(int[] arr){ int len = arr.length; int temp = 0;  for (int i = 0; i < len-1; i++) { for (int j = i+1; j < len; j++) { if(arr[i] > arr[j]){ temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } } return arr;}

解读:

        arr[i]是当前元素,范围是[0,arr.length-1);arr[j]是当前元素后面的元素,范围是[i+1,arr.length)

时间复杂度:

        最好的情况是所有数字都是有序的,对于n位的数组,时间复杂度为O(n);

        最坏的情况是把顺序的排列变成逆序,或者把逆序的数列变成顺序。在这种情况下,每一次比较都需要进行交换运算。对于n位的数组,则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2,这就得到了最大的比较次数。所以时间复杂度为o(n(n-1)/2);


0 2
冒泡排序


核心思想:依次拿相邻的元素做比较,满足条件就互换值。每轮比较找到一个最值(最大或者最小),把其放到末尾。

代码:

public static int[] maopao(int[] arr){ int len = arr.length; int temp = 0;  for (int i = 0; i < len-1; i++) { for (int j = 0; j < len-1-i; j++) { if(arr[j] > arr[j+1]){ temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } return arr;}

解读:

      外层for循环表示比较轮数,范围是[0,arr.length-1),总共比较了length-1轮;内层for循环表示第 i 轮比较的次数,范围是[0,arr.length-1-i);

      每一轮都会产生一个最值(最大值或最小值),则下一轮就少比较一次;外层for循环控制比较的总轮数,该循环是以内层for循环的变量 j 作为数组的下标进行比较;


时间复杂度:

        最好的情况同选择排序,即所有数字都是有序的,对于n位的数组,时间复杂度为O(n);

        最坏的情况同选择排序,是把顺序的排列变成逆序,或者把逆序的数列变成顺序。在这种情况下,每一次比较都需要进行交换运算。对于n位的数组,则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2,这就得到了最大的比较次数。所有时间复杂度为o(n(n-1)/2)


0 3
插入排序


核心思想:假设前面的数字是有序的,依次拿当前元素与前面元素做比较,满足条件就互换值。

代码:

public static int[] charu(int[] arr){ int len = arr.length; int temp = 0;  for (int i = 1; i < len; i++) { for (int j = i; j > 0; j--) { if(arr[j] > arr[j-1]){ temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; }else{ break; } } } return arr;}

解读:

        外层for循环控制轮数,范围是[1,arr.length);从第2个数字开始,与前面的数字比较,满足条件就互换值,否则就放到当前位置(代码中有break)

时间复杂度:

        最好的情况跟上面的相同,是所有数字都是有序的,对于n位的数组,时间复杂度为O(n);

        最坏的情况跟上面的相同,是把顺序的排列变成逆序,或者把逆序的数列变成顺序。在这种情况下,每一次比较都需要进行交换运算。对于n位的数组,则有比较次数为 (n-1) + (n-2) + ... + 1 = n * (n - 1) / 2,这就得到了最大的比较次数。所有时间复杂度为o(n(n-1)/2)


0 4
三种排序算法对比

        

        根据时间复杂度来比较,三种排序算法的最好和最坏的值都是相同的。所以,我们无法从时间复杂度上面来对比他们。

        我们可以从代码上面分析,由于插入排序代码里有一个break,以至于不满足条件的时候,直接中断内层for循环的执行。所以,相对于其它算法,它的比较次数相应的会少很多,所以效率会更快。

        综合考虑的情况下,插入排序>=冒泡排序>=选择排序。


0 5
与其它排序对比