数据结构与算法-排序(二)

希尔排序

• 基本排序

将原本有大量记录数的记录进行分组。分割成若干序列，此时每个子序列待排序的记录个数就比较少了，然后在这些子序列内分别进行直接插入排序，当整个序列都基本有序时，再对全体记录执行一次直接插入排序。其时间复杂度为O(n**3/2),突破了O(n*n)。

快速排序

• 基本思想

快速排序是基于一种“二分”的思想，相比较冒泡排序，总的比较和交换的次数减少。核心是设置基准点，跳跃式交换，平均时间复杂度为O(NlogN)。

代码实现(python)

import random


def shell_sort(test_list):
    increment = len(test_list)

    while increment > :
        # increment分割的序列
        increment = increment/ + 
        # 以下就是直接插入排序的代码 
        for i in range(increment, len(test_list)):
            # 每一个子序列都设定一个基准
            temp = test_list[i]
            j = i - 
            while j >=  and test_list[j] > temp:
                test_list[j + ] = test_list[j]
                j -= 
            test_list[j + ] = temp

    return test_list


def quick_sort(arr, left, right):

    if left > right:
        return
    # temp存的基准数
    temp = arr[left]
    pivot_index = left
    pivot_end = right

    while pivot_index != pivot_end:

        # 先从右往左找大于基准数的数
        while arr[pivot_end] >= temp and pivot_index < pivot_end:
            pivot_end -= 

        # 再从左往右找小于基准数的数
        while arr[pivot_index] <= temp and pivot_index < pivot_end:
            pivot_index += 

        # 交换两个数在数组中的位置
        if pivot_index < pivot_end:
            arr[pivot_index], arr[pivot_end] = arr[pivot_end], arr[pivot_index]

    # 将基准位置归位
    arr[left], arr[pivot_index] = arr[pivot_index], arr[left]

    # 继续处理左边的,这是一个递归的过程
    quick_sort(arr, left, pivot_index - )
    # 继续处理右边的,这是一个递归的过程
    quick_sort(arr, pivot_index + , right)

    return arr

if __name__ == '__main__':
    quick_list = [random.randint(, ) for _ in range()]
    print(quick_sort(quick_list, , len(quick_list)-))

    shell_list = [random.randint(, ) for _ in range()]
    print(quick_sort(shell_list, , len(shell_list)-))