Python 数据结构之十大经典排序算法一文通关

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

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

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 arr

def 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-1

def 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、桶排序

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

算法演示

算法步骤

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

算法实现

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;
}

到此这篇关于Python 数据结构之十大经典排序算法一文通关的文章就介绍到这了,更多相关Python 排序算法内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家！

原文链接：https://blog.csdn.net/weixin_44586883/article/details/120715016