排序算法对比分析

嗯,这是个老话题,其实我就是复习下而已.

冒泡排序:

冒泡排序是一种交换排序,相邻之间的两个元素进行比较,如果两个元素的顺序是错误的,那么就交换位置.

具体的步骤是:

比较相邻两个元素,如果地一个元素比第二个元素大,那么就交换位置每对相邻的元素做同样的比较,从开头的第一对元素,直到最后一对元素.经过这轮的比较交换后,最后的那个元素是最大的了,也就是说这个最大的元素在该列表是有顺序了的,此后不再参与比较工作. 重复上面的个两个步骤,每重复一次,列表中已经有序的元素就会增加一个,且这个元素不再参与比较.不断的对越来越少的无序元素重复上面的步骤直到没有元素参与比较时,该列表就是一个有顺序的列表了. 参考实现代码:

import random
l = [random.randint(0,101) for n in range(10)]
print l
for i in range(len(l)):
   for j in range(len(l)-i-1):
       if l[j] > l[j+1]:
           l[j],l[j+1] = l[j+1],l[j]
print l

冒泡排序是一种很慢的排序算法,时间复杂度为O(n^{2}), 因此只适用于少量数据的情景中.

快速排序:

快速排序的思路是采用分治法将一个list分成两个子列表,它的步骤是:

在列表中选择一个元素作为”基准”(pivot) 所有小于”基准”的元素都移到基准的左边,所有大于”基准”的元素移到基准的右边. 对基准左边和右边的两个子集,重复第一步和第二步,直到子集中的元素只剩下一个元素为止参考实现:

#!/usr/bin/env python

# Written by Magnus Lie Hetland

"Everybody's favourite sorting algorithm... :)"

def partition(list, start, end):
    pivot = list[end]                          # Partition around the last value
    bottom = start-1                           # Start outside the area to be partitioned
    top = end                                  # Ditto

    done = 0
    while not done:                            # Until all elements are partitioned...

        while not done:                        # Until we find an out of place element...
            bottom = bottom+1                  # ... move the bottom up.

            if bottom == top:                  # If we hit the top...
                done = 1                       # ... we are done.
                break

            if list[bottom] > pivot:           # Is the bottom out of place?
                list[top] = list[bottom]       # Then put it at the top...
                break                          # ... and start searching from the top.

        while not done:                        # Until we find an out of place element...
            top = top-1                        # ... move the top down.

            if top == bottom:                  # If we hit the bottom...
                done = 1                       # ... we are done.
                break

            if list[top] < pivot:              # Is the top out of place?
                list[bottom] = list[top]       # Then put it at the bottom...
                break                          # ...and start searching from the bottom.

    list[top] = pivot                          # Put the pivot in its place.
    return top                                 # Return the split point

def quicksort(list, start, end):
    if start < end:                            # If there are two or more elements...
        split = partition(list, start, end)    # ... partition the sublist...
        quicksort(list, start, split-1)        # ... and sort both halves.
        quicksort(list, split+1, end)
    else:
        return

快速排序的时间复杂度为Ο(n log n)

选择排序:

选择排序每次从列表中查找出最小的元素,存放到已经是有序的列表中,再从剩余未排序的列表中查找最小的元素放入已排序好的列表的最后,依次类推直到所有元素排序完毕.

def selection_sort(l):
    for i in range(len(l)):
        min = i
        for j in range(i+1, len(l)):
            if l[min]>l[j]:
                min = j
        if l[i]!=l[min]:
            l[i],l[min] = l[min],l[i]

比较次数O(n^2),比较次数与关键字的初始状态无关，总的比较次数N=(n-1)+(n-2)+…+1=n*(n-1)/2。交换次数O(n),最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

关注公众号「Python之禅」，回复「1024」免费获取Python资源

排序算法对比分析

猜你喜欢