首页 > 其他分享 >排序整合(1)

排序整合(1)

时间:2022-11-26 22:33:49浏览次数:37  
标签:arr right 元素 整合 序列 排序 left

冒泡排序

基本思想
第 i (i = 1, 2, …) 趟排序时从序列中前 n - i + 1 个元素的第 1 个元素开始,相邻两个元素进行比较,若前者大于后者,两者交换位置,否则不交换。

代码实现

 def bubbleSort(self, arr):
     # 第 i 趟排序
     for i in range(len(arr)):
         # 从序列中前 n - i + 1 个元素的第 1 个元素开始,相邻两个元素进行比较
         for j in range(len(arr) - i - 1):
             # 相邻两个元素进行比较,如果前者大于后者,则交换位置
             if arr[j] > arr[j + 1]:
                 arr[j], arr[j + 1] = arr[j + 1], arr[j]

     return arr
时间复杂度 O(n^2)

选择排序

基本思想
将序列分为两部分:前边 i - 1 个元素为已排序部分,后边 n - i + 1 个元素为未排序部分。第 i 趟排序从未排序部分 n − i + 1 (i = 1, 2, …, n − 1) 个元素中选择一个值最小的元素与未排序部分最前面那个元素交换位置,即与整个序列的第 i 个位置上的元素交换位置。如此下去,直到所有元素都变为已排序部分,排序结束。

代码实现

class Solution:
    def selectionSort(self, arr):
        for i in range(len(arr) - 1):
            # 记录未排序部分中最小值的位置
            min_i = i
            for j in range(i + 1, len(arr)):
                if arr[j] < arr[min_i]:
                    min_i = j
            # 如果找到最小值的位置,将 i 位置上元素与最小值位置上的元素进行交换
            if i != min_i:
                arr[i], arr[min_i] = arr[min_i], arr[i]
        return arr
时间复杂度O(n^2)

插入排序

基本思想:
把待排数组分成已排序的前i个和未排序的后n-i两部分,每次排序就把未排序部分的第一个找到其在已排序部分的位置。
代码实现:

class Solution:
    def insertionSort(self, arr):
        # 遍历无序序列
        for i in range(1, len(arr)):
            temp = arr[i]
            j = i
            # 从右至左遍历有序序列
            while j > 0 and arr[j - 1] > temp:
                # 将有序序列中插入位置右侧的元素依次右移一位
                arr[j] = arr[j - 1]
                j -= 1
            # 将该元素插入到适当位置
            arr[j] = temp
        return arr
		
时间复杂度O(n^2) 理想情况下是O(n)

希尔排序

基本思想
将整个序列切按照一定的间隔取值划分为若干个子序列,每个子序列分别进行插入排序。然后逐渐缩小间隔进行下一轮划分子序列和对子序列进行插入排序。直至最后一轮排序间隔为 1,对整个序列进行插入排序。
代码实现

class Solution:
    def shellSort(self, arr):
        size = len(arr)
        gap = size // 2
		# 按照 gap 分组
        while gap > 0:
            # 对每组元素进行插入排序
            for i in range(gap, size):
                # temp 为每组中无序序列第 1 个元素
                temp = arr[i]
                j = i
                # 从右至左遍历每组中的有序序列元素
                while j >= gap and arr[j - gap] > temp:
                    # 将每组有序序列中插入位置右侧的元素依次在组中右移一位
                    arr[j] = arr[j - gap]
                    j -= gap
                # 将该元素插入到适当位置
                arr[j] = temp
            # 缩小 gap 间隔
            gap = gap // 2
        return arr
时间复杂度:介于O(nlogn)  与O(n^2)  之间。

归并排序

基本思想
采用经典的分治策略,先递归地将当前序列平均分成两半。然后将有序序列两两合并,最终合并成一个有序序列。
代码实现

class Solution:
    def merge(self, left_arr, right_arr):           # 归并过程
        arr = []
        left_i, right_i = 0, 0
        while left_i < len(left_arr) and right_i < len(right_arr):
            # 将两个有序子序列中较小元素依次插入到结果数组中
            if left_arr[left_i] < right_arr[right_i]:
                arr.append(left_arr[left_i])
                left_i += 1
            else:
                arr.append(right_arr[right_i])
                right_i += 1
        
        while left_i < len(left_arr):
            # 如果左子序列有剩余元素,则将其插入到结果数组中
            arr.append(left_arr[left_i])
            left_i += 1
            
        while right_i < len(right_arr):
            # 如果右子序列有剩余元素,则将其插入到结果数组中
            arr.append(right_arr[right_i])
            right_i += 1
        
        return arr                                  # 返回排好序的结果数组

    def mergeSort(self, arr):                       # 分割过程
        if len(arr) <= 1:                           # 数组元素个数小于等于 1 时,直接返回原数组
            return arr
        
        mid = len(arr) // 2                         # 将数组从中间位置分为左右两个数组。
        left_arr = self.mergeSort(arr[0: mid])      # 递归将左子序列进行分割和排序
        right_arr =  self.mergeSort(arr[mid:])      # 递归将右子序列进行分割和排序
        return self.merge(left_arr, right_arr)      # 把当前序列组中有序子序列逐层向上,进行两两合并。

   

标签:arr,right,元素,整合,序列,排序,left
From: https://www.cnblogs.com/habc706/p/16928513.html

相关文章

  • Failed to load ApplicationContext-myBatis注解与整合
    严重:CaughtexceptionwhileallowingTestExecutionListener[org.springframework.test.context.support.DependencyInjectionTestExecutionListener@21213b92]topre......
  • 基于桶的排序之计数排序
    基于桶的排序之计数排序作者:Grey原文地址:博客园:基于桶的排序之计数排序CSDN:基于桶的排序之计数排序说明基于桶的排序有两种,分别是计数排序和基数排序。但是这两种排......
  • spring boot整合spring security 前后端分离
    1.springsecurity的介绍springsecurity是一个安全管理框架,源自Spring家族,可以和Spring框架无缝整合。其主要功能有:认证也就是你进行访问一些网站的时候需要进行......
  • java实现扑克牌游戏(洗牌,发牌,排序)
    packagepoker.bean;importlombok.AllArgsConstructor;importlombok.Getter;importlombok.NoArgsConstructor;importlombok.Setter;importjava.lang.annotatio......
  • 力扣153(java&python)-寻找旋转排序数组中的最小值(中等)
    题目:已知一个长度为n的数组,预先按照升序排列,经由1到n次旋转后,得到输入数组。例如,原数组nums=[0,1,2,4,5,6,7]在变化后可能得到:若旋转4次,则可以得到[4,5,6,......
  • SpringBoot整合Alibaba-Dubbo和Apache-Dubbo
    目录1Alibaba整合Dubbo1.1服务提供者1.1.1服务提供者接口1.1.2服务提供者实现类1.1.2.1项目结构图1.1.2.2pom.xml1.1.2.3服务实现类1.1.2.4配置文件1.1.2.5启动类......
  • Spring--整合JUnit
    整合JUnit导入两个依赖在MyBatis的基础上进行JUit的整合在Maven项目里面自带的test文件夹里面新建一个.java文件,当作测试文件也就是上图中的这么一个结构使用注解,......
  • sort自然排序顺序
    1、问题:fs读取文件夹文件的时候,有时顺序是乱的   而实际想要的顺序是这样的2、思路:主要通过js的数组中的sort方法来处理利用replace正则区分数字与非数字来遍历......
  • [拓扑排序 反向建图] 825E - Minimal Labels
    [拓扑排序编号字典序最小]825E-MinimalLabels题目​​题目链接​​思路这题答案要求节点编号越小,打上的标签越小,即编号序列字典序最小,而非拓扑序列字典序最小。想让当......
  • SQL语句查询关键字:where筛选、group by分组、distinc去重、order by排序、limit分页
    目录SQL语句查询关键字前期数据准备编写SQL语句的小技巧查询关键字之where筛选查询关键字之groupby分组查询关键字之having过滤查询关键字值distinct去重查询关键字值orde......