茉莉Python

voidqueens@hotmail.com

0%

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

一、冒泡排序

一、思想

每次比较两个相邻的元素,如果他们之前的顺序不符就交换位置。
比如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))

`