データ構造——並べ替え

カテゴリ
ソート方法
平均して
ベスト?コンディション
最悪の場合
補助スペース
安定性
並べ替えの挿入
並べ替えの直接挿入
O(n 2)
O(n)
O(n 2)
O(1)
安定している
ヒルの並べ替え
O(nlogn)~O(n 2)
O(n 1.3)
O(n 2)
O(1)
不安定です
並べ替えを選択
並べ替えを簡単に選択
O(n 2)
O(n 2)
O(n 2)
O(1)
安定している
積み上げ順序
O(nlogn)
O(nlogn)
O(nlogn)
O(1)
不安定です
並べ替え
泡の並べ替え
O(n 2)
O(n)
O(n 2)
O(1)
安定している
クイックソート
O(nlogn)
O(nlogn)
O(n 2)
O(logn)~O(n)
不安定です
並べ替え
並べ替え
O(nlogn)
O(nlogn)
O(nlogn)
O(n)
安定している

#! /usr/bin/python
# coding=utf-8
import random, timeit
times = 10000
def bubble(array):
    # o(n*n)
    for i in xrange(len(array) - 1):
        for j in xrange(len(array) - i):
            if array[i] > array[j+i]:
                array[j+i], array[i] = array[i], array[j+i]
    if times == 1: print array,

def select(array):
    """
    Simple Selection Srot
    o(n*n)
    """
    for i in xrange(len(array) - 1):
        min = array[i]
        index = 0
        for j in xrange(i,len(array)):
            if array[j] < min:
                min  = array[j]
                index = j
        if index > 0:
            array[index], array[i] = array[i], array[index] #      
    if times == 1: print array,

def insert(array):
    """
    Straight Insertion Sort
    """
    for i in xrange(len(array) - 1):
        if array[i+1] >= array[i]: #              
            continue
        j = i + 1
        temp = array[j]
        while j > 0 and array[j-1] > temp:
            array[j] = array[j - 1]
            j -= 1
        array[j] = temp

    if times == 1: print array,

def shell(array):
    """
        
                 
    """
    increment = len(array)
    while increment > 1:
        increment = increment / 3 + 1
        for i in xrange(increment, len(array)):
            if array[i] >= array[i - increment]:
                continue
            j = i
            temp = array[i]
            while j > 0 and array[j-1] > temp:
                array[j] = array[j - 1]
                j -= 1
            array[j] = temp
    if times == 1: print array,

def heap(array):
    """
       
            ，          
    """
    length = len(array)
    for x in xrange(0,length / 2):
        i = length / 2 - x
        _heap(array, i, len(array))
    for x in xrange(1,length):
        i = length - x + 1
        array[0], array[i-1] = array[i-1], array[0]
        _heap(array, 1, i - 1)
    if times == 1: print array,

def _heap(array, s, length):
    #print str(s) + "-" * 10
    temp = array[s-1]
    j = 2 * s
    while j <=length:
        if j < length and array[j-1] < array[j]: #        ， j(  )    
            j +=1
        if temp > array[j-1]: #         ，  
            break
        array[s-1] = array[j-1]
        s = j
        j *= 2
    array[s-1] = temp

def merge(array):
    """
        
    """
    _merge(array, 0, len(array))
    if times == 1: print array,

def _merge(array, start, end):
    
    if end - start < 2:
        return

    m = (end - start) / 2
    #print start, m, end
    left = array[start:start + m]
    right = array[start + m:end]

    _merge(array, start,  start + m)
    _merge(array, start + m, end)
    
    _merge2(array, start, start + m, end)

def _merge2(array, start, middle, end):
    s,m = start, middle
    l = []
    while start < m and middle < end:
        a,b = array[start], array[middle]
        if a < b:
            l.append(a)
            start += 1
        else:
            l.append(b)
            middle += 1
    if start < m:
        l += array[start:m]
    if middle < end:
        l += array[middle:end]
    for i in xrange(s,end):
        if array[i] != l[i - s]:
            array[i] = l[i - s]

def quick(array):
    """
        
    """
    _quick(array, 0, len(array) - 1)
    if times == 1: print array,

def _quick(array, start, end):
    if start >= end:
        return
    
    pivot = partition(array, start, end)
    _quick(array, start, pivot)
    _quick(array, pivot + 1, end)

def partition(array, start, end):
    key = array[start]
    while start < end:
        while start < end and array[end] >= key:
            end -= 1
        array[start], array[end] = array[end], array[start]
        while start < end and array[start] <= key:
            start += 1
        array[start], array[end] = array[end], array[start]
    return end

if __name__ == '__main__':
    array = [random.randint(1,100) for i in xrange(100)]
    print array
    
    from timeit import Timer

    print "bubble",Timer(lambda: bubble(array[:])).timeit(number=times)
    
    print "select", Timer(lambda: select(array[:])).timeit(number=times)
    print "insert", Timer(lambda: insert(array[:])).timeit(number=times)
    print "shell", Timer(lambda: shell(array[:])).timeit(number=times)
    print "heap", Timer(lambda: heap(array[:])).timeit(number=times)
    print "merge", Timer(lambda: merge(array[:])).timeit(number=times)
    print "quick", Timer(lambda: quick(array[:])).timeit(number=times)

    print "sorted", Timer(lambda: sorted(array[:])).timeit(number=times)