QuickSort again

　　I wrote a blog about Quick Sort before. Let's talk more about it.

　　If you don't think that the implementation in the blog mentioned is easy to remember and understand.

You can send your implementation to me by E-mail(lxw.ucas@gmail.com). Now let's look at some other

implementations that are not so amazing:

　　A new implementation in python is shown here:

def qs(arr):

    if not arr:

        return []

    low = []

    high = []

    for x in arr[1:]:

        if x <= arr[0]:

            low.append(x)

        else:

            high.append(x)

    low = qs(low)

    high = qs(high)

    return low + arr[:1] + high    # low + arr[0] + high   is NOT OK! --> ERROR PROMPT: 'can only concatenate list(not int) to list'

　　It seemed not so amazing and easy to understand as the former one. But it's ok as well. : ) Let's look

at another new implementation in python:

def quickSort(arr, start, end):

    if start >= end:    # EXIT

        return

    i = start

    j = end

    target = arr[i]

    while i < j:

        while arr[i] <= target and i < end:

            i += 1

        while arr[j] > target and j > start:

            j -= 1

        if i < j:

            arr[i], arr[j] = arr[j], arr[i]

    arr[start] = arr[j]

    arr[j] = target

    quickSort(arr, start, j - 1)

    quickSort(arr, j + 1, end)

　　Now, which way of implementation do you prefer? Do you think the implementation in the blog mentioned

is easy to understand and remember?

巴特西

QuickSort again

最新文章

热门文章