排序算法

  根据时间复杂度的不同，主流的排序算法可以分为三大类：
1 . 时间复杂度为O(n2)的排序算法：
(1) . 冒泡排序；
(2) . 选择排序；
(3) . 插入排序；
(4) . 希尔排序；

2 . 时间复杂度为O(nlogn)的排序算法：
(1) . 快速排序；
(2) . 归并排序；
(3) . 堆排序；

3 . 时间复杂度为线性的排序算法：
(1) . 计数排序；
(2) . 桶排序；
(3) . 基数排序；

  根据稳定性，可以分为稳定排序和不稳定排序：
1 . 稳定排序：如果值相同的元素在排序后仍然保持着排序前的顺序，则这样的排序算法是稳定排序；
2 . 不稳定排序：如果值相同的元素在排序后打乱了排序前的顺序，则这样的排序算法是不稳定排序。

冒泡排序

冒泡排序基础

  冒泡排序是一种基础的交换排序。冒泡排序之所以叫冒泡排序，是因为这种排序算法的每一个元素都可以像小气泡一样，根据自身的大小，一点点地向着数组的一侧移动。
  按照冒泡排序的思想，我们要把相邻的元素两两比较，当一个元素大于右侧相邻元素时，交换他们的位置；当一个元素小于或等于右侧相邻元素时，位置不变。
  如下所示，显示一个数列的冒泡排序的步骤：

原始数列：5 8 6 3 9 2 1 7
第一轮第一次：5 8 6 3 9 2 1 7
第一轮第二次：5 6 8 3 9 2 1 7
第一轮第三次：5 6 3 8 9 2 1 7
第一轮第四次：5 6 3 8 9 2 1 7
第一轮第五次：5 6 3 8 2 9 1 7
第一轮第六次：5 6 3 8 2 1 9 7
第一轮第七次：5 6 3 8 2 1 7 9

  如上面所示，第一轮两两比较结束后，最大值9，就排到了最右侧。接下来重复第一轮的两两比较的操作，只不过第二轮开始从第二个数字开始比较，第三轮从第三个数字开始比较，一次类推，最终会得到最终结果，如下：

1 2 3 5 6 7 8 9

  冒泡排序是一种稳定排序，值相等的元素并不会打乱原本的顺序。由于该排序算法的每一轮都要遍历所有元素，总共遍历（元素数量 - 1）轮，所以平均时间复杂度是O(n2)

  冒泡排序的实现代码如下：

public static void sort(int array[]){
    for(int i = 0;i < array.length - 1;i ++){
        for(int j = 0;i < array.length - i - 1;j ++){
            int temp = 0;
            if(array[j] > array[j + 1]){
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
        System.out.println("进行的第" + i + "轮排序:" + Arrays.toString(array));
    }
}

  在上面的代码中我们使用if(array[j] > array[j + 1])这个作为判断，是把最大值排到数列的末尾，最终得到的是一个升序的数列；如果我们改成if(array[j] < array[j + 1])，就会得到一个降序的数列，就是把最大值排到了数列的开头。

冒泡排序的优化

  在上面的冒泡排序中，其实在第六轮排序中，我们的排序顺序就已经是最终排序了。

原始数列：5 8 6 3 9 2 1 7
最终数列：1 2 3 5 6 7 8 9

  但是，冒泡排序还是继续执行了第七轮排序，因为排序的轮数还没结束。在这种情况下，如果能判断出数列已经有序，并作出标记，那么剩下的几轮排序就不必执行了，可以提前结束排序工作。代码如下：

public static void sortBetter(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        boolean isSorted = true;
        for (int j = 0; j < array.length - i - 1; j++) {
            int temp = 0;
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                isSorted = false;
            }
        }
        if (isSorted) {
            break;
        }
        System.out.println("进行的第" + i + "轮排序:" + Arrays.toString(array));
    }
}

  我们可以比对这两个方法的打印，就可以发现第二个方法比第一个方法少进行了一轮排序。

  到了这里，只是优化冒泡排序的第一步，我们还可以进一步提升冒泡排序的性能。我们使用一种特殊点的数列来举例，如下：

3 4 2 1 5 6 7 8

  可以看到，这个数列的特点是前面的元素是无序的，后面的元素已经是生序排列了。并且后面的元素的最小值也大于前面的元素的最大值。

  按照冒泡排序，会发现数列后面的元素已经有序了，但还是会进行比较，每一轮就白白地比较了好多次。这个问题的关键点在于对数列有序区的界定。按照冒泡排序现有的逻辑，有序区的长度和排序的轮数是相等的。比如第一轮排序后排出最大值，有序区的长度是1；第二轮排序排出最大的两个值，有序区的长度是2；依此类推。实际上，有序区的长度可能会大于现有逻辑下的有序区长度。如上面这个数列，第一轮排序以后，后面的几个元素都已经属于有序区了。因此后面的多次元素比较是没有意义的。
  我们可以在每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序区数列的边界，再往后就是有序区了。

public static void sortMoreBetter(int[] array) {
    for (int i = 0; i < array.length - 1; i++) {
        boolean isSorted = true;
        int sortBorder = array.length - 1;
        for (int j = 0; j < sortBorder; j++) {
            int temp = 0;
            if (array[j] > array[j + 1]) {
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                isSorted = false;
                sortBorder = j;
            }
        }
        if (isSorted) {
            break;
        }
        System.out.println("进行的第" + i + "轮排序:" + Arrays.toString(array));
    }
}

  其实这仍然不是最优的冒泡排序，还有一种排序算法叫做鸡尾酒排序，是基于冒泡排序的一种升级排序法。

  冒泡排序的每一轮都是从左向右来比较元素，进行单向的位置交换的。鸡尾酒排序的元素比较和交换过程是双向的。

  举个例子，如下的数列，希望能对其进行从小到大的排序：

2 3 4 5 6 7 8 1

  其实只要把最后一个值1，拍到第一位，这个数列就排好了顺序，但是如果按照冒泡排序的话，就需要进行好多轮才能排好顺序。

  鸡尾酒排序，就像钟摆一样，第一轮从左向右，第二轮从右向左，第三轮再从左向右，依此类推。

public static void sortCockTail(int[] array){
    int temp = 0;
    for(int i = 0;i < array.length / 2;i ++){
        boolean isSorted = true;
        for(int j = i;j < array.length - i - 1;j ++){
            if(array[j] > array[j + 1]){
                temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                isSorted = false;
            }
        }
        if(isSorted){
            break;
        }

        isSorted = true;
        for(int j = array.length - i - 1;j > i;j --){
            if(array[j] < array[j -1]){
                temp = array[j];
                array[j] = array[j - 1];
                array[j - 1] = temp;
                isSorted = false;
            }
        }
        if(isSorted){
            break;
        }
        System.out.println("进行的第" + i + "轮排序:" + Arrays.toString(array));
    }
}

  上面就是鸡尾酒排序的代码实现。代码外层的大循环控制着所有排序回合，大循环内包含两个小循环，第一个小循环从左向右比较并交换元素，第二个小循环内从右向左比较并交换元素。

  鸡尾酒排序的优点是能够在特定条件下，减少排序的回合数。这种排序方法能发挥出优势的场景就是大部分元素已经有序的情况。

快速排序

快速排序基础

  快速排序是从冒泡排序演变而来的，同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达成排序的目的。
  不同的是，冒泡排序在每一轮只把一个元素冒泡到数列的一端。而快速排序则是在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列的一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。这种思路叫做分治法。

  比如给出一个八个元素的数列，一般情况下，使用冒泡排序需要比较七轮，每一轮把一个元素移动到数列的一端，时间复杂度是O(n2)。
  在分治法的思路下，原数列在每一轮都被拆分成两部分，每一部分在下一轮又分别拆分成两部分，直到不可再分为止。每一轮的比较和交换，需要把数组全部元素都遍历一遍，时间复杂度是O(n)。假如元素个数是n，那么平均情况下需要logn轮，因此快速排序算法总体的平均时间复杂度是O(nlogn)。

  基准元素的选择，以及元素的交换，都是快速排序的核心问题。

基准元素的选择

  在分治过程中，以基准元素为中心，把其他元素移动到它的左右两边。
  如果把第一个元素作为基准元素，在遇到一个原本逆序的数列，在这种极端情况下，快速排序需要进行n轮，时间复杂度退化成了O(n2)。
  所以，我们随机选择一个元素作为基准元素，并且让基准元素和数列首元素交换位置。这样，即使在数列完全逆序的情况下，也可以有效地将数列分成两部分。当然，即使是随机选择基准元素，也会有极小的几率选到数列的最大值或者最小值，同样会影响分治的效果。
  所以，虽然快速排序的平均时间复杂度是O(nlogn)，但最坏的情况下的时间复杂度是O(n2)

元素的交换

  选定了基准元素以后，我们要做的就是把其他元素中小于基准元素的都交换到基准元素一边，大于基准元素的都交换到基准元素的另一边。
  有两种方法可以实现：
1 . 双边循环法；
2 . 单边循环法；

堆排序

  二叉堆的特性：
1 . 最大堆的堆顶是整个堆中的最大元素；
2 . 最小堆的堆顶是整个堆中的最小元素；

  二叉堆的节点“下沉”调整是堆排序算法的基础，这个调节操作的时间复杂度是O(logn)。

  堆排序的步骤如下：
1 . 把无序数组构建成一个二叉堆。需要从小到大排序，则构建成最大堆；需要从大到小排序，则构建成最小堆；
2 . 循环删除堆顶的元素，替换到二叉堆的末尾，调整堆产生新的堆顶；
  第一步，把无序数组构建成二叉堆，这一步的时间复杂度是O(n)；
  第二步，需要进行n - 1次循环。每次循环调用一次“下沉”调整方，所以第二步的计算规模是(n - 1) * logn，时间复杂度是O(nlogn)。
  堆排序的整体的时间复杂度是O(nlogn)。

  快速排序和堆排序的相同点：两者的平均时间复杂度都是O(nlogn)，并且都是不稳定排序。
  快速排序和堆排序的不同点：快速排序的最坏的时间复杂度是O(n2)，堆排序的最坏的时间复杂度稳定在O(nlogn)。快速排序递归和快速排序非递归方法的平均空间复杂度都是O(logn)，堆排序的空间复杂度是O(1)。

计数排序和桶排序

  前面的冒泡排序、快速排序、堆排序都是基于元素之间的比较来进行排序的。有一些特殊的排序并不基于元素比较，如计数排序、桶排序、基数排序。

计数排序基础

  假设一个数组中有20个随机整数，取值范围是0～10，要求用最快的速度把这20个整数从小到大进行排序。考虑到这些整数只能够在0～10这十一个整数中取值，取值范围有限。所以，我们可以根据有限的取值范围，建立一个长度为11的数组。数组下标从0到10，元素初始值全为0。

0 0 0 0 0 0 0 0 0 0 0

  假设20个随机整数的值如下：

9 3 5 4 9 1 2 7 8 1 3 6 5 3 4 0 10 9 7 9

  下面就开始遍历这个无序的随机数列，每一个整数按照其值对号入座。同时，对应数组的下标的元素进行加1的操作。
  例如第一个整数为9，就在数组下标为9的元素加1；第二个整数位3，就在数组下标为3的元素加1；依此类推。最终，当数组遍历完成时，数组的状态如下：

1 2 1 3 2 2 1 2 1 4 1

  该数组中每一个下标位置的值代表了数列中对应整数出现的次数。有个这个统计结果，直接遍历数组，输出数组元素的下标值，元素的值是几，就输出几次。

0 1 1 2 3 3 3 4 4 5 5 6 7 7 8 9 9 9 9 10

  这就是计数排序的基本过程，它适用于一定范围内的整数排序。在取值范围不是很大的情况下，它的性能甚至快过那些时间复杂度为O(nlogn)的排序。

public static int[] countSort(int[] array) {
    //得到数列的最大值;
    int max = array[0];
    for (int i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    int[] countArray = new int[max + 1];
    for (int i = 0; i < array.length; i++) {
        countArray[array[i]]++;
    }
    int index = 0;
    int[] sortedArray = new int[array.length];
    for (int i = 0; i < countArray.length; i++) {
        for (int j = 0; j < countArray[i]; j++) {
            sortedArray[index++] = i;
        }
    }
    return sortedArray;
}

  上面代码最开头有一个步骤，就是求数列的最大整数值max。后面创建的统计数组countArray，长度是max + 1，以此来保证数组的最后一个下标是max。

计数排序的优化

  如果我们给一个数列排序，如下：

95 94 91 98 99 90 99 93 91 92

  这个数列的最大值是99，最小的整数是90。如果创建长度为100的数组，那么前面从0到89的空间位置就浪费了。
  解决空间浪费的问题，只要不再以输入数列的最大值 + 1作为统计数组的长度，而是以数列最大值 - 最小值 + 1作为统计数组的长度即可。同时，数列的最小值作为一个偏移量，用于计算整数在统计数组中的下标。

  以刚才的数列为例，统计出数组的长度为99 - 90 + 1 = 10，偏移量等于数列的最小值90。对于第一个整数95，对应的统计数组的下标是95 - 90 = 5。那么数列最终统计结果，如下图所示：

1 2 1 1 1 1 0 0 1 2

  也就是:

90 91 91 92 93 94 95 98 99 99

  当数列最大值和最小值差距巨大时，并不适合用计数排序；
  当数列元素不是整数时，也不适合用计数排序；

桶排序

  桶排序同样是一种线性时间的排序算法。类似于计数排序所创建的统计数组，桶排序需要创建若干个桶来协助排序。

总结

排序算法 平均时间复杂度 最坏时间复杂度 空间复杂度 是否稳定排序
冒泡排序 O(n2) O(n2) O(1) 稳定
鸡尾酒排序 O(n2) O(n2) O(1) 稳定
快速排序 O(nlogn) O(n2) O(logn) 不稳定
堆排序 O(nlogn) O(nlogn) O(1) 不稳定
计数排序 O(n + m) O(n + m) O(m) 稳定
桶排序 O(n) O(nlogn) O(n) 稳定


« SecureCRT工具使用
建造者模式 »

Copyright © 2015 Powered by MWeb,  Theme used GitHub CSS.

TOP