内部排序算法

内部排序

插入类排序
- 直接插入排序
- 折半插入排序
- 希尔排序/缩小增量排序
交换类排序
- 冒泡排序
- 快速排序
选择类排序
- 简单选择排序
- 堆排序

稳定性

待排序序列中有两个或两个以上相同的关键字时，排序前和排序后这些关键字的相对位置如果没有发生变化就是稳定的，否则就是不稳定的。

测试用序列
nums=[49,38,65,97,76,13,27,49]

插入类排序

直接插入排序

时间
+ 最差的情况下，即序列倒序，每次插入一个元素，都要与已排序好每个元素进行比较，每比较一次就移动一次，时间复杂度为O(n^2)
+ 最好的情况下即原序列有序，需要比较n次，时间复杂度为O(n)，所以此算法适合序列基本有序的情况
空间
O(1)
稳定性
稳定
注意
一趟排序并不能保证保证一个关键字到达其最终位置，这是插入类排序算法的共同特点
实现

def InsertSort(nums):
    n = len(nums)
    if n < 2:
        return nums
    for i in range(1, n):
        while i > 0:
            if nums[i] < nums[i - 1]:
                nums[i - 1], nums[i] = nums[i], nums[i - 1]
                i -= 1
            else:
                break
    return nums
print(InsertSort(nums))

折半插入排序

寻找插入位置较直接插入排序大大减少，但移动次数是一样的。所以此算法适合关键字比较多的序列

时间复杂度
空间复杂度
O(1)
稳定性
稳定
算法分析
- 从第i个数字（nums[i],i>=2）开始，需要寻找其插入位置，令low,high=0，i-1,即从[0，i-1]查找nums[i]需要插入的位置，分两种情况：
  1. nums[i]没有出现在nums[0:i]中，此时，一定会发生high 对于nums[loc:i]应该全部向后移动一个位置，最后将待插入数字放置到nums[loc]位置
  2. nums[i]已经出现在nums[0:i]中，此时，必然有nums[i]=nums[mid]，此时,令loc=mid+1,
    对于nums[loc:i]应该全部向后移动一个位置，最后将待插入数字放置到nums[loc]位置
实现

def Half_InsertSort(nums):
    n = len(nums)
    if n < 2:
        return nums
    for i in range(1, n):
        loc = 0
        tmp = nums[i]
        low, high = 0, i - 1
        while low <= high:
            mid = low + (high - low) // 2
            if nums[mid] == nums[i]:
                loc = mid
                break
            elif nums[mid] < nums[i]:
                low = mid + 1
            else:
                high = mid - 1
        if high < low:
            loc = low
        for j in range(i, loc, -1):
            nums[j] = nums[j - 1]
        nums[loc] = tmp
    return nums

print(Half_InsertSort(nums))

希尔排序/缩小增量排序

希尔排序又叫作缩小增量排序，其本质还是插入排序，只不过是将待排序列按某种规则分成几个子序列。分别对这几个子序列进行直接插入排序。
这个规则的体现就是增量的选取，如果增量为1,就是直接插入排序

时间复杂度
时间复杂度取决于增量的选取方式，常见的有两种:
空间复杂度
O(1)
稳定性
不稳定
注意
实现

def ShellerSort(nums):
    def InsertSort(nums,k):
        n = len(nums)
        if n < 2:
            return nums
        for i in range(k, n, k):
            while i > 0:
                if nums[i] < nums[i - k]:
                    nums[i - k], nums[i] = nums[i], nums[i - k]
                    i -= k
                else:
                    break
        return nums
    incre = [5, 2, 1]
    for k in incre:
        nums = InsertSort(nums,k)
    return nums
print(ShellerSort(nums))

交换类排序

冒泡排序

注意
起泡排序算法结束的条件是在一趟排序过程中没有发生关键字交换。
时间复杂度
- 最好情况下，为原序列有序，只需要进行一趟冒泡排序，比较n-1次，时间复杂度为O(n)
- 最坏情况下，为原序列逆序，需要交换n(n-1)/2次数，比较n(n-1)次，时间复杂度为O(n^2)
空间复杂度
O(1)
稳定性
稳定
实现

def BubbleSort(nums):
    n = len(nums)
    if n < 2:
        return nums
    flag = True
    while flag:
        flag = False
        i = 0
        while i < n - 1:
            if nums[i] > nums[i + 1]:
                nums[i], nums[i + 1] = nums[i + 1], nums[i]
                flag = True
            i += 1
    return nums


print(BubbleSort(nums))

快速排序

来实现排序。以升序为例，其执行流程可以概括为" />

时间复杂度
空间复杂度
稳定性
不稳定
实现

def QuicklySort(nums):
    n = len(nums)
    if n < 2:
        return nums
    left = []
    right = []
    for i in range(1, n):
        if nums[i] <= nums[0]:
            left.append(nums[i])
        else:
            right.append(nums[i])
    return QuicklySort(left) + [nums[0]] + QuicklySort(right)


print(QuicklySort(nums))

选择类排序

简单选择排序

时间复杂度
需要n-1趟排序，共比较(n-1)+(n-2)+…+1=n(n-1)/2,交换n-1次，时间复杂度为O(n^2)
空间复杂度
O(1)
稳定性
不一定，看写法（稍微想了一下，但是没有验证）
实现

def SimpleSelectSort(nums):
    n = len(nums)
    if n < 2:
        return nums
    while n > 1:
        max_value = nums[0]
        loc = 0
        for i in range(1, n):
            if nums[i] > max_value:
                loc = i
                max_value = nums[i]
        nums[loc], nums[n - 1] = nums[n - 1], nums[loc]
        n -= 1
    return nums

print(SimpleSelectSort(nums))

堆排序

时间复杂度
空间复杂度
稳定性
实现

时间复杂度
空间复杂度
稳定性
实现

参考资料
《2023天勤计算机数据结构高分笔记》 (率辉)

内部排序算法

Java相关栏目本月热门文章