快速排序法和合并排序法——Python实现

向右看齐 2022-05-19 06:51 178阅读 0赞

# 快速排序法
    class Solution:
        def sort(self,a):
            first = 0
            last = len(a) - 1
            # 这里需要注意的是，需要将a整体作为迭代变量
            # 因此也需要将first和last作为迭代变量
            # 这是因为python中输入数组后，如果分割数组作为下一次迭代，原数组是不会变的
            self.start_sort(a,first,last)
            return a
        def start_sort(self,a,first,last):
            if first < last:
                # 以第一元素作为阈值
                key = a[first]
                i = first
                j = last
                while i < j:
                    # 从后向前，寻找小于阈值的元素（注意这里的>=）
                    while i<j and a[j] >= key:
                        j = j - 1
                    # 将小于阈值的元素赋值给靠前的a[i]
                    a[i] = a[j]
                    # 从前向后，寻找大于阈值的元素（注意这里的<=）
                    while i<j and a[i] <= key:
                        i = i + 1
                    # 将大于阈值的元素赋值给靠后的a[j]
                    a[j] = a[i]
                # 将阈值赋值给第i个元素，这样可以保证，i之前的数组均小于a[i]，i之后的数组均大于a[i]
                a[i] = key
                self.start_sort(a,first,i-1)
                self.start_sort(a,i+1,last)
    a = [2,8,4,6,99,8,82,12]
    S = Solution()
    S.sort(a)

# 合并排序法
    class Solution:
        def sort(self,a):
            first = 0
            last = len(a) - 1
            # 和快速排序法一样，需要将a的整体作为递归的变量
            self.sort_begin(a,first,last)
            return a
        # 开始排序，需要注意先将a数组按二分法进行分割
        def sort_begin(self,a,first,last):
            if first < last:
                # 二分法分割数组，划分为最小的单元
                mid = (first + last)/2
                self.sort_begin(a,first,mid)
                self.sort_begin(a,mid+1,last)
                self.compare(a,first,last) # 从最底层（最小单元）到全部的排序，完成对a整体的排序
        def compare(self,a,first,last):
            if first < last:
                mid = (first + last)/2
                i = first
                j = mid + 1
                b = []
                # 将前一半和后一半进行比较，小的放在前面
                while i <= mid and j <= last:
                    if a[i] < a[j]:
                        b.append(a[i])
                        i = i +1 
                    else:
                        b.append(a[j])
                        j = j + 1
                # 哪一半没有遍历完，将其加在排序后数组的最后
                while i<= mid:
                    b.append(a[i])
                    i = i + 1
                while j <= last:
                    b.append(a[j])
                    j = j + 1
                # 对递归变量a进行赋值
                for i in range(len(b)):
                    a[first+i] = b[i]
    S = Solution()
    S.sort([1,3,5,2,3,99,3,12,0,1])