常用的排序算法整理

冒泡排序

• 原理：从头开始比较相邻的元素。如果第一个比第二个大，则相互交换位置。针对所有元素重复以上步骤，除了最后一个，因为最后一个已经是最大的元素了。

• 时间复杂度

  • 平均时间复杂度：O(n^2)

  • 最好情况：O(n)

  • 最坏情况: O(n^2)

• 空间复杂度: O(1)

实现方式

JS方式

// 冒泡排序
function bubbleSort(arr) {
    const len = arr.length
    for (let i = 0; i < len - 1; ++i) {
        for (let j = 0; j < len - 1 - i; ++j) {
            if (arr[j] > arr[j + 1]) {
                const temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp
            }
        }
    }
    return arr
}

console.log(bubbleSort([2, 3, 1, 6, 5]))//ouput:[1,2,3,5,6]

python方式

# 冒泡排序
def bubbelSort(arr):
    for i in range(0, len(arr) - 1):
        for j in range(0, len(arr) - 1 - i):
            if arr[j] > arr[j + 1]:
                temp = arr[j]
                arr[j] = arr[j + 1]
                arr[j + 1] = temp

    return arr


print(bubbelSort([2, 3, 1, 6, 5]))  # ouput:[1,2,3,5,6]

选择排序

• 原理

  1. 在未排序序列中，找到最小的值，放到未排序序列的起始位置，这个值不再参与下次的排序

  2. 再从剩余未排序元素中找到最小的值，放到未排序序列的起始位置

  3. 重复第2步操作，直至全部元素排序完毕

• 时间复杂度

  • 平均时间复杂度: O(n^2)

  • 最好情况：O(n^2)

  • 最坏情况: O(n^2)

• 空间复杂度

O(1)

实现方式

Js方式

// 快速排序
function selectionSort(arr) {
    const len = arr.length
    let minIndex, temp
    for (let i = 0; i < len - 1; ++i) {
        minIndex = i
        for (let j = i + 1; j < len; ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j
            }
        }
        temp = arr[minIndex]
        arr[minIndex] = arr[i]
        arr[i] = temp
    }
    return arr
}

console.log(selectionSort([2, 3, 1, 6, 5]))//ouput:[1,2,3,5,6]

pthon方式

def selectionSort(arr):
    for i in range(0, len(arr) - 1):
        minIndex = i
        for j in range(i + 1, len(arr)):
            if (arr[j] < arr[minIndex]):
                minIndex = j
        temp = arr[minIndex]
        arr[minIndex] = arr[i]
        arr[i] = temp
    return arr


print(selectionSort([2, 3, 1, 6, 5]))  # ouput:[1,2,3,5,6]

插入排序

• 原理

• 时间复杂度

  • 平均时间复杂度: O(n^2)

  • 最好情况： O(n)

  • 最坏情况: O(n^2)

• 空间复杂度

  O(1)

实现方式

js方式

待更新