排序的几种算法

前言

排序算法是将一组数据按照一定的顺序排列的算法。这里列举几种常见的排序算法：

冒泡排序（Bubble Sort）

  • 通过依次比较相邻的两个元素，如果它们的顺序不正确就交换它们，一轮比较下来最大（或最小）的元素就像气泡一样”浮”到了最上面（或最下面），因此称为冒泡排序。
  • 时间复杂度：平均情况和最坏情况均为 O(n^2)。
1
2
3
4
5
6
def BUBsort(buf):
    length = len(buf)
    for j in range(length):
        for i in range(length-j-1):
            if(int(buf[i])>int(buf[i+1])):
                buf[i],buf[i+1] = buf[i+1],buf[i]

可以发现需要进行两次遍历，时间复杂度就为O(n^2)

选择排序（Selection Sort）

  • 在未排序序列中选择最小（或最大）的元素，将其放置到已排序序列的末尾，直到所有元素均排序完毕。
  • 时间复杂度：平均情况和最坏情况均为 O(n^2)。
1
2
3
4
5
6
7
8
9
10
11
def SELsort(buf):
    length = len(buf)
    for i in range(length-1,0,-1):
    #i 从最后一个开始
        max_index = 0
        #从第一个到最后一个进行比较，找出最大的一个
        for j in range(i+1):
            if(int(buf[j])>int(buf[max_index])):
                max_index = j
        #交换
        buf[i],buf[max_index] = buf[max_index], buf[i]

可以发现需要进行两次遍历，时间复杂度就为O(n^2)

插入排序（Insertion Sort）

  • 将未排序序列的第一个元素插入到已排序序列中的正确位置，然后将下一个未排序元素插入到已排序序列中，依次类推，直到所有元素均排序完毕。
  • 时间复杂度：平均情况和最坏情况均为 O(n^2)。
1
2
3
4
5
6
7
8
9
10
11
12
13
def INSsort(buf):
    length = len(buf)
    sorted_buf=[]
    sorted_buf.append(buf[0])
    for i in range(1,length):
        midel_index=len(sorted_buf)
        for j in range(len(sorted_buf)-1,-1,-1):
            if(int(buf[i])<int(sorted_buf[j])):
                midel_index=j
            else:
                break
        sorted_buf.insert(midel_index,buf[i])
    return sorted_buf

快速排序（Quick Sort）

  • 选择一个基准元素，将数组分为两个子数组，小于基准元素的放在左边，大于基准元素的放在右边，然后对子数组进行递归排序。
  • 时间复杂度：平均情况下为 O(nlogn)，最坏情况下为 O(n^2)。

归并排序（Merge Sort）

  • 将数组分成两个子数组，分别对两个子数组进行递归排序，然后将排好序的子数组合并成一个新的有序数组。
  • 时间复杂度：平均情况和最坏情况均为 O(nlogn)。

堆排序（Heap Sort）

  • 将数组构建成一个最大堆（或最小堆），然后将堆顶元素与最后一个元素交换并移除，然后重新调整堆，重复这个过程直到所有元素都排好序。
  • 时间复杂度：平均情况和最坏情况均为 O(nlogn)。

总结

这些是排序算法中的一些经典方法，每种排序算法都有自己的优劣和适用场景。在实际应用中，选择合适的排序算法往往需要考虑到数据规模、数据特点、时间复杂度等因素。