Python 代码实现身份证号码随机隐去和排序

本文将使用 Python 代码实现对身份证号码进行随机隐去,并用 1-9 之间的随机数代替,之后利用插入排序、选择排序、二分归并排序和快速排序算法对生成的 ID_Number 序列进行排序,并比较各算法的执行时间。

代码实现

import random
import time

# 随机生成一个身份证号码
id_num = '123456789012345678'
id_num_list = list(id_num)

# 隐藏4位数字并用1-9的随机数代替
start = random.randint(0, 12)
for i in range(start, start+4):
    id_num_list[i] = str(random.randint(1, 9))

ID_Number = id_num_list
print('替换后的身份证号码:', ''.join(ID_Number))

# 插入排序
def insertion_sort(arr):
    for i in range(1, len(arr)):
        j = i
        while j > 0 and arr[j] < arr[j-1]:
            arr[j], arr[j-1] = arr[j-1], arr[j]  # 交换元素
            j -= 1
    return arr

start_time = time.time()
sorted_arr = insertion_sort(ID_Number)
end_time = time.time()
print('插入排序后的结果:', ''.join(sorted_arr))
print('用时:{:.10f}s'.format(end_time - start_time))
print()

# 选择排序
def selection_sort(arr):
    for i in range(len(arr)):
        min_index = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]  # 交换元素
    return arr

start_time = time.time()
sorted_arr = selection_sort(ID_Number)
end_time = time.time()
print('选择排序后的结果:', ''.join(sorted_arr))
print('用时:{:.10f}s'.format(end_time - start_time))
print()

# 二分归并排序
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result += left[i:]
    result += right[j:]
    return result

start_time = time.time()
sorted_arr = merge_sort(ID_Number)
end_time = time.time()
print('二分归并排序后的结果:', ''.join(sorted_arr))
print('用时:{:.10f}s'.format(end_time - start_time))
print()

# 快速排序
def quick_sort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quick_sort(arr, low, pi-1)
        quick_sort(arr, pi+1, high)
    return arr

def partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]  # 交换元素
    arr[i+1], arr[high] = arr[high], arr[i+1]  # 交换元素
    return i+1

start_time = time.time()
sorted_arr = quick_sort(ID_Number, 0, len(ID_Number)-1)
end_time = time.time()
print('快速排序后的结果:', ''.join(sorted_arr))
print('用时:{:.10f}s'.format(end_time - start_time))
print()

# 输出个人信息和系统时间
def print_info():
    print('李某某机器学习作业 模块 完成时间:', time.strftime('%Y年%m月%d日'))

print_info()

算法分析

  • 插入排序

    • 时间复杂度:最佳情况 O(n),平均情况 O(n^2),最坏情况 O(n^2)
    • 空间复杂度:O(1)
    • 适用于少量数据排序
  • 选择排序

    • 时间复杂度:O(n^2)
    • 空间复杂度:O(1)
    • 不稳定排序
    • 适用于数据量较小的情况
  • 二分归并排序

    • 时间复杂度:O(n log n)
    • 空间复杂度:O(n)
    • 稳定排序
    • 适用于数据量较大且需要稳定排序的情况
  • 快速排序

    • 时间复杂度:最佳情况 O(n log n),平均情况 O(n log n),最坏情况 O(n^2)
    • 空间复杂度:O(log n)
    • 不稳定排序
    • 适用于数据量较大且需要快速排序的情况

总结

通过以上代码实现和算法分析,我们可以看到,不同的排序算法在时间复杂度和空间复杂度方面各有优劣,选择合适的排序算法需要根据实际情况进行权衡。


原文地址: https://www.cveoy.top/t/topic/or4B 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录