美文网首页
排序算法

排序算法

作者: 晨光523152 | 来源:发表于2020-07-11 17:48 被阅读0次

常考排序

  • 快速排序
def quickSort(iList):
      if len(iList) <= 1:
             return iList
      mid = len(iList) // 2
      left = []
      right = []
      for i in range(1,len(iList)):
            if iList[0] < iList[i]:
                   right.append(iList[i])
            else:
                   left.append(iList[i])
      return quickSort(left) + [iList[0]] + quickSort(right)
n = int(input())
nums = list(map(int,input().split()))

def quick_sort(q, l, r):
    
    if l >= r:
        return
    
    mid = (l + r) // 2
    x = q[mid]
    i = l - 1
    j = r + 1
    
    while i < j:
        while True:
            i += 1
            if q[i] >= x:
                break
        while True:
            j -= 1
            if q[j] <= x:
                break
        if i < j:
            q[i], q[j] = q[j], q[i]
    quick_sort(q, l, j)
    quick_sort(q, j + 1, r)

quick_sort(nums,0,n-1)
print(' '.join(list(map(str, nums))))
  • 归并排序
def mergeSort(nums):
       if len(nums) <=1 :
              return nums
       mid = len(nums) // 2
       left = mergeSort(nums[:mid])
       right = mergeSort(nums[mid:])
       return merge(left,right)

def merge(left,right):
       i,j,temp = 0,0,[]
       while i < len(left) and j < len(right):
           if left[i] > right[j]:
               temp.append(right[j])
                j += 1
          else:
               temp.append(right[i])
               i += 1
       temp = temp + left[i:]
       temp = temp + right[j:]
       return temp
  • 归并排序求逆序数对
class Solution(object):
    def reversePairs(self, nums) -> int:
        if not nums:
            return 0
        self.count = 0
        def merge(nums):
            if len(nums) == 1:
                return nums
            mid = len(nums) // 2
            left = nums[:mid]
            right = nums[mid:]
            left = merge(left)
            right = merge(right)
            return mergeSort(left, right)

        def mergeSort(left,right):
            temp = []
            i, j = 0, 0
            while i < len(left) and j < len(right):
                if left[i] <= right[j]:
                    temp.append(left[i])
                    i += 1
                else:
                    temp.append(right[j])
                    self.count += len(left) - i  ###!!!!!
                    j += 1
            temp += left[i:]
            temp += right[j:]
            return temp
        merge(nums)
        return self.count
  • 堆排序

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

堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:子结点的键值或索引总是小于(或者大于)它的父节点。

直接使用 from heapq import heapify 实现最小堆。

def heapSort(nums):
      n = len(nums)
      for i in range(n,-1,-1):
              heapify(nums,n,i)
      for i in range(n-1,0,-1):
              nums[0],nums[i] = nums[i],nums[0]
              heapify(nums,n,0)
def heapify(nums,n,i):
       largest = i
       l = 2 * i + 1
       r = 2 * i + 2
       if l < n and nums[i] < nums[l]:
               largest = l
       if r < n and nums[largest] < nums[r]:
               largegst = r
       if largest != i:
               nums[i], nums[largest] = nums[largest], nums[i]
               heapify(nums,n,largest)

参考资料:
https://www.runoob.com/python3/python-heap-sort.html

https://greyireland.gitbook.io/algorithm-pattern/ji-chu-suan-fa-pian/sort

https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/

相关文章

  • java实现快速排序、归并排序、希尔排序、基数排序算法...

    快速排序算法 归并排序算法 希尔排序算法 基数排序算法

  • web开发需要知道的几个算法

    算法分类 快速排序算法 深度优先算法 广度优先算法 堆排序算法 归并排序算法

  • 算法学习(1)-排序算法

    八大排序算法九大排序算法再总结[经典排序算法][集锦][直观学习排序算法] 视觉直观感受若干常用排序算法 快速排序...

  • 经典排序算法总结

    经典排序算法集锦 冒泡法 排序算法入门之冒泡排序 排序算法入门之冒泡排序优化

  • 前端算法学习-第一篇

    冒泡排序算法 冒泡排序算法是最慢的排序算法之一,也是最容易实现的排序算法。之所以叫冒泡排序是因为使用这种算法排序时...

  • 七大排序算法之冒泡排序

    七大排序算法之冒泡排序 @(算法笔记)[排序算法, 冒泡排序, C++实现] 冒泡排序介绍 冒泡排序是七大排序算法...

  • 算法-选择排序

    算 法:选择排序算法时间复杂度: 选择排序算法概述 选择排序伪代码 选择排序实现 选择排序算法概述 排序算法有许...

  • 浅谈排序算法

    排序算法有很多种,今天先谈谈一些简单的排序算法。包括桶排序、冒泡排序和快速排序算法。后期总结各种排序算法。 桶排序...

  • 线性排序

    桶排序、计数排序、基数排序 一、线性排序算法介绍 1.线性排序算法包括桶排序、计数排序、基数排序。2.线性排序算法...

  • 算法4:插入排序和选择排序算法的比较

    排序算法列表电梯: 选择排序算法:详见 《算法4》2.1 - 选择排序算法(Selection Sort), Py...

网友评论

      本文标题:排序算法

      本文链接:https://www.haomeiwen.com/subject/hvsicktx.html