快速排序法

由于冒泡排序法的时间复杂程度较高,为了提高排序效率,人们改进了冒泡排序,从而得到了快速排序法.快速排序法的核心思想是:经过一趟比较后,确定某个元素在排序后的最终位置.

假设有一个含n个元素的待排序集合A={a1,a2...an},选取a1作为基准元素,采用快速排序法一趟排序的过程如下:

1.设置两个变量i,j作为指针,排序之初,i=0,j=n-1

2.以第一个元素作为基准元素,保存为变量key,key=a1

3.从后向前搜索,即从j开始向前,如果A[j]>key,则j--,直到找到第一个比key小的元素,交换A[i]与A[j]

4.从前向后搜素,即从i开始向后,如果A[i]>key,则i++,直到找到一个比key大的元素,交换A[i]与A[j]

5.反复执行步骤3,4,直到i=j,停止循环,完成一趟排序,i位置就是基准元素最终的落脚位置.i位置的左侧元素都比key小,i的右侧都比key大,最总key将处于集合中的最终位置.

然后对左侧子集合和右侧子集合继续套用上述排序过程,直到每个子集合只含有一个元素为止,至此排序完毕.

用python实现快速排序法,定义名为Quicksort的快速排序函数,变量如下:

1.num变量:表示排序数组名,为list类型

2.low变量:表示次趟排序的首位元素位置,为int类型

3.high变量:表示此趟排序的末位元素的位置,为int类型

4.i变量:表示此趟排序的左指针,为int类型

5.j变量:表示此趟排序的右指针,为int类型

6.key变量:保存基准元素的值,为list类型

函数定义如下:

def Quicksort(nums, low, high):
    if low < high:
        i = low
        j = high
        key = nums[i]
        
        while i < j:
            # 从右向左找第一个小于基准元素的元素
            while i < j and key <= nums[j]:
                j -= 1
            if i < j:
                nums[i] = nums[j]
            
            # 从左向右找第一个大于基准元素的元素
            while i < j and key >= nums[i]:
                i += 1
            if i < j:
                nums[j] = nums[i]
        
        # 将基准元素放到它最终的位置
        nums[i] = key
        
        # 递归对基准元素左边的子数组进行快速排序
        Quicksort(nums, low, i - 1)
        
        # 递归对基准元素右边的子数组进行快速排序
        Quicksort(nums, i + 1, high)

测试

nums = [3, 5, 2, 4, 1]
Quicksort(nums, 0, len(nums) - 1)
print(nums)  # 输出排序后的数组

输出

[1, 2, 3, 4, 5]