十大经典排序算法

总览

image-20230514145515237

image-20230514145444586

名词解释

• n：数据规模
• k："桶"的个数
• In-place：占用常数内存，不占用额外内存
• Out-place：占用额外内存
• 稳定性：排序后 2 个相等键值的顺序和排序之前它们的顺序相同

冒泡排序

算法步骤

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
• 针对所有的元素重复以上的步骤，除了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动图展示

img

最快情况

当输入的数据已经是正序时

最慢情况

当输入的数据是反序时

代码实现

JavaScript

function bubbleSort(arr) {
    var len = arr.length;
    // 每次遍历确定一位最大值，所以最后一位不用操作
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
         		// 相邻元素两两对比
            if (arr[j] > arr[j+1]) {   
            		// 元素交换
                var temp = arr[j+1];        
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

Python

def bubbleSort(arr):
    for i in range(1, len(arr)):
        for j in range(0, len(arr)-i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

参考链接

• 十大经典排序算法