使用Python对众多字符串序列进行三种算法排序?

Question

题目描述

使用Python对产生的众多字符串实现快速排序,归并排序和选择排序并计算时间

相关代码

# -*- coding: utf-8 -*-
import random
import string
import time


# 产生随机字符串
def stochastic():
    str_listname = [random.choice(string.digits + string.ascii_letters) for _ in range(random.randint(3, 12))]
    random_str = ""
    random_str = random_str.join(str_listname)
    random_str_abc = random_str.split()
    return random_str_abc


data = []


# 产生众多字符串
def cycle():
    for i in range(1, 100_001):
        s = stochastic()[0]
        data.append(s)


cycle()


# print(data)


def selection_sort(num_list):
    import time
    time1 = time.time()
    length = len(num_list)
    if length <= 1:
        return num_list

    for j in range(length):
        min_num_index = j
        for i in range(j + 1, length):
            if num_list[i] < num_list[min_num_index]:
                min_num_index = i

        # 交换位置
        num_list[min_num_index], num_list[j] = num_list[j], num_list[min_num_index]
    time2 = time.time()
    time = time2 - time1
    print(time)
    return num_list


def merge_sort(array):
    if len(array) == 1:
        return array
    left_array = merge_sort(array[:len(array) // 2])
    right_array = merge_sort(array[len(array) // 2:])
    return merge(left_array, right_array)


def merge(left_array, right_array):
    left_index, right_index, merge_array = 0, 0, list()
    while left_index < len(left_array) and right_index < len(right_array):
        if left_array[left_index] <= right_array[right_index]:
            merge_array.append(left_array[left_index])
            left_index += 1
        else:
            merge_array.append(right_array[right_index])
            right_index += 1
    merge_array = merge_array + left_array[left_index:] + right_array[right_index:]
    return merge_array


def QuickSort(num):
    if len(num) <= 1:
        return num
    key = num[0]
    llist, rlist, mlist = [], [], [key]
    for i in range(1, len(num)):
        if num[i] > key:
            rlist.append(num[i])
        elif num[i] < key:
            llist.append(num[i])
        else:
            mlist.append(num[i])
    return QuickSort(llist) + mlist + QuickSort(rlist)


if __name__ == '__main__':
    a = time.time()
    selection_sort(data)  # 选择排序
    b = time.time()
    c = b - a
    print('选择耗时为%s' % c)
    # print('-----------------------------------------------------------------------------------------------')
    # # # print(sorted(data))  # 内置排序
    print('-----------------------------------------------------------------------------------------------')
    d = time.time()
    merge_sort(data)
    e = time.time()
    f = e - d
    print('归并耗时为%s' % f)
    print('-----------------------------------------------------------------------------------------------')
    g = time.time()
    QuickSort(data)
    h = time.time()
    i = h - g
    print('快速耗时为%s' % i)

你期待的结果是什么？实际看到的错误信息又是什么？

大佬们好,我自身感觉我的代码没有问题,但选择排序的时候运行不出来,我查了一下是内存的问题,我想问一下我应该如何优化选择排序部分的代码?

Answer 1

1.使用内置的 sorted() 函数进行排序，这样可以大大提升性能。
2.将循环条件改为 range(length - 1)，因为在最后一次循环中，最小数已经在最后一个位置，不需要再进行比较。
3.在交换位置时，可以采用高级赋值符号 x, y = y, x。

def selection_sort(num_list):
    length = len(num_list)
    if length <= 1:
        return num_list

    for j in range(length - 1):
        min_num_index = j
        for i in range(j + 1, length):
            if num_list[i] < num_list[min_