クイックソート、集計ソート、スタックソートpython実装

高速ソートの時間的複雑度はO(n*logn)、最悪はO(n^2)、平均はO(n*logn)と不安定なソートが望ましい
集計ソートの時間的複雑度はO(n*logn)、最悪はO(n*logn)、平均はO(n*logn)と安定したソートが望ましい
スタックソートの時間的複雑度はO(n*logn)、最悪はO(n*logn)、平均はO(n*logn)と不安定なソートが望ましい
1.クイックソート
クイックソートの紹介とC言語実装ここで:クイックソートC言語実装
ここでは、高速ソートpython実装について説明します.

def recurse(lista,left,right):
	if left<right:
		i=left;
		j=right;
		tmp=lista[left];
		while(i<j):
			while(i<j and lista[j]>=tmp):
				j=j-1;
			if i<j:
				lista[i]=lista[j];
				i=i+1;
			while (i<j and lista[i]<tmp):
				i=i+1;
			if i<j:
				lista[j]=lista[i];
				j=j-1;
		lista[i]=tmp;
		recurse(lista,left,i-1);  #  
		recurse(lista,i+1,right);
	return lista;
def quicksort(lista):
	leng=len(lista);
	recurse(lista,0,leng-1);

lista=[1,4,23,45,97,22,10,4];   #        
quicksort(lista);
print lista;

2.集計ソート
集計ソートおよびC言語実装ここで、集計ソートC言語実装
ここでは、python実装の集計ソートについて説明します.

def merge(lista,left,mid,right):   #       
	i=left;
	j=mid+1;
	tmp=[];
	while(i<=mid and j<=right):
		if lista[i]<= lista[j]:
			tmp.append(lista[i]);
			i=i+1;
		else:
			tmp.append(lista[j]);
			j=j+1;
	while(i<=mid):
		tmp.append(lista[i]);
		i=i+1;
	while(j<=right):
		tmp.append(lista[j]);
		j=j+1;
	i=0; 
	while(i<right-left+1):
		lista[left+i]=tmp[i];
		i=i+1;
def mergerecurse(lista,left,right):
	if left<right:
		mid=int((right+left)/2);
		mergerecurse(lista,left,mid);
		mergerecurse(lista,mid+1,right);
		merge(lista,left,mid,right);
	return lista;
def mergesort(lista):                              
	leng=len(lista);
	mergerecurse(lista,0,leng-1);

lista=[1,4,23,45,97,22,10,4];       #    
mergesort(lista);
print lista;
	

3.ヒープのソート
スタックソートおよびC言語実装ここで:スタックソートC言語実装
この文書では、スタックソートpython実装について説明します.
pythonでは、heapのheappushメソッドを直接使用してスタックを構築し、heapppopを使用してスタックの最小要素をポップアップするスタックというデータ構造が提供されています.

from heapq import *;
def heapsort(lista):
	h=[];
	for i in range(0,len(lista)):
		heappush(h,lista[i]);
	for i in range(0,len(h)):
		lista[i]=heappop(h);

Heapデータ構造を独自に実現することもできます.

def heapadjust(lista,s,end):
	i=2*s+1;
	tmp=lista[s];
	while(i<=end):
		if i+1<=end and lista[i+1]>lista[i]:
			i=i+1;
		if lista[i]<=tmp:
			break;
		lista[s]=lista[i];
		s=i;
		i=s*2+1;
	lista[s]=tmp;
def heapsort2(lista):
	n=len(lista);
	for i in range((n-1)/2,-1,-1):
		heapadjust(lista,i,n-1);
	for i in range(n-1,-1,-1):
		lista[i],lista[0]=lista[0],lista[i];
		heapadjust(lista,0,i-1);
lista=[5,4,2,5,1,7];        #        
heapsort(lista);
print lista;