几种常见的排序算法


排序算法概述

常见的排序算法整体上可以分为两大类,比较类排序和非比较类排序,如下所示:

下表是不同排序算法的复杂度对比

相关的一些概念:

  • 稳定/不稳定,如果 a=b,并且 a 在 b 之前,排序后能保证 a b 顺序不会变化就是稳定排序,如果有可能造成 a b 顺序互换就是不稳定排序
  • 时间复杂度,对排序数据的总的操作次数。反映当 n 变化时,操作次数呈现什么规律。
  • 空间复杂度:是指算法在计算机内执行时所需存储空间的度量,它也是数据规模 n 的函数。

冒泡排序

两个数比较大小,较大的数下沉,较小的数冒起来。

排序过程:

  • 从后向前进行冒泡,第1次遍历即可将最小的元素移至第一位
  • 重复上面的步骤对剩余的 n-1 个元素进行冒泡,得到第二小的元素放在第二位
  • 以此类推直到最后一个元素排序完成

注意也可以从前向后将最大的值先移至最后一位,道理相同!

Java 示例

public static void maopaoSort(int[] arr){
    int temp;
    for (int i = 0; i < arr.length-1; i++) { //因为是两两比较,所以一共冒泡 n-1 趟
        for (int j = arr.length-1; j > i; j--) { //从最后一个元素开始冒,冒到上次已经排好序的位置 i 即可
            if (arr[j] < arr[j-1]){
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

动图演示

快速排序

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

排序算法不稳定,是冒泡排序的一种改进,由于从两端向中间比较,且每次移动的距离较远,因此可以减少移动次数,所以比较快; 时间复杂度为 O(n*log2(n)), 由于使用递归方法,因此需要一个 O(log2(n)) 的栈空间。

Java 示例代码

public static void quickSort(int a[], int low, int high) {  // 这里其实 low = 0;high = r.length-1; 但是后面要用递归,需要指定不同的边界
    int i, j, temp;   //temp 用于保存基准元素
    if(low < high) {   // 这里确保待比较的元素个数大于 1
        i = low;
        j = high;
        temp = a[i];  // 令第一个数据为基准
        while(i<j) {
            while(i<j && a[j]>=temp) j--; // 从数组的右端向左依次和基准比较,直到遇到小于基准的数或者比较完依然没遇到。
                          // 注意,相等的时候也要换过去,这也造成快排不具有稳定性
            if(i<j){    // 如果在没比较完之前遇到,则:
                a[i] = a[j]; i++;  // 右侧较小的数挪到数组左侧去,注意这里不用交换,因为基准数已经保存在变量 temp 里了
            }
            while(i<j&&a[i]<=temp) i++; // 然后又从左侧向右开始和基准比较
            if(i<j){a[j] = a[i]; j--;   // 直到遇到大于基准的数,将其挪到数组右侧去
            }
        }
        a[i] = temp; // 直到 i 和 j 相遇时第一圈比完,这个位置就应该是基准在数组排序中的位置,且此时 i=j
        if(low < i-1) quickSort(a,low,i-1); // 最后对基准左侧和右侧的数据不断重复上述过程
        if(high > j+1) quickSort(a,j+1,high); // 注意 if 里的判断条件, 因为此时 r[i] or r[j] 已经不需要再比较
    }

}

动图演示

简单选择排序

选择排序的算法思想很简单,先找出最小的数放在左侧第一位,再从剩下 n-1 个数中找到最小的数放在左侧第二位,以此类推;该排序法不稳定 (例如序列 5 8 5 2 9,第一次选择后第一个 5 会被交换到第二个 5 之后);时间复杂度 O(n^2) 。

看上去和冒泡差不多,只不过比较的过程中只记录最小记录的下标,每趟比完后再将找到的最小元素交换到有序队列的队尾。

Java 示例代码

public static void selectSort(int a[]){
    int i, j, minIndex, temp;  
    for(i=0; i<a.length; i++){
        minIndex = i;
        for(j=i+1; j<a.length; j++){
            if(a[j] < a[minIndex]){
                minIndex = j;
            }
        }
        temp = a[i];
        a[i] = a[minIndex];
        a[minIndex] = temp;
    }
}

堆排序

堆排序也是一种选择排序,是利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

动图示意

直接插入排序法

将待排序的记录逐个插入到已经排好序的序列的适当位置,直到全部插入完为止。一般认为第一个值已排好序,从第二个值开始向其中插入;时间复杂度 O(n^2);空间复杂度 O(1),因为只使用了一个 temp 临时变量的辅助空间。

  • 从第一个元素开始,该元素可以认为已经被排序;
  • 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  • 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  • 将新元素插入到该位置后;
  • 重复步骤2-5

Java 示例代码

public static void insertSort(int a[]){
    int i,j,temp;
    for(i=1; i<a.length; i++){
        j=i-1;
        temp = a[i];  // 这里必须用一个临时变量存储 arr[i], 因为后面的 while 会改变其值
        while(j>=0 && a[j]>temp) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

动图演示

希尔排序

1959 年 Shell 发明,第一个突破 O(n2) 的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

归并排序是一种稳定的排序方法。和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是O(nlogn)的时间复杂度。代价是需要额外的内存空间。

  • 把长度为n的输入序列分成两个长度为n/2的子序列;
  • 对这两个子序列分别采用归并排序;
  • 将两个排序好的子序列合并成一个最终的排序序列。

先掌握不同排序算法的思想,代码实现还需要一个熟练的过程!

总结

除了选择排序多一个最小下标的辅助参量 minIndex,其他排序都是用到 i, j, temp 这三个辅助量;很容易理解选择排序和冒泡排序都是两重循环,而插入排序则使用 while 为待插入元素腾位置,快速排序则要用递归;其中选择排序和快速排序不稳定,而冒泡和插入则是稳定排序。

参考

Copyright © jverson.com 2019 all right reserved,powered by Gitbook 17:54:24

results matching ""

    No results matching ""