python排序算法
时间: 2023-07-01 18:13:05 浏览: 39
Python中常用的排序算法有以下几种:
1. 冒泡排序(Bubble Sort)
2. 选择排序(Selection Sort)
3. 插入排序(Insertion Sort)
4. 快速排序(Quick Sort)
5. 归并排序(Merge Sort)
6. 堆排序(Heap Sort)
下面给出一个简单的冒泡排序的实现代码:
```python
def bubble_sort(arr):
n = len(arr)
# 遍历所有数组元素
for i in range(n):
# Last i elements are already in place
for j in range(0, n-i-1):
# 如果当前元素大于下一个元素,则交换它们的位置
if arr[j] > arr[j+1] :
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
```
该函数接受一个数组作为参数,返回一个排序后的数组。首先,我们定义一个变量 `n` 来表示数组的长度(元素个数)。然后,我们使用两个嵌套的循环来遍历所有的数组元素,外层循环从第一个元素开始,内层循环从第一个元素开始直到倒数第二个元素,比较相邻的两个元素大小,如果前一个元素大于后一个元素,则交换它们的位置。这样,每一次内层循环结束后,最大的元素就会被移动到数组的最后一个位置,因此,外层循环可以减少一次遍历。最后,返回排好序的数组。
相关问题
PYTHON排序算法
Python 中有很多种排序算法,下面是其中几种常见的排序算法:
1. 冒泡排序(Bubble Sort):比较相邻的元素,如果顺序不对则交换,重复这个过程直到整个数组排序完成。
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
```
2. 选择排序(Selection Sort):每次从未排序的部分找到最小元素,放到已排序部分的末尾。
```python
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
```
3. 插入排序(Insertion Sort):将未排序的元素插入到已排序部分的合适位置。
```python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
```
4. 快速排序(Quick Sort):选择一个基准元素,将比基准元素小的放在左边,比基准元素大的放在右边,然后对左右两个子数组递归地进行快速排序。
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
```
这些只是其中的几种排序算法,在实际应用中,根据数据规模和性能需求,选择合适的排序算法非常重要。
python 排序算法
Python中常见的排序算法有以下几种:
1. 冒泡排序(Bubble Sort)
2. 选择排序(Selection Sort)
3. 插入排序(Insertion Sort)
4. 归并排序(Merge Sort)
5. 快速排序(Quick Sort)
6. 堆排序(Heap Sort)
以下是各种排序算法的Python实现代码:
1. 冒泡排序
```python
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
```
2. 选择排序
```python
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
```
3. 插入排序
```python
def insertion_sort(arr):
n = len(arr)
for i in range(1, n):
j = i
while j > 0 and arr[j] < arr[j-1]:
arr[j], arr[j-1] = arr[j-1], arr[j]
j -= 1
return arr
```
4. 归并排序
```python
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left = merge_sort(left)
right = merge_sort(right)
return merge(left, right)
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
```
5. 快速排序
```python
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr)//2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
```
6. 堆排序
```python
def heap_sort(arr):
n = len(arr)
for i in range(n//2-1, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
return arr
def heapify(arr, n, i):
largest = i
l = 2*i + 1
r = 2*i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
```