算法之排序

小灰灰 2022-04-18 06:28 82阅读 0赞

排序算法是一种非常基础也非常重要的算法。

要选择合适的排序算法为自己的程序做优化，那么就需要了解不同算法优劣的衡量依据。

# 衡量排序算法的依据 #

1.  执行效率  
    1.1 最好时间复杂度、最坏时间复杂度、平均时间复杂度  
    1.2 在数据规模不大时，低阶、系数、常量也需要考虑  
    1.3 时间复杂度相同，需要考虑比较与交换次数
2.  空间消耗  
    使用空间复杂度判断，原位排序的时间复杂度为O(1)
3.  稳定性  
    排序算法的稳定性：相同的数在排序之后，相对位置保持不变则为稳定的排序。

接下来分别对不同常用的排序算法做简单介绍。

# 冒泡排序 #

*  最好时间复杂度：O(n)
 *  最坏、平均时间复杂度：O(n^2)
 *  空间复杂度：O(1)
 *  稳定排序
 *  python实现：

def main():
            s_raw = input()
            s = s_raw.split(",")
            s = [int(x) for x in s]
            for j in range(len(s)-1):
                    for i in range(len(s)-1-j):
                            if s[i] > s[i+1]:
                                    tmp = s[i]
                                    s[i] = s[i+1]
                                    s[i+1] = tmp
            print(s)
    
    main()

# 插入排序 #

*  最好时间复杂度：O(n)
 *  最坏、平均时间复杂度：O(n^2)
 *  空间复杂度：O(1)
 *  稳定排序
 *  Python实现：

def main():
            s_raw = input()
            s = s_raw.split(",")
            s = [int(x) for x in s]
            for j in range(1,len(s)):
                    tmp = s[j]
                    i = j-1
                    while i >= 0:
                            if s[i] > tmp:
                                    s[i+1] = s[i]
                                    i = i - 1
                            else:
                                    break
                    s[i+1] = tmp
    
            print(s)
    
    main()

# 选择排序 #

*  最好、最坏、平均时间复杂度：O(n^2)
 *  空间复杂度：O(1)
 *  不稳定排序
 *  Python实现：

def main():
            s_raw = input()
            s = s_raw.split(",")
            s = [int(x) for x in s]
            for i in range(len(s)):
                    min_value = s[i]
                    min_index = i
                    for j in range(i, len(s)):
                            if min_value > s[j]:
                                    min_value = s[j]
                                    min_index = j
                    s[i], s[min_index] = s[min_index], s[i]
    
            print(s)
    
    main()

# 冒泡排序与插入排序对比 #

冒泡排序中数据的交换操作：
    if (a[j] > a[j+1]) {  // 交换
       int tmp = a[j];
       a[j] = a[j+1];
       a[j+1] = tmp;
       flag = true;
    }
    
    插入排序中数据的移动操作：
    if (a[j] > value) { 
      a[j+1] = a[j]; // 数据移动
    } else { 
      break;
    }

冒泡排序与插入排序的时间复杂度、空间复杂度、稳定性都是相同的。

不过，冒泡排序每次交换数据的语句要比插入排序复杂一些，所以，在时间上来说，插入排序是要比冒泡排序快一些的。

# 归并排序 #

*  最好、最坏、平均时间复杂度：O(nlogn)
 *  空间复杂度：O(n)
 *  稳定排序

# 快速排序 #

*  最好时间复杂度、平均时间复杂度：O(nlogn)
 *  最坏时间复杂度：O(n^2)
 *  空间复杂度：O(1)
 *  非稳定排序

# 桶排序 #

*  适用场景：  
    要排序的数据需要很容易就能划分为m个桶，并且，桶与桶之间有着天然的大小顺序，这样每个桶内的数据都排序之后，桶与桶之间的数据就不需要再进行排序。
 *  比如：  
    有10GB的订单数据，希望按订单金额进行排序，但是内存有限，只有几百MB，这个时候就可以使用桶排序了。先将订单金额划分为多个天然的有序的桶，然后分桶进行排序。

# 计数排序 #

计数排序是桶排序的特殊用法。

*  适用场景：  
    适用于数据范围有限且数据量大于数据范围的场景。
 *  比如：  
    高考的分数排名，数据范围为0到750，划为751个桶之后，遍历分数，将对应的分数放入对应的桶内。

# 基数排序 #

适用可以进行分别排序的数据。

*  比如：  
    对大量的手机11位手机号码进行排序。  
    可以先排序最后一位，然后排序倒数第二位，直到排序第一位。  
    每次排序的数据的范围要有限，这样可以使用桶排序，才能达到线性排序的时间复杂度。

这三种排序算法都是线性排序算法，也就是说，时间复杂度都为O(n)。

接下来看一下C语言中实现的排序：

# C语言中的qsort() #

C语言中的qsort()在数据量很少的情况下使用的是归并排序，数据量比较大的时候使用快速排序。在快速排序中，当区间元素的个数小于等于4时，qsort()会退化为插入排序。

首先，因为归并排序在各种情况下的时间复杂度均为O(nlogn)，所以在数据量不大的情况下使用归并是最合适的，因为现在计算机内存已经不是特别的小了，在内存够用的情况下，我们经常更在意执行的效率。

假如数据量很大的情况下，毕竟归并排序的空间复杂度为O(n)，所以当数据量很大情况下会使得占用的空间翻倍，就要在意内存的使用了。那么此时会使用快速排序来替代归并排序。