本文隶属于分类

编程语言

广告推荐

技术交流学习或者有任何问题欢迎加群

编程技术交流群 : 154514123 爱上编程      Java技术交流群 : 6128790  Java

标签:归并   range   排序算法   列表   tint   算法   找到   clas   迭代   

1.使用内置函数list.sort()

1 class Solution:
2     """
3     @param: A: an integer array
4     @return: 
5     """
6     def sortIntegers(self, A):
7         A.sort()

2.使用sorted() 函数

1 sorted([5, 2, 3, 1, 4])
2 [1, 2, 3, 4, 5]

注:

sorted()与list.sort()的不同

  1)list.sort() 方法返回none,sorted()返回结果

  2)list.sort() 方法只可以供列表使用,而 sorted() 函数可以接受任意可迭代对象(iterable)

1 sorted({1: D, 2: B, 3: B, 4: E, 5: A})
2 [1, 2, 3, 4, 5]

 

3.插入排序法

 1 def insert_sort(lists):
 2     # 插入排序
 3     count = len(lists)
 4     for i in range(1, count):
 5         key = lists[i]
 6         j = i - 1
 7         while j >= 0:
 8             if lists[j] > key:
 9                 lists[j + 1] = lists[j]
10                 lists[j] = key
11             j -= 1
12     return lists

适用于少量数据的排序,时间复杂度为O(n^2),逐个向前遍历

 

4.希尔排序

 1 def shell_sort(lists):
 2     # 希尔排序
 3     count = len(lists)
 4     step = 2
 5     group = count / step
 6     while group > 0:
 7         for i in range(0, group):
 8             j = i + group
 9             while j < count:
10                 k = j - group
11                 key = lists[j]
12                 while k >= 0:
13                     if lists[k] > key:
14                         lists[k + group] = lists[k]
15                         lists[k] = key
16                     k -= group
17                 j += group
18         group /= step
19     return lists

首先增量为2,分成len()/2组,两两比较

然后减小增量分成len()/2/2组,每组内比较

直到分成一组,排序完成

其中以    插入排序+分组   实现

时间复杂度O(n^1.3)

 

5.冒泡排序

1 def bubble_sort(lists):
2     # 冒泡排序
3     count = len(lists)
4     for i in range(0, count):
5         for j in range(i + 1, count):
6             if lists[i] > lists[j]:
7                 lists[i], lists[j] = lists[j], lists[i]
8     return lists

一次比较两个元素,时间复杂度O(n)

 

6.快速排序

 1 def quick_sort(lists, left, right):
 2     # 快速排序
 3     if left >= right:
 4         return lists
 5     key = lists[left]
 6     low = left
 7     high = right
 8     while left < right:
 9         while left < right and lists[right] >= key:
10             right -= 1
11         lists[left] = lists[right]
12         while left < right and lists[left] <= key:
13             left += 1
14         lists[right] = lists[left]
15     lists[right] = key
16     quick_sort(lists, low, left - 1)
17     quick_sort(lists, left + 1, high)
18     return lists

low = left;high = right; 将基准数挖出形成第一个坑key。

right --由后向前找比它小的数,找到后挖出此数填前一个坑key中。

left ++由前向后找比它大的数,找到后也挖出此数填到前一个坑key中。

再重复执行2,3二步,直到left=right,将基准数填入a[i]中。

-----------------------------------------------------------------------------------存疑

 

7.直接选择排序

 1 def select_sort(lists):
 2     # 选择排序
 3     count = len(lists)
 4     for i in range(0, count):
 5         min = i
 6         for j in range(i + 1, count):
 7             if lists[min] > lists[j]:
 8                 min = j
 9         lists[min], lists[i] = lists[i], lists[min]
10     return lists

先把数列中最小的一个数放在第一个位置,再遍历第二小的数放在第二个位置,以此类推

 

堆排序,归并排序,基数排序存疑,以后再看

相关连接:

http://blog.jobbole.com/11745/

视觉直观感受 7 种常用的排序算法

http://python.jobbole.com/82270/

八大排序算法的python实现

python中-----数组中的排序

标签:归并   range   排序算法   列表   tint   算法   找到   clas   迭代   

原文:https://www.cnblogs.com/xnwjx/p/8352676.html

技术交流学习或者有任何问题欢迎加群

编程技术交流群 : 154514123 爱上编程      Java技术交流群 : 6128790  Java

广告推荐

讨论区