【数据结构】手撕排序NO.1----排序初识

**数据结构之手撕排序 NO.1——排序初识**

在计算机科学中，排序是指将一个无序的集合中的元素按照某种规则重新排列成有序的集合。排序算法是数据结构学习中非常重要的一部分，它们广泛应用于各种场景，如数据库管理、文件系统组织、网络通信等。

本文将介绍一些基本的排序算法，包括冒泡排序、选择排序、插入排序、归并排序和快速排序等。这些算法都是手撕排序 NO.1 的基础内容。

**1. 冒泡排序**

冒泡排序是一种简单的排序算法，它通过反复地遍历列表来将元素按顺序排列。

def bubble_sort(arr):
 n = len(arr)
 for i in range(n-1):
 # Traverse through all array elements for j in range(0, n-i-1):
 # Last i elements are already in place if arr[j] > arr[j+1]:
 # Swap arr[j] and arr[j+1]
 arr[j], arr[j+1] = arr[j+1], arr[j]
 return arr# Test the functionarr = [64,34,25,12,22,11,90]
print("Sorted array is:", bubble_sort(arr))

def selection_sort(arr):
 n = len(arr)
 for i in range(n-1):
 # Find the minimum element in remaining unsorted array min_idx = i for j in range(i+1, n):
 if arr[min_idx] > arr[j]:
 min_idx = j # Swap the found minimum element with the first element arr[i], arr[min_idx] = arr[min_idx], arr[i]
 return arr# Test the functionarr = [64,34,25,12,22,11,90]
print("Sorted array is:", selection_sort(arr))

def insertion_sort(arr):
 n = len(arr)
 for i in range(1, n):
 key = arr[i]
 # Move elements of arr[0..i-1], that are greater than key,
 # to one position ahead of their current position j = i-1 while j >=0 and key < arr[j]:
 arr[j+1] = arr[j]
 j -=1 arr[j+1] = key return arr# Test the functionarr = [64,34,25,12,22,11,90]
print("Sorted array is:", insertion_sort(arr))

def merge_sort(arr):
 if len(arr) <=1:
 return arr mid = len(arr) //2 left_half = arr[:mid]
 right_half = arr[mid:]
 # Recursively sort both halves left_half = merge_sort(left_half)
 right_half = merge_sort(right_half)
 # Merge the sorted halves return merge(left_half, right_half)

def merge(left, right):
 merged = []
 left_index =0 right_index =0 while left_index < len(left) and right_index < len(right):
 if left[left_index] <= right[right_index]:
 merged.append(left[left_index])
 left_index +=1 else:
 merged.append(right[right_index])
 right_index +=1 # Append the remaining elements, if any merged.extend(left[left_index:])
 merged.extend(right[right_index:])
 return merged# Test the functionarr = [64,34,25,12,22,11,90]
print("Sorted array is:", merge_sort(arr))

def quick_sort(arr):
 if len(arr) <=1:
 return arr pivot = arr[len(arr) //2]
 # Divide the array into three lists: elements less than the pivot,
 # equal to the pivot, and greater than the pivot 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]
 # Recursively sort the subarrays and combine them return quick_sort(left) + middle + quick_sort(right)

# Test the functionarr = [64,34,25,12,22,11,90]
print("Sorted array is:", quick_sort(arr))