茉莉Python

voidqueens@hotmail.com

0%

数据结构与算法-14-排序

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/solution/ge-chong-pai-xu-suan-fa-tu-xie-zong-jie-by-ke-ai-x/

一、冒泡排序

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为止,过程如图:

https://gypsy-1255824480.cos.ap-beijing.myqcloud.com/blog/quickSort.jpg

二、用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, ]))

http://10.160.59.114/web/searchList.jsp?v=5&from=index&pid=sogou-waps-7880d7226e872b77&w=1274&t=1607593533262&s_t=1607593620931&s_from=index&pg=webSearchList&inter_index=&keyword=baidu&suguuid=ec4c985f-a61f-4638-bf33-c45a765ae712&sugsuv=&sugtime=1607593620931&dump=1

http://10.160.67.72/web?query=baidu&_asf=www.sogou.com&_ast=&w=01019900&p=40040100&ie=utf8&from=index-nologin&s_from=index&sut=13051&sst0=1607593834109&lkt=2%2C1607593832605%2C1607593832773&sugsuv=&sugtime=1607593834109&dump=1

5.3 多路归并

https://www.cnblogs.com/dream-of-cambridge/articles/8046031.html

六、桶排序

http://www.chenxm.cc/article/981.html