Python 冒泡排序 快速排序 求素数代码实现 初级岗位面试经常有的

快速排序是在工作中基本不会用到的算法,但是面试中经常出现,面试官主要想考考大家对于递归运算是否了解

快速排序的基本思想:
在当前待排序的无序区中任选一个记录作为基准, 以此基准将当前无序区划分为左、右两个较小的子区间, 并使左边子区间中所有记录的值均小于等于基准值, 右边子区间中所有记录的值均大于等于基准值, 然后再递归排序左右两个较小的子区间。

以下代码实现了3种不同的冒泡排序算法,一种快速排序算法以及一种优化过的求素数的算法
#!/bin/python3
#-*- coding: utf-8 -*-
import random
import math, sys

x = list(range(0, 6))
random.shuffle(x)

def bubbleSort(x):
    if len(x) <= 1: return
    for i in range(0, len(x) - 1):
        for j in range(i+1, len(x)):
            if x[i] > x[j]:
                x[i], x[j] = x[j], x[i]

def bubbleSort2(x):

    start = 0
    end = len(x) - 1
    while 1:
        if start >= end: break
        
        minv = x[start]
        maxv = x[end]
        minp = start
        maxp = end
        
        for i in range(start, end + 1):
            if minv > x[i]:
                minp = i
                minv = x[i]
            if maxv < x[i]:
                maxp = i
                maxv = x[i]
            
        x[start], x[minp] = x[minp], x[start]
        if start == maxp: maxp = minp
        x[end], x[maxp] = x[maxp], x[end]

        start += 1
        end -= 1

def bubbleSort3(x, start=0, end=-1):

    if (end == -1): end = len(x) - 1
    if start >= end: return
        
    minv = x[start]
    maxv = x[end]
    minp = start
    maxp = end
        
    for i in range(start, end + 1):
        if minv > x[i]:
                minp = i
                minv = x[i]
        if maxv < x[i]:
            maxp = i
            maxv = x[i]
            
    x[start], x[minp] = x[minp], x[start]
    if start == maxp: maxp = minp
    x[end], x[maxp] = x[maxp], x[end]

    bubbleSort3(x, start + 1, end - 1)

def quickSort(x, start=0, end=-1):
    if (end == -1): end = len(x)

    # if end > len(x): return
    if (start + 1 >= end): return

    pos = start
    mid = x[start]
    for i in range(start + 1, end):
        if x[i] < mid:
            x[pos] = x[i]
            x[i] = x[pos + 1]
            pos = pos + 1
        x[pos] = mid

    quickSort(x, start, pos) 
    quickSort(x, pos+1, end)

def prime(n):  
    x = [2, 3, 5, 7]

    for i in range(3, n + 1, 2):
        if (i % 3 == 0): continue
        if (i % 5 == 0): continue
        if (i % 7 == 0): continue

        flag = True
        for j in range(11, int(math.sqrt(i)) + 1):
            if (i % j == 0): 
                flag = False
                break
        if (flag): x.append(i)    
    return x

# print(x)
# print()
# quickSort(x)
# bubbleSort(x)
# bubbleSort2(x)
# bubbleSort3(x)
# print(x)

print(prime(100))


发表于:2014-10-13 14:20:28

原文链接(转载请保留): http://www.multisilicon.com/blog/a25312251.html

友情链接: MICROIC
首页