注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

AP计算机众里寻他千百度,名师成就满分路

AP计算机

 
 
 

日志

 
 
关于我

大学讲师,中国首批AP计算机教师,著有中国第一套,历经五年实践证明深受学生欢迎的成功的AP计算机双语教材,2013年以93%的满分率开创了中国AP计算机成功的先河,远远超出全美26.6%的满分率,为中国AP计算机教学树立了典范,并在同年加拿大计算机竞赛中勇夺桂冠,任教学生获哥伦比亚大学,麻省理工学院,卡耐基梅隆大学,宾夕法尼亚大学,康奈尔大学,西北大学等学校录取,远程学生遍及北京、长春、南京、重庆、广州、济南, 深圳、成都、费城,洛杉矶,加州,宾州,新罕布什尔州等地,希望借此平台为信息技术的发展做出贡献!

网易考拉推荐

Python冒泡排序,插入排序,选择排序算法实现  

2015-06-03 14:31:46|  分类: Python |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

Python冒泡排序,插入排序,选择排序算法实现 - 千里马 - 众里寻他千百度,腾飞成就满分路
 [python] view plaincopy
  1. #-------------------------------------------------------------------------------  
  2. # Name:        Sort.py  
  3. # Purpose:  
  4. #  
  5. # Author:      Killua  
  6. # E-mail:      killua_hzl@163.com  
  7. # Created:     11-04-2011  
  8. # Copyright:   (c) Killua 2011  
  9. #-------------------------------------------------------------------------------  
  10. #!/usr/bin/env python  
  11. # -*- coding: utf-8 -*-  
  12. import sys;  
  13. import random;  
  14. import time;  
  15. #冒泡排序  
  16. def BubbleSort(array):  
  17.     for i in range(0,len(array)):  
  18.         flag = True;  
  19.         for j in range(i,0,-1):  
  20.             if array[j] < array[j-1]:  
  21.                 array[j-1], array[j] = array[j], array[j-1];  
  22.                 flag = False;  
  23.             if flag :  
  24.                 break;  
  25. #选择排序  
  26. def SelectSort(array):  
  27.     for i in range(0, len(array)):  
  28.         pMin = i;  
  29.         for j in range(i+1, len(array)):  
  30.             if array[j] < array[pMin]:  
  31.                 pMin = j;  
  32.         if pMin != i :  
  33.             array[i], array[pMin] = array[pMin], array[i];  
  34. #插入排序  
  35. def InsertSort(array):  
  36.     for i in range(1, len(array)):  
  37.         for j in range(i,0,-1):  
  38.             if array[j] < array[j-1]:  
  39.                 array[j],array[j-1] = array[j-1],array[j];  
  40.             else:  
  41.                 break;  
#--coding: utf8--
    
def insertion_sort(arr):
        arrlen = len(arr)
        for i in range(1, arrlen):
            insert(arr, i)
    
def insert(arr, i):
        tmp = arr[i]
        j = i
        # 查找第i的元素应该的位置, 并且
        # 顺便把比它大的元素往后挪 -- 因为
        # 总是要挪的, 看似很小的一个东西
        # 其实是用了心思在里面的
        while j > 0 and tmp < arr[j - 1]:
            arr[j] = arr[j - 1]
            j -= 1
# 把第i个元素放到我们查找的正确位置
arr[j] = tmp
  1. #快速排序  
  2. def partition(array, left, right):  
  3.     mid = (left + right) / 2;  
  4.     tmp = array[mid];  
  5.     i = left;  
  6.     j = right;  
  7.     while(True):  
  8.         if i == j:  
  9.             array[i] = tmp;  
  10.             return i;  
  11.         if array[i] > tmp:  
  12.             array[i] = array[j];  
  13.             j = j - 1;  
  14.             break;  
  15.         i = i + 1;  
  16.     while(True):  
  17.         if i == j:  
  18.             array[i] = tmp;  
  19.             return i;  
  20.         if array[j] < tmp:  
  21.             array[j] = array[i];  
  22.             i = i - 1;  
  23.             break;  
  24.         j = j - 1;  
  25. def quickSort(array, left, right):  
  26.     if left >= right:  
  27.         pivot = partition(array, left, right);  
  28.         quickSort(array,left, pivot - 1);  
  29.         quickSort(array, pivot + 1, right);  
  30. def QuickSort(array):  
  31.     quickSort(array, 0, len(array) - 1);  
  32. #希尔排序  
  33. def ShellSort(array):  
  34.     delta = int(len(array) / 2);  
  35.     while delta > 0:  
  36.         for i in range(0, delta):  
  37.             for j in range(i + delta, len(array), delta):  
  38.                 for k in range(j, 0, -delta):  
  39.                     if array[k] < array[k-delta]:  
  40.                         array[k],array[k-delta] = array[k-delta],array[k];  
  41.         delta = int(delta / 2);  
  42. #归并排序  
  43. def merge(array, left, right, middle):  
  44.     i = left;  
  45.     j = middle + 1;  
  46.     tmp = [];  
  47.     while i <= middle and j <= right:  
  48.         if array[i] < array[j]:  
  49.             tmp.append(array[i]);  
  50.             i = i + 1;  
  51.         else:  
  52.             tmp.append(array[j]);  
  53.             j = j + 1;  
  54.     while i <= middle:  
  55.         tmp.append(array[i]);  
  56.         i = i + 1;  
  57.     while j <= right:  
  58.         tmp.append(array[j]);  
  59.         j = j + 1;  
  60.     array[left : right] = tmp[0 : -1]; #此处不能写成array[left : right] = tmp;  
  61. def mergeSort(array, left, right):  
  62.     if left < right:  
  63.         middle = int((left + right) / 2);  
  64.         mergeSort(array, left, middle);  
  65.         mergeSort(array, middle + 1, right);  
  66.         merge(array, left, right, middle);  
  67. def MergeSort(array):  
  68.     mergeSort(array, 0, len(array) - 1);  
  69. #堆排序  
  70. def heapAdjust(array, s, e):  
  71.     tmp = array[s];  
  72.     i = s * 2;  
  73.     while i <= e:  
  74.         if i + 1 <= e and array[i] < array[i+1]:  
  75.             i = i + 1;  
  76.         if array[i] < array[s]:  
  77.             array[s] = array[i];  
  78.             i = s;  
  79.         else:  
  80.             break;  
  81.         i = i * 2;  
  82.     array[s] = tmp;  
  83. def HeapSort(array):  
  84.     for i in (int((len(array) - 1)/2), 0, -1):  
  85.         heapAdjust(array, i, len(array) - 1);  
  86.     for i in (len(array) - 10, -1):  
  87.         array[i], array[0] = array[0], array[i];  
  88.         heapAdjust(array, 0, i);  
  89. #数据生成  
  90. def RandomNumGenerate(n):  
  91.     data = [];  
  92.     for i in range(0,n):  
  93.         data.append(random.randint(0,1000));  
  94.     return data;  
  评论这张
 
阅读(191)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018