一文搞掂十大经典排序算法

今天整理一下十大经典排序算法。

1、冒泡排序

——越小的元素会经由交换慢慢“浮”到数列的顶端

算法演示

算法步骤

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

算法实现

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

2、选择排序

—— 最小的出来排第一，第二小的出来排第二…

算法演示

算法步骤

• 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
• 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
• 重复第二步，直到所有元素均排序完毕。

算法实现

def selectionSort(arr):    for i in range(len(arr) - 1):        # 记录最小数的索引        minIndex = i        for j in range(i + 1, len(arr)):            if arr[j] < arr[minIndex]:                minIndex = j        # i 不是最小数时，将 i 和最小数进行交换        if i != minIndex:            arr[i], arr[minIndex] = arr[minIndex], arr[i]    return arr

3、简单插入排序

——通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法演示

算法步骤

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

算法实现

def insertionSort(arr):    for i in range(len(arr)):        preIndex = i-1        current = arr[i]        while preIndex >= 0 and arr[preIndex] > current:            arr[preIndex+1] = arr[preIndex]            preIndex-=1        arr[preIndex+1] = current    return arr

4、希尔排序

——希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。

算法演示

算法步骤

• 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
• 按增量序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法实现

def shellSort(arr):    import math    gap=1    while(gap < len(arr)/3):        gap = gap*3+1    while gap > 0:        for i in range(gap,len(arr)):            temp = arr[i]            j = i-gap            while j >=0 and arr[j] > temp:                arr[j+gap]=arr[j]                j-=gap            arr[j+gap] = temp        gap = math.floor(gap/3)    return arr

5、归并排序

——建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

算法演示

算法步骤

• 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
• 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
• 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
• 重复步骤 3 直到某一指针达到序列尾；
• 将另一序列剩下的所有元素直接复制到合并序列尾。

算法实现

def mergeSort(arr):    import math    if(len(arr)<2):        return arr    middle = math.floor(len(arr)/2)    left, right = arr[0:middle], arr[middle:]    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

6、快速排序

——快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。 快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

算法演示

算法步骤

• 从数列中挑出一个元素，称为 “基准”（pivot）;
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
• 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

算法实现

def quickSort(arr, left=None, right=None):    left = 0 if not isinstance(left,(int, float)) else left    right = len(arr)-1 if not isinstance(right,(int, float)) else right    if left < right:        partitionIndex = partition(arr, left, right)        quickSort(arr, left, partitionIndex-1)        quickSort(arr, partitionIndex+1, right)    return arrdef partition(arr, left, right):    pivot = left    index = pivot+1    i = index    while  i <= right:        if arr[i] < arr[pivot]:            swap(arr, i, index)            index+=1        i+=1    swap(arr,pivot,index-1)    return index-1def swap(arr, i, j):    arr[i], arr[j] = arr[j], arr[i]   

7、堆排序

——利用堆这种数据结构所设计的一种排序算法

算法演示

算法步骤

• 创建一个堆 H[0……n-1]；
• 把堆首（最大值）和堆尾互换；
• 把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；
• 重复步骤 2，直到堆的尺寸为 1。

算法实现

def buildMaxHeap(arr):    import math    for i in range(math.floor(len(arr)/2),-1,-1):        heapify(arr,i)def heapify(arr, i):    left = 2*i+1    right = 2*i+2    largest = i    if left < arrLen and arr[left] > arr[largest]:        largest = left    if right < arrLen and arr[right] > arr[largest]:        largest = right    if largest != i:        swap(arr, i, largest)        heapify(arr, largest)def swap(arr, i, j):    arr[i], arr[j] = arr[j], arr[i]def heapSort(arr):    global arrLen    arrLen = len(arr)    buildMaxHeap(arr)    for i in range(len(arr)-1,0,-1):        swap(arr,0,i)        arrLen -=1        heapify(arr, 0)    return arr

8、计数排序

——作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法演示

算法步骤

• 找出待排序的数组中最大和最小的元素
• 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
• 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
• 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

算法实现

def countingSort(arr, maxValue):    bucketLen = maxValue+1    bucket = [0]*bucketLen    sortedIndex =0    arrLen = len(arr)    for i in range(arrLen):        if not bucket[arr[i]]:            bucket[arr[i]]=0        bucket[arr[i]]+=1    for j in range(bucketLen):        while bucket[j]>0:            arr[sortedIndex] = j            sortedIndex+=1            bucket[j]-=1    return arr

9、桶排序

——桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。

算法演示

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-9ybEGKPU-1633970885002)(C:/Users/LANWEI~1/AppData/Local/Temp/1633970398356.png)]

算法步骤

• 设置一个定量的数组当作空桶；
• 遍历输入数据，并且把数据一个一个放到对应的桶里去；
• 对每个不是空的桶进行排序；
• 从不是空的桶里把排好序的数据拼接起来。

算法实现

function bucketSort(arr, bucketSize) {    if (arr.length === 0) {      return arr;    }     var i;    var minValue = arr[0];    var maxValue = arr[0];    for (i = 1; i < arr.length; i++) {      if (arr[i] < minValue) {          minValue = arr[i];                // 输入数据的最小值      } else if (arr[i] > maxValue) {          maxValue = arr[i];                // 输入数据的最大值      }    }     // 桶的初始化    var DEFAULT_BUCKET_SIZE = 5;            // 设置桶的默认数量为5    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;      var buckets = new Array(bucketCount);    for (i = 0; i < buckets.length; i++) {        buckets[i] = [];    }     // 利用映射函数将数据分配到各个桶中    for (i = 0; i < arr.length; i++) {        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);    }     arr.length = 0;    for (i = 0; i < buckets.length; i++) {        insertionSort(buckets[i]);                      // 对每个桶进行排序，这里使用了插入排序        for (var j = 0; j < buckets[i].length; j++) {            arr.push(buckets[i][j]);                             }    }     return arr;}

10、基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。

算法演示

算法步骤

• 取得数组中的最大数，并取得位数；
• arr为原始数组，从最低位开始取每个位组成radix数组；
• 对radix进行计数排序（利用计数排序适用于小范围数的特点）；

算法实现

var counter = [];function radixSort(arr, maxDigit) {    var mod = 10;    var dev = 1;    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {        for(var j = 0; j < arr.length; j++) {            var bucket = parseInt((arr[j] % mod) / dev);            if(counter[bucket]==null) {                counter[bucket] = [];            }            counter[bucket].push(arr[j]);        }        var pos = 0;        for(var j = 0; j < counter.length; j++) {            var value = null;            if(counter[j]!=null) {                while ((value = counter[j].shift()) != null) {                      arr[pos++] = value;                }          }        }    }    return arr;}