建议收藏！10 种 Python 聚类算法完整操作示例

Python034

建议收藏！10 种 Python 聚类算法完整操作示例,第1张

#encoding=utf-8

import random

from copy import copy

def directInsertSort(seq):

 """ 直接插入排序 """

 size = len(seq)

 for i in range(1,size):

  tmp, j = seq[i], i

  while j > 0 and tmp < seq[j-1]:

   seq[j], j = seq[j-1], j-1

  seq[j] = tmp

 return seq

def directSelectSort(seq):

 """ 直接选择排序 """

 size = len(seq)

 for i in range(0,size - 1):

  k = ij = i+1

  while j < size:

   if seq[j] < seq[k]:

    k = j

   j += 1

  seq[i],seq[k] = seq[k],seq[i]

 return seq

def bubbleSort(seq):

 """冒泡排序"""

 size = len(seq)

 for i in range(1,size):

  for j in range(0,size-i):

   if seq[j+1] < seq[j]:

    seq[j+1],seq[j] = seq[j],seq[j+1]

 return seq

def _divide(seq, low, high):

 """快速排序划分函数"""

 tmp = seq[low]

 while low != high:

  while low < high and seq[high] >= tmp: high -= 1

  if low < high:

   seq[low] = seq[high]

   low += 1

  while low < high and seq[low] <= tmp: low += 1

  if low < high:

   seq[high] = seq[low]

   high -= 1

 seq[low] = tmp

 return low

def _quickSort(seq, low, high):

 """快速排序辅助函数"""

 if low >= high: return

 mid = _divide(seq, low, high)

 _quickSort(seq, low, mid - 1)

 _quickSort(seq, mid + 1, high)

def quickSort(seq):

 """快速排序包裹函数"""

 size = len(seq)

 _quickSort(seq, 0, size - 1)

 return seq

def merge(seq, left, mid, right):

 tmp = []

 i, j = left, mid

 while i < mid and j <= right:

  if seq[i] < seq[j]:

   tmp.append(seq[i])

   i += 1

  else:

   tmp.append(seq[j])

   j += 1

 if i < mid: tmp.extend(seq[i:])

 if j <= right: tmp.extend(seq[j:])

 seq[left:right+1] = tmp[0:right-left+1]

def _mergeSort(seq, left, right):

 if left == right: 

  return

 else:

  mid = (left + right) / 2

  _mergeSort(seq, left, mid)

  _mergeSort(seq, mid + 1, right)

  merge(seq, left, mid+1, right)

#二路并归排序

def mergeSort(seq):

 size = len(seq)

 _mergeSort(seq, 0, size - 1)

 return seq

if __name__ == '__main__':

 s = [random.randint(0,100) for i in range(0,20)]

 print s

 print "\n"

 print directSelectSort(copy(s))

 print directInsertSort(copy(s))

 print bubbleSort(copy(s))

 print quickSort(copy(s))

 print mergeSort(copy(s))