Python 双向链表 快速排序

1、创建链表：

from random import randint

class DLinkedNode(object):

    def __init__(self, data=None, pre=None, post=None):

        self.data = data

        self.pre = pre

        self.post = post

class DLinkedList(object):

    def __init__(self):

        self.head = DLinkedNode()

        self.tail = DLinkedNode()

        self.head.post = self.tail

        self.tail.pre = self.head

    def build(self, n):

        pre = self.head

        for _ in range(n):

            data = randint(1, 100)

            node = DLinkedNode(data, post=self.tail)

            self.tail.pre = node

            pre.post = node

            node.pre = pre

            pre = node

        return self.head, self.tail

2、快速排序：

class Solution(object):

    def quick_sort(self, low, high):

        if not lowor not low.post:

            return

        if low != high:

            p, q = low, high

            key = p.data

            while p != q:

                while p != q and q.data >= key:

                    q = q.pre

                p.data = q.data

                while p != q and p.data <= key:

                    p = p.post

                q.data = p.data

            p.data = key

            if low != p:

                self.quick_sort(low, p.pre)

            if p != high:

                self.quick_sort(p.post, high)

3、测试：

h, t = DLinkedList().build(10)

curr = h

while curr.post:

    print curr.post.data,

    curr = curr.post

print()

while curr.pre:

    print curr.pre.data,

    curr = curr.pre

print()

Solution().quick_sort(h.post, h.post, t.pre)

curr = h

while curr.post:

    print curr.post.data,

    curr = curr.post

list快速排序：

import random

class Solution(object):

    def quick_sort(self, a, left, right):

        if left >= right: return

        pivot = self.partition(a, left, right)

        self.quick_sort(a, left, pivot-1)

        self.quick_sort(a, pivot+1, right)

    def partition(self, a, left, right):

        index = left + 1

        key = a[left]

        for i in range(left+1, right+1):

            if a[i] <= key:

                a[i], a[index] = a[index], a[i]

                index += 1

        a[left], a[index-1] = a[index-1], key

        return index-1

if __name__ == '__main__':

    a = [random.randint(0, 100) for _ in range(10)]

    print(a)

    Solution().quick_sort(a, 0, len(a)-1)

    print(a)