快速排序的python实现

quick_sort.py

#! /usr/bin/env python
# -*- coding: utf-8 -*-


def quick_sort(sequence, start_index, end_index):
#    print sequence
    if start_index < end_index:
        main_element = partition(sequence, start_index, end_index)
#        print main_element
        quick_sort(sequence, start_index, main_element-1)
        quick_sort(sequence, main_element+1, end_index)
    else:
        pass


def partition(sequence, start_index, end_index):
    middle_value = sequence[end_index]
    mark_index = start_index - 1
    scan_index = start_index
    while scan_index < end_index:
        if sequence[scan_index] < middle_value:
            mark_index += 1
            sequence[scan_index], sequence[mark_index] = \
                    sequence[mark_index], sequence[scan_index]
        else:
            pass
        scan_index += 1

    sequence[end_index], sequence[mark_index+1] = \
            sequence[mark_index+1], sequence[end_index]
    return mark_index+1


if __name__ == '__main__':
    original_sequence = raw_input("Enter the sequence: ")
    sequence_str = original_sequence.split()
    sort_sequence = []
    for number_str in sequence_str:
        sort_sequence.append(int(number_str))

    size = len(sort_sequence)
    quick_sort(sort_sequence, 0, size-1)
    print sort_sequence


"""
➜  algorithm  ./quick_sort.py
Enter the sequence: 90 89 09 32 4 5 76 8999 32 43554 6576 090
[4, 5, 9, 32, 32, 76, 89, 90, 90, 6576, 8999, 43554]
"""