一、冒泡排序
https://www.cnblogs.com/heyuquan/p/bubble-quick-sort.html
一、思想
每次比较两个相邻的元素,如果他们之前的顺序不符就交换位置。
比如5个数从小到大排序,23,64,1,43,21
第一趟:
第一次比较:23,64,1,43,21
第二次比较:23,1,64,43,21
第三次比较:23,1,43,64,21
第四次比较:23,1,43,21,64
经过第一趟的比较后,最大的数字已经到最后面了,接下来只需要比较前四个数字,以此类推。
第二趟:1,23,21,43,64
第三趟:1,21,23,43,64
第四趟:1,21,23,43,64
冒泡排序每一趟只能对一个数进行归位,如果是n个数进行排序,则需要将n-1个数归位,即n-1趟操作
冒泡排序解决了桶排序浪费空间的问题,但是它效率很低。
时间复杂度:O(n^2)
二、用Python实现
`
#!/usr/bin/env python
# coding:utf-8
def bubbleSort(nums):
for i in range(len(nums) - 1):
for j in range(len(nums) - i - 1):
if nums[j] > nums[j + 1]:
nums[j], nums[j + 1] = nums[j + 1], nums[j]
return nums
nums = [5, 6, 3, 1, 6, 2, 5, 33, 3]
print(bubbleSort(nums))
`
二、选择排序
一、思想
第1趟,在待排序记录r1 ~ r[n]中选出最小的记录,将它与r1交换;
第2趟,在待排序记录r2 ~ r[n]中选出最小的记录,将它与r2交换;
以此类推,第i趟在待排序记录r[i] ~ r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。
原始数据:[3,1,0,8,4,2]
第一趟:[0,1,3,8,4,2]
第二趟:[0,1,3,8,4,2]
第三趟:[0,1,2,8,4,3]
第四趟:[0,1,2,3,4,8]
第五趟:[0,1,2,3,4,8]
二、用Python实现选择排序
`
def selectSort(nums):
for i in range(len(nums)-1):
print(i)
min = i
for j in range(i + 1, len(nums)):
if nums[min] > nums[j]:
min = j
nums[i], nums[min] = nums[min], nums[i]
return nums`
三、插入排序
一、思想
插入排序原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。
其基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据,算法适用于少量数据的排序,是稳定的排
序方法。
时间复杂度为O(n^2)。
二、步骤
1. 从第一个元素开始,该元素可以认为已经被排序
2. 取出下一个元素,在已经排序的元素序列中从后向前扫描
3. 如果该元素(已排序)大于新元素,将该元素移到下一位置
4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该位置后
6. 重复步骤2~5
二、用Python实现插入排序
`
#!/usr/bin/env python
# coding:utf-8
def insertSort(lists):
for i in range(1, len(lists)):
key = lists[i]
j = i - 1
while j >= 0:
if lists[j] > key:
lists[j + 1] = lists[j]
lists[j] = key
j -= 1
return lists
lists = [4, 6, 2, 4, 7, 3, 9, 2, 1]
print(insertSort(lists))
`
四、快速排序
一、思想
快速排序是对冒泡排序的一种改进,其基本思想是通过一趟排序将待排序记录分割成独立的两部分,一种一部分记录的关键字均比另一部分记录的关键字小,最后再分别对这两部分记录继续进行排序,以达到整个序列有序。
一趟快读排序的具体做法是:附设两个指针low和high,初值分别为low和high,设枢轴记录关键字为pivotkey,则首先从high所指位置向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录相互交换,然后从low所指位置起向后搜索,找到第一个关键字大于pivotkey的记录和枢轴记录相互交换,重复这两步直到low=high为止,过程如图:
二、用Python实现快速排序
`
#!/usr/bin/env python
# coding:utf-8
def quickSort(lists, left, right):
if left >= right:
return lists
key = lists[left]
low = left
high = right
print("111")
while left < right:
while (left < right and lists[right] >= key):
right -= 1
lists[left] = lists[right]
while (left < right and lists[left] <= key):
left += 1
lists[right] = lists[left]
lists[left] = key
print("key")
quickSort(lists, low, left - 1)
quickSort(lists, left + 1, high)
return lists
lists = [59, 3, 6, 3, 46]
print(quickSort(x, 0, 4))
`
def partition(arr, low, high):
i = low-1
pivot = arr[high]
for j in range(low,high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[high] = arr[high], arr[i+1]
return i+1
def quickSort(arr, low, high):
if low<high:
pi = partition(arr, low, high)
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
return arr
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
print(quickSort(arr,0,len(arr)-1))
五、归并排序
时间复杂度:O(nlogn)
空间复杂度:O(n)
https://www.cnblogs.com/JMWan233/p/11175006.html
大文件排序:https://www.cnblogs.com/dream-of-cambridge/articles/8042311.html
5.1 递归
def mergeSort(arr):
if len(arr) < 2:
return arr
mid = len(arr)//2
left, right = arr[0:mid], arr[mid:]
return merge(mergeSort(left), mergeSort(right))
def merge(left, right):
result = []
while left and right:
if left[0] < right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
while left:
result.append(left.pop(0))
while right:
result.append(right.pop(0))
return result
print(mergeSort([1, 7, 5, 6, 9, 0, 10, 20, ]))
5.3 多路归并
https://www.cnblogs.com/dream-of-cambridge/articles/8046031.html