目录

  1. 排序
    1. 概述
    2. 冒泡排序
    3. 选择排序
    4. 插入排序
    5. 希尔排序
    6. 归并排序
    7. 快速排序
    8. 堆排序

排序

概述

排序算法划分方法有：稳定性，内外排序，时间复杂复杂度和空间复杂度。

  • 按照稳定性划分，稳定排序，如果a原本在b前面，而a=b，排序之后a仍然在b的前面；而不稳定可能出现在b之后。

  • 按照内外排序划分，内排序，所有排序操作都在内存中完成；外排序 ：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；

  • 按照时间复杂度、空间复杂度划分，时间复杂度是指运行时间，空间复杂度运行完一个程序所需内存的大小。

冒泡排序

冒泡排序的基本过程，就是，比较两个相邻元素的大小，并根据是升序还是降序，交换位置，直到将最大值或者最小值，放到数组末尾，同时将比较范围缩小。

时间复杂度O(n^2)，空间复杂度O(1)，稳定，内排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution(object):
    def bubble_sort(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        length = len(nums)
        for i in range(0, length - 1):
            for j in range(0, length - 1 - x):
                if nums[j] > nums[j + 1]:
                    nums[j], nums[j + 1] = nums[j + 1], nums[j]
        return nums

选择排序

和冒泡排序类似，选择排序算法在排序的过程中每次遍历时，都将最大值或者最小值（取决是升序还是降序）放置列表前面，再遍历剩下的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution(object):
    def selection_sort(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i, len(nums)):
                if nums[i] > nums[j]:
                    nums[i], nums[j] = nums[j], nums[i]    
        return nums

时间复杂度O(n^2)，空间复杂度O(1)，稳定，内排序。

插入排序

插入排序的思想就是将后一个元素插入到前面已经排序好的列表中。

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution(object):
    def insertion_sort(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        for i in in range(1, len(nums)):
            while i and nums[i] < nums[i - 1]:
                nums[i], nums[i - 1] = nums[i - 1], nums[i]
                i -= 1
        return nums

时间复杂度O(n^2)，空间复杂度O(1)，稳定，内排序。

希尔排序

希尔排序是插入排序的改进版，也称为缩小增量排序。

希尔排序是把列表元素按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个列表元素恰被分成一组，算法便终止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution(object):
    def shell_sort(nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        length = len(nums)
        gap = length // 2
        while gap:
            for i in range(gap, length):
                while i - gap >=0 and nums[i - gap] > nums[i]:
                    nums[i - gap], nums[i] = nums[i], nums[i - gap]
                    i -= gap
            gap //= 2
        return nums

平均算法时间复杂度是O(n log n)，最坏情况时间复杂度O(n^2)，空间复杂度O(1)，不稳定，内排序。

归并排序

归并排序，采用是分治法，先将数组分成子序列，让子序列有序，再将子序列间有序，合并成有序数组。

  1. 把长度为n的输入序列分成长度n/2的子序列；
  2. 对两个子序列采用归并排序；
  3. 合并所有子序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

class Solution(object):
    def merge_sort(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if len(nums) <= 1:
            return nums
        mid = len(nums) // 2
        left = self.merge_sort(nums[:mid])
        right = self.merge_sort(nums[mid:])
        return self.merge(left, right)

    def merge(self, left, right):
        result = []
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                result.append(left[i])
                i += 1
            else: 
                result.append(right[j])
                j += 1
        result += left[i:]
        result += right[j:]
        return result
    
    def merge_sort2(nums, l, r):
        if l == r:
            return
        mid = (l + r ) // 2
        self.merge_sort2(nums, l, mid)
        self.merge_sort2(nums, mid + 1, r)
        temp = []
        i = l
        j = mid + 1
        while i <= mid or j <= r:
            if i > mid or (j <= r and nums[j] < nums[i]):
                temp.append(nums[j])
                j += 1
            else:
                temp.append(nums[i])
                i += 1
        nums[l : r + 1] = temp
    
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        return self.merge_sort2(nums, 0, len(nums) - 1)

算法时间复杂度是O(n log n)，空间复杂度O(n)，稳定，外排序。

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        self.quick_sort(nums, 0, len(nums) - 1)
        retrun nums

    def quick_sort(self, nums, l, r):
        if l >= r:
            return
        left = l
        right = r
        piovt = nums[l]
        while left < right:
            while left < right and nums[right] >= piovt:
                right -= 1
            nums[left] = nums[right]
            while left < right and nums[left] <= piovt:
                left += 1
            nums[right] = nums[left]
        
        nums[left] = piovt
        self.quick_sort(nums, l, right - 1)
        self.quick_sort(nums, left + 1, l)

算法时间复杂度是O(n log n)，空间复杂度O(1)，不稳定，内排序。

堆排序

1
2
3
4
5
6
7
8

class Solution(object):
    def sortArray(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """