堆排序与直接选择排序

**堆排序与直接选择排序**

在计算机科学中，排序算法是指将数据按某种顺序排列的过程。堆排序和直接选择排序都是常见的排序算法，它们都能对任意长度的数组进行排序。

### **1. 堆排序**

**定义：**
堆排序是一种基于堆的排序算法，首先将待排序的元素构建成一个最大堆（或最小堆），然后反复取出根结点，替换为最后一个元素，并调整堆，使得堆仍然满足堆性质。

**步骤：**

1. **构造最大堆：**
* 将待排序的数组中的所有元素作为叶子结点。
* 然后从最后一个非叶子结点开始，依次向上进行调整，使得每个父结点都大于或等于其左右孩子结点。

2. **取出根结点：**
* 将根结点（最大值）与最后一个元素交换。
* 然后从新得到的最大堆中，重新调整堆，使得仍然满足堆性质。

3. **重复上述过程：**
* 直到整个数组都被排序完毕。

**时间复杂度：**

* 最好情况（已排序）：O(n log n)
* 最坏情况（逆序）：O(n log n)

**空间复杂度：**

* O(1)，因为堆排序不需要额外的存储空间。

### **2. 直接选择排序**

**定义：**
直接选择排序是一种简单的排序算法，通过反复遍历数组中的元素，并将最小（或最大）元素放置在前面来实现排序。

**步骤：**

1. **首先找到最小值：**
* 遍历整个数组，找出最小值。
* 将最小值与第一个元素交换。

2. **然后找到第二小值：**
* 从第二个元素开始，遍历整个数组，找出第二小值。
* 将第二小值与第二个元素交换。

3. **重复上述过程：**
* 直到整个数组都被排序完毕。

**时间复杂度：**

* 最好情况（已排序）：O(n^2)
* 最坏情况（逆序）：O(n^2)

**空间复杂度：**

* O(1)，因为直接选择排序不需要额外的存储空间。

### **代码示例**

#### 堆排序

def heapify(arr, n, i):
 largest = i # Initialize largest as root left =2 * i +1 # left =2*i +1 right =2 * i +2 # right =2*i +2 if left < n and arr[i] < arr[left]:
 largest = left if right < n and arr[largest] < arr[right]:
 largest = right if largest != i:
 arr[i], arr[largest] = arr[largest], arr[i]
 heapify(arr, n, largest)

def heap_sort(arr):
 n = len(arr)
 # Build a maxheap.
 for i in range(n //2 -1, -1, -1):
 heapify(arr, n, i)
 # One by one extract elements for i in range(n-1,0, -1):
 arr[i], arr[0] = arr[0], arr[i]
 heapify(arr, i,0)

# Test the codearr = [12,11,13,5,6,7]
heap_sort(arr)
print("Sorted array is:", 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 codearr = [12,11,13,5,6,7]
print("Original array is:", arr)
sorted_arr = selection_sort(arr)
print("Sorted array is:", sorted_arr)