几种排序算法的实现

数据结构与算法 fireling 5921℃ 0评论

常见的几种排序算法,包括冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序和堆排序,冒泡排序、选择排序和插入排序的时间复杂度为O(n^2),希尔排序的时间复杂度为O(n^1.25),快速排序、归并排序和堆排序的时间复杂度为O(nlog2(n))

列出几种算法的代码实现:

  • 冒泡排序

def bubble_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len<2:
        return sort_list
    for i in range(iter_len-1):
        for j in range(iter_len-i-1):
            if sort_list[j]>sort_list[j+1]:
                sort_list[j], sort_list[j+1] = sort_list[j+1], sort_list[j]
    return sort_list
  • 选择排序

def selection_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len<2:
        return sort_list
    for i in range(iter_len-1):
        smallest = sort_list[i]
        location = i
        for j in range(i+1, iter_len):
            if sort_list[j]<smallest:
                smallest = sort_list[j]
                location = j
        if i != location:
            sort_list[i], sort_list[location] = sort_list[location], sort_list[i]
    return sort_list
  • 插入排序

def insertion_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len<2:
        return sort_list
    for i in range(1, iter_len):
        key = sort_list[i]
        location = i
        for j in range(i-1, -1, -1):
            if sort_list[j]>key:
                sort_list[j+1] = sort_list[j]
                location = j
        sort_list[location] = key
    return sort_list
  • 快速排序

class quick_sort(object):
    def _partition(self, alist, p, r):
        i, j = p, r
        x = alist[p]
        while i<j:
            while i<j and alist[j]>=x:
                j -= 1
            if i<j:
                alist[i] = alist[j]
                i += 1
            while i<j and alist[i]<=x:
                i += 1
            if i<j:
                alist[j] = alist[i]
                j -= 1
        alist[i] = x
        return i
    def _quicksort(self, alist, p, r):
        if p<r:
            q = self._partition(alist, p, r)
            self._quicksort(alist, p, q-1)
            self._quicksort(alist, q+1, r)
    def __call__(self, sort_list):
        self._quicksort(sort_list, 0, len(sort_list)-1)
        return sort_list
  • 归并排序

class merge_sort(object):
    def _merge(self, alist, p, q, r):
        left = alist[p:q+1]
        right = alist[q+1:r+1]
        for i in range(p, r+1):
            if len(left)>0 and len(right)>0:
                if left[0] <= right[0]:
                    alist[i] = left.pop(0)
                else:
                    alist[i] = right.pop(0)
            elif len(right) == 0:
                alist[i] = left.pop(0)
            elif len(left) == 0:
                alist[i] = right.pop(0)
    def _merge_sort(self, alist, p, r):
        if p<r:
            q = int((p+r)/2)
            self._merge_sort(alist, p, q)
            self._merge_sort(alist, q+1, r)
            self._merge(alist, p, q, r)
    def __call__(self, sort_list):
        self._merge_sort(sort_list, 0, len(sort_list)-1)
        return sort_list
  • 希尔排序

def shell_sort(sort_list):
    iter_len = len(sort_list)
    if iter_len<2:
        return sort_list
    gap = int(iter_len/2)
    while gap>0:
        for i in range(0, gap):
            for j in range(i+gap, iter_len, gap):
                if sort_list[j]<sort_list[j-gap]:
                    key = sort_list[j]
                    k = j-gap
                    while k>=0 and sort_list[k]>key:
                        sort_list[k+gap] = sort_list[k]
                        k -= gap
                    sort_list[k+gap] = key
        gap = int(gap/2)
    return sort_list
  • 堆排序

class heap_sort(object):
    def _max_heapify(self, alist, i, heap_size=None):
        length = len(alist)
        if heap_size is None:
            heap_size = length
        l = 2*i+1
        r = 2*i+2
        largest = i
        if l<heap_size and alist[l]>alist[i]:
            largest = l
        if r<heap_size and alist[r]>alist[largest]:
            largest = r
        if largest != i:
            alist[i], alist[largest] = alist[largest], alist[i]
            self._max_heapify(alist, largest, heap_size)
    def _build_max_heap(self, alist):
        root_end = int(len(alist)/2)
        for i in range(root_end-1, -1, -1):
            self._max_heapify(alist, i)
    def __call__(self, sort_list):
        self._build_max_heap(sort_list)
        heap_size = len(sort_list)
        for i in range(len(sort_list)-1, 0, -1):
            sort_list[0], sort_list[i] = sort_list[i], sort_list[0]
            heap_size -= 1
            self._max_heapify(sort_list, 0, heap_size)
        return sort_list

转载请注明:宁哥的小站 » 几种排序算法的实现

喜欢 (5)

您必须 登录 才能发表评论!