首页 > 试题广场 >

排序

[编程题]排序

热度指数：305555 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的数组，请你编写一个函数，返回该数组按升序排序后的结果。

数据范围： $0 \le n \le 1\times10^3$ ，数组中每个元素都满足 $0 \le val \le 10^9$

要求：时间复杂度 $O(n^2)$ ，空间复杂度 $O(n)$

进阶：时间复杂度 $O(nlogn)$ ，空间复杂度 $O(n)$

注：本题数据范围允许绝大部分排序算法，请尝试多种排序算法的实现。

示例1

输入

[5,2,3,1,4]

输出

[1,2,3,4,5]

示例2

输入

[5,1,6,2,5]

输出

[1,2,5,5,6]

算法知识视频讲解

Python

HaochenL

希尔排序

class Solution:

def MySort(self , arr ):
# write code here
n = len(arr)
gap = n//2
while gap > 0:
for i in range(gap,n):
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//2
return arr

发表于 2021-07-13 14:46:01 回复(0)

Python

呀呀哎呀呀

#quicksort

class Solution:
def quickSort(self, arr):
left = 0
right = len(arr)-1
if(left<right):
base = arr[left]
while(left<right):
while(left<right and base <= arr[right]):
right-=1
arr[left] = arr[right]
while(left<right and base >= arr[left]):
left+=1
arr[right] = arr[left]
return self.quickSort(arr[:left])+[base]+self.quickSort(arr[left+1:])
return arr

def MySort(self , arr ):
# write code here
arr = self.quickSort(arr)
return arr

编辑于 2021-07-09 10:47:08 回复(0)

Python

彩鳞

class Solution:
def MySort(self , arr ):
for i in range(len(arr)):
for j in range(len(arr)-1-i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr

发表于 2021-07-08 10:25:42 回复(0)

Python

牛客895086703号

class Solution:
def MySort(self , arr ):
# write code here
return sorted(arr)

发表于 2021-06-21 22:47:18 回复(0)

Python

小洛13

链接：https://www.nowcoder.com/questionTerminal/2baf799ea0594abd974d37139de27896
来源：牛客网
#冒泡排序改进
def bubbleSort(arr):
n = len(arr)
exchange = True
while n - 1 > 0 and exchange:
exchange = False
for j in range(n-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
exchange = True
n -= 1

return arr

#选择排序

def selectSort(arr):
n = len(arr)
for i in range(n):
positionMax = 0
for location in range(n-i):
if arr[location] > arr[positionMax]:
positionMax = location
arr[n-i-1], arr[positionMax] = arr[positionMax], arr[n-i-1]
return arr
#插入排序
def insertSort(arr):
n = len(arr)
for i in range(1, n):
value = arr[i] #取出要插入的值
position = i #记录要插入值的位置，相当于之后要从哪开始做循环
while position > 0 and arr[position-1] > value:
arr[position] = arr[position-1]
position -= 1
arr[position] = value
return arr

#谢尔排序
def shellSort(arr):
n = len(arr)
gap = n//2
while gap > 0:
#每个子列表做插入排序
for start in range(gap):
#单个子列表做插入排序
for i in range(start, n, gap):
value = arr[i]
position = i
while position > 0 and arr[position-gap] > value:
arr[position] = arr[position-gap]
position -= gap
arr[position] = value
gap = gap // 2
return arr

#归并排序2
def mergeSort(arr):
n = len(arr)
if n > 1:
mid = n//2
left = mergeSort(arr[:mid])
right = mergeSort(arr[mid:])
merge = []
while left and right:
if left[0] < right[0]:
merge.append(left.pop(0))
else:
merge.append(right.pop(0))
merge.extend(left if left else right)
return merge
return arr

def quickSort(arr):
return quickSortHelper(arr, 0, len(arr) - 1)

#快速排序
def quickSortHelper(arr, first, last):
if first < last:
a = arr[first]
left = first + 1
right = last
done = False
while not done:
while left <= right and arr[left] <= a:
left = left + 1
while left <= right and arr[right] >= a:
right = right - 1
if right < left:
done = True
else:
arr[left], arr[right] = arr[right], arr[left]
arr[first], arr[right] = arr[right], arr[first]
quickSortHelper(arr, first, right - 1)
quickSortHelper(arr, right + 1, last)
return arr

编辑于 2021-06-19 20:43:31 回复(0)

Python

奋斗的习习张

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
# 冒泡，选择在时间复杂度上都通不过，使用快排可以，但空间占用较大
class Solution:
    def MySort(self , arr ):
        # write code here
        if len(arr) <= 1:
            return arr
        return self.quick_sort(arr)
    
    def quick_sort(self, array):
        if len(array) >= 2:
            base = array.pop(0)
            left = []
            right = []
            for i in array:
                if i < base:
                    left.append(i)
                else:
                    right.append(i)
            return self.quick_sort(left) + [base] + self.quick_sort(right)
        return array

发表于 2021-06-09 22:37:39 回复(0)

Python

code_of_yang

import copy
class Solution:
    def MySort(self , arr ):
        res = copy.deepcopy(arr)
        res.sort()
        return res
        # write code here

能用何必造轮子呢

发表于 2021-06-02 21:04:51 回复(0)

Python

JohnWick888

这是我的，你们为啥搞那么复杂

class Solution:

def MySort(self , arr ):
return sorted(arr)

编辑于 2021-05-19 11:02:42 回复(0)

Python

食堂在逃干饭王

快排，Partition中交换low和high的判断条件中时要记得加等号

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
    def partition(self, arr, low, high):
        base = arr[low]
        while low < high:
            while low < high and arr[high] >= base:
                high -= 1
            arr[low] = arr[high]
            while low < high and arr[low] <= base:
                low += 1
            arr[high] = arr[low]
        arr[low] = base
        return low
        
    def quick_sort(self, arr, low, high):
        mid = self.partition(arr, low, high)
        if low < mid - 1:
            self.quick_sort(arr, low, mid-1)
        if mid + 1 < high:
            self.quick_sort(arr, mid+1, high)
        
        
    def MySort(self , arr ):
        if len(arr) > 0:
            self.quick_sort(arr, 0, len(arr)-1)
        return arr

发表于 2021-03-25 10:07:17 回复(0)

Python

名字很落俗套

为什么会超时，一个示例都无法通过

发表于 2021-03-18 00:40:50 回复(0)

Python

ScorchHu

python实现:

class Solution:
    def MySort(self , arr ):
        # write code here
#         return self.bubble_sort(arr)
#         return self.select_sort(arr)
#         return self.insert_sort(arr)
        return self.quick_sort(arr)
#         return self.merge_sort(arr)
         
    def bubble_sort(self, arr):
        # 冒泡排序 不通过
        for i in range(len(arr) - 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
       
    def select_sort(self, arr):
        # 选择排序 不通过
        for i in range(len(arr)):
            min_index = i
            for j in range(i+1, len(arr)):
                if arr[j] < arr[min_index]:
                    min_index = j
            arr[min_index], arr[i] = arr[i], arr[min_index]
        return arr
    
    def insert_sort(self, li):
        # 插入排序 不通过
        for i in range(1, len(li)):
            tmp = li[i]                     # tmp要插入的之
            j = i - 1
            while j >= 0 and li[j] > tmp:   # 前面的值比tmp大
                li[j+1] = li[j]             # 前面的值向后移一位
                j = j - 1                   # 继续向前对比
            li[j+1] = tmp                   # 直到while不满足条件, 也就是前面的值比tmp小, 插入到比tmp小的值后
        return li
    
    def quick_sort(self, li):
        # 快速排序 通过
        if len(li) < 2:
            return li
        else:
            tmp = li[0]
            less = [i for i in li[1:] if i <= tmp]
            more = [i for i in li[1:] if i > tmp]
            return self.quick_sort(less) + [tmp] + self.quick_sort(more)
        
    def merge_sort(self, li):
        # 归并排序 可能通过 可能不通过
        if len(li) < 2:
            return li
        else:
            num = len(li) // 2
            left = self.merge_sort(li[:num])
            right = self.merge_sort(li[num:])
            return self.merge(left, right)
        
    def merge(self, left, right):
        l,r = 0,0
        result = []
        while l < len(left) and r < len(right):
            if left[l] < right[r]:
                result.append(left[l])
                l += 1
            else:
                result.append(right[r])
                r += 1
        result += left[l:]
        result += right[r:]
        return result

编辑于 2021-03-03 10:59:35 回复(5)

Python

圆fufu

插入排序为啥不行，因为时间复杂度高吗

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 将给定数组排序
# @param arr int整型一维数组 待排序的数组
# @return int整型一维数组
#
class Solution:
    def MySort(self , arr ):
        # write code here
        list=[]
        list.append(arr[0])
        arr.remove(arr[0])
#         arrIndex=0
        listIndex=0
        for i in arr:
            for j in list:
                listIndex+=1
                if i<=j:
                    list.insert(listIndex-1,i)
                    break
            if listIndex==len(list):
                list.append(i)
            listIndex=0

        return list

发表于 2021-01-31 00:27:15 回复(0)

Python

牛客297072041号

class Solution:
def MySort(self , arr ):
# write code here
arr.sort()
return arr

发表于 2021-01-27 18:38:08 回复(0)

Python

是你的浩哥啊

#快排

class Solution:
def MySort(self , arr ):
# write code here
def quick_sort(nums, i, j):
if i > j:
return nums
mid = nums[i]
left,right= i,j
while i < j:
while i < j and nums[j] >= mid:
j -= 1
nums[i] = nums[j]
while i < j and nums[i] <= mid:
i += 1
nums[j] = nums[i]
nums[i] = mid
quick_sort(nums, left, i - 1)
quick_sort(nums, j + 1, right)
return nums
return quick_sort(arr, 0,len(arr)-1)

发表于 2021-01-26 16:18:33 回复(0)

Python

E.N.G

这个....可以用内置函数？难道不应该自编函数吗？自编函数的话Python最快的就是归并排序和快速排序了吧，试了一下时间不满足呀

发表于 2020-10-24 15:12:31 回复(1)

Python

玖拾肆

class Solution:
    def MySort(self , arr ):
        # write code here
        arr=sorted(arr)
        return arr

发表于 2020-10-22 15:14:31 回复(0)

提交观点

问题信息

排序

难度：

17条回答 997收藏 13160浏览

通过挑战的用户

查看代码

钟森

2023-03-12 20:16:31
Zhaaaaaaa

2023-03-10 16:50:57
最喜欢夏天的懒羊羊

2023-03-08 01:29:53
牛客71457...

2023-02-26 20:40:50
你需要至高之拳

2023-02-24 11:16:30

排序

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题