快速排序

Wayne posted @ Wed, 27 Aug 2014 02:17:23 +0000 in Notes , 2589 readers

步骤:1. 选择其中一个数,假设它是中间值

            2. 遍历一遍,比它小的放一段,大的放另一端,记录其中一段的数目

            3. 在记录的数目的下一位,将中间值插回去

            4. 于此位置,将要排序的数列分成两段,递归做

从上面的步骤可以看出,分治的过程是快排的核心。

一些优化:

1. 选中间值时,若选在最大或者最小,并恰好数列是有序的,都会是噩梦。故最好使用三点定位法

2. 遍历并分置两端时,为了节省空间开销,常用原地分割法。通过交换应置于位置的数,与当前实际位置的数,在同一个数列内部区分大小端。但是此交换存在过多中间操作,一个数可能要被交换多次。使用替换法可以有效缩短时间。替换法首先让中间值等于其中一端的值,然后从两端交替对中间值进行比较,并互相替换。最后多出一位赋回中间值

3. 用迭代替换递归。不过虽说如此,若中间值选择不当,依然还是会发生层数过多的情况。

 

代码留档:

class sort:
    def quicksort(self, num, start, end):
        while (start < end):                        #迭代改造后的递归
            p = sort().partition(num, start, end)
            #print num
            sort().quicksort(num, start, p)
            start = p + 1
        return num

    def partition(self, num, start, end):           #替换法下的排序过程
        sort().generatePivot(num, start, end)
        target = num[start]
        while( start < end - 1  ):
            while(start < end -1  and num[end-1] > target) :
                end -= 1
            num[start] = num[end - 1]
            while(start < end - 1  and num[start] < target):
                start += 1
            num[end - 1] = num[start]
        num[start] = target
        return start

    def generatePivot(self, num, start, end):       #三点定位,将中间值放到最左侧
        middle = start + (end -1- start)/2
        if num[start] > num[end-1]:
            num[start],num[end-1] = num[end-1],num[start]
        if num[middle] > num[end-1]:
            num[middle],num[end-1] = num[end-1],num[middle]
        if num[middle] > num[start]:
            num[middle],num[start] = num[start],num[middle]

    def sort(self, num):
        return sort().quicksort(num, 0, len(num))

#test case
print sort().sort([2,1,3,7,5,4,6])
print sort().sort(range(20)[::-1])
print sort().sort(range(20))
print sort().sort(range(200000)[::-1])
print sort().sort(range(200000))

 

write my essay fast said:
Fri, 12 Oct 2018 14:49:29 +0000

The lottery is one of the most searched categories on internet engines right now...These apartments are really cool and unique...The people who'll win them will be so lucky. Thanks for sharing it.

TN Board 9th Model P said:
Thu, 25 Aug 2022 14:26:16 +0000

Tamil Nadu Board Class 9th English Paper 2, 9th First Term Question Paper 2023, 9th Social Question Paper 2023, 9th English Question Paper 2023, TN Board 9th Exam Last Year Question Paper 2023, <a href="https://www.modelpaper2020.in/tn-board-9th-model-paper-2019-for-sa-fa-exam/">TN Board 9th Model Paper 2023</a> TN Board 9th Model Paper 2023, SA, FA Exam. TN 9th Model Paper 2023, Term 1 & 2 9th Model Question Paper 2023, 9th Tamil Question Paper 2023, Pdf 9th Question Paper 2023, in Tamil Nadu 9th English Question Paper 2023,, TN Board 9th Model Paper 2023 TN Board 9th Model Paper 2023, SA, FA Exam. TN 9th Model Paper 2023, Term 1 & 2 9th Model Question Paper 2023, 9th Tamil Question Paper 2023, Pdf 9th Question Paper 2023, in Tamil Nadu 9th English Question Paper 2023


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter