八大排序算法（八大排序算法c语言）

## 八大排序算法详解### 简介排序算法是计算机科学中非常重要的基础算法之一，它用于将一组数据按照特定的顺序排列。常见的排序算法有很多，但最基础且常用的有八种：

冒泡排序

选择排序

插入排序

希尔排序

归并排序

快速排序

堆排序

基数排序下面将详细介绍每种排序算法的原理、步骤和优缺点。### 1. 冒泡排序 (Bubble Sort)

原理：

冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素，并交换它们的位置，直到整个列表排序完成。

步骤：

1. 比较相邻的两个元素。 2. 如果第一个元素大于第二个元素，则交换它们的位置。 3. 重复步骤 1 和 2，直到遍历整个列表。 4. 重复步骤 1 到 3，直到列表完全排序。

优缺点：

优点：

实现简单，容易理解。

缺点：

时间复杂度为 O(n^2)，效率低下，对于大数据集不适用。

示例代码：

```python def bubble_sort(arr):n = len(arr)for i in range(n-1):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. 选择排序 (Selection Sort)

原理：

选择排序也是一种简单的排序算法，它在每一轮中找到列表中最小的元素，并将其与当前位置的元素交换。

步骤：

1. 找到列表中最小的元素。 2. 将最小元素与当前位置的元素交换。 3. 重复步骤 1 和 2，直到列表完全排序。

优缺点：

优点：

简单易懂，空间复杂度为 O(1)。

缺点：

时间复杂度为 O(n^2)，效率低下，对于大数据集不适用。

示例代码：

```python def selection_sort(arr):n = len(arr)for i in range(n-1):min_idx = ifor j in range(i+1, n):if arr[min_idx] > arr[j]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arr ```### 3. 插入排序 (Insertion Sort)

原理：

插入排序是一种比较简单的排序算法，它将待排序的列表分为已排序部分和未排序部分，每次从未排序部分中取出一个元素，将其插入到已排序部分的合适位置。

步骤：

1. 从第二个元素开始遍历列表。 2. 将当前元素与已排序部分的元素逐个比较，直到找到比当前元素小的元素为止。 3. 将当前元素插入到该位置。 4. 重复步骤 1 到 3，直到遍历整个列表。

优缺点：

优点：

简单易懂，空间复杂度为 O(1)，对于已经排序的列表非常高效，时间复杂度为 O(n)。

缺点：

时间复杂度为 O(n^2)，对于大数据集效率低下。

示例代码：

```python def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i-1while j >= 0 and key < arr[j]:arr[j+1] = arr[j]j -= 1arr[j+1] = keyreturn arr ```### 4. 希尔排序 (Shell Sort)

原理：

希尔排序是插入排序的一种改进版本，它通过将列表分成多个子列表进行排序，然后逐渐减小子列表的间隔，最终对整个列表进行排序。

步骤：

1. 选择一个间隔值，将列表分成多个子列表。 2. 对每个子列表进行插入排序。 3. 逐渐减小间隔值，重复步骤 1 和 2，直到间隔值为 1。

优缺点：

优点：

比插入排序效率更高，时间复杂度为 O(n^(3/2))。

缺点：

实现比插入排序复杂，对于大数据集仍然效率低下。

示例代码：

```python def shell_sort(arr):n = len(arr)gap = n // 2while gap > 0:for i in range(gap, n):key = arr[i]j = iwhile j >= gap and key < arr[j - gap]:arr[j] = arr[j - gap]j -= gaparr[j] = keygap //= 2return arr ```### 5. 归并排序 (Merge Sort)

原理：

归并排序是一种基于分治思想的排序算法，它将待排序的列表递归地分成两个子列表，对子列表进行排序，然后将两个排序后的子列表合并成一个排序后的列表。

步骤：

1. 将列表递归地分成两个子列表，直到子列表只有一个元素。 2. 对子列表进行排序。 3. 合并两个排序后的子列表。

优缺点：

优点：

时间复杂度为 O(n log n)，效率高，稳定排序算法。

缺点：

需要额外的空间来存储子列表。

示例代码：

```python def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_arr = arr[:mid]right_arr = arr[mid:]merge_sort(left_arr)merge_sort(right_arr)i = j = k = 0while i < len(left_arr) and j < len(right_arr):if left_arr[i] < right_arr[j]:arr[k] = left_arr[i]i += 1else:arr[k] = right_arr[j]j += 1k += 1while i < len(left_arr):arr[k] = left_arr[i]i += 1k += 1while j < len(right_arr):arr[k] = right_arr[j]j += 1k += 1return arr ```### 6. 快速排序 (Quick Sort)

原理：

快速排序也是一种基于分治思想的排序算法，它通过选择一个基准元素，将列表分成两个子列表，一个子列表包含所有小于基准元素的元素，另一个子列表包含所有大于基准元素的元素，然后递归地对子列表进行排序。

步骤：

1. 选择一个基准元素。 2. 将列表分成两个子列表，一个子列表包含所有小于基准元素的元素，另一个子列表包含所有大于基准元素的元素。 3. 递归地对子列表进行排序。

优缺点：

优点：

平均时间复杂度为 O(n log n)，效率高，空间复杂度为 O(log n)。

缺点：

最坏时间复杂度为 O(n^2)，不稳定排序算法。

示例代码：

```python def quick_sort(arr, low, high):if low < high:pi = partition(arr, low, high)quick_sort(arr, low, pi-1)quick_sort(arr, pi+1, high)return arrdef partition(arr, low, high):pivot = arr[high]i = low - 1for j in range(low, high):if arr[j] <= pivot:i += 1arr[i], arr[j] = arr[j], arr[i]arr[i+1], arr[high] = arr[high], arr[i+1]return i+1 ```### 7. 堆排序 (Heap Sort)

原理：

堆排序是一种基于堆数据结构的排序算法，它利用堆的性质，将列表构建成一个堆，然后依次取出堆顶元素，直到堆为空。

步骤：

1. 将列表构建成一个堆。 2. 依次取出堆顶元素，并将其与最后一个元素交换。 3. 将堆的大小减 1，并重新调整堆。 4. 重复步骤 2 和 3，直到堆为空。

优缺点：

优点：

时间复杂度为 O(n log n)，效率高，空间复杂度为 O(1)。

缺点：

不稳定排序算法。

示例代码：

```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 arrdef heapify(arr, n, i):largest = il = 2

i + 1r = 2

i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest) ```### 8. 基数排序 (Radix Sort)

原理：

基数排序是一种非比较排序算法，它根据数字的每一位进行排序。它将列表分成多个桶，每个桶对应一个数字，然后将列表中的元素按照每一位的数字分配到不同的桶中，最后将桶按照顺序合并。

步骤：

1. 确定排序的关键字，例如个位、十位、百位等。 2. 根据关键字，将列表中的元素分配到不同的桶中。 3. 将桶按照顺序合并。 4. 重复步骤 2 和 3，直到所有关键字都排序完成。

优缺点：

优点：

时间复杂度为 O(nk)，其中 n 是列表长度，k 是关键字的数量，对于特定数据分布效率很高。

缺点：

空间复杂度为 O(n+k)，对于不规则的数据分布可能效率低下。

示例代码：

```python def radix_sort(arr):max_num = max(arr)exp = 1while max_num // exp > 0:buckets = [[] for _ in range(10)]for num in arr:index = (num // exp) % 10buckets[index].append(num)arr = [num for bucket in buckets for num in bucket]exp

= 10return arr ```### 总结以上八种排序算法各有优缺点，在实际应用中应该根据具体的数据规模、数据分布和性能要求选择合适的排序算法。例如，对于小规模数据集，可以选择简单易懂的冒泡排序或选择排序；对于大规模数据集，则可以选择效率更高的归并排序、快速排序或堆排序。

八大排序算法详解

简介排序算法是计算机科学中非常重要的基础算法之一，它用于将一组数据按照特定的顺序排列。常见的排序算法有很多，但最基础且常用的有八种：* 冒泡排序 * 选择排序 * 插入排序 * 希尔排序 * 归并排序 * 快速排序 * 堆排序 * 基数排序下面将详细介绍每种排序算法的原理、步骤和优缺点。

1. 冒泡排序 (Bubble Sort)**原理：**冒泡排序是一种简单的排序算法，它重复地遍历要排序的列表，比较相邻的元素，并交换它们的位置，直到整个列表排序完成。**步骤：**1. 比较相邻的两个元素。 2. 如果第一个元素大于第二个元素，则交换它们的位置。 3. 重复步骤 1 和 2，直到遍历整个列表。 4. 重复步骤 1 到 3，直到列表完全排序。**优缺点：*** **优点：** 实现简单，容易理解。 * **缺点：** 时间复杂度为 O(n^2)，效率低下，对于大数据集不适用。**示例代码：**```python def bubble_sort(arr):n = len(arr)for i in range(n-1):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. 选择排序 (Selection Sort)**原理：**选择排序也是一种简单的排序算法，它在每一轮中找到列表中最小的元素，并将其与当前位置的元素交换。**步骤：**1. 找到列表中最小的元素。 2. 将最小元素与当前位置的元素交换。 3. 重复步骤 1 和 2，直到列表完全排序。**优缺点：*** **优点：** 简单易懂，空间复杂度为 O(1)。 * **缺点：** 时间复杂度为 O(n^2)，效率低下，对于大数据集不适用。**示例代码：**```python def selection_sort(arr):n = len(arr)for i in range(n-1):min_idx = ifor j in range(i+1, n):if arr[min_idx] > arr[j]:min_idx = jarr[i], arr[min_idx] = arr[min_idx], arr[i]return arr ```

3. 插入排序 (Insertion Sort)**原理：**插入排序是一种比较简单的排序算法，它将待排序的列表分为已排序部分和未排序部分，每次从未排序部分中取出一个元素，将其插入到已排序部分的合适位置。**步骤：**1. 从第二个元素开始遍历列表。 2. 将当前元素与已排序部分的元素逐个比较，直到找到比当前元素小的元素为止。 3. 将当前元素插入到该位置。 4. 重复步骤 1 到 3，直到遍历整个列表。**优缺点：*** **优点：** 简单易懂，空间复杂度为 O(1)，对于已经排序的列表非常高效，时间复杂度为 O(n)。 * **缺点：** 时间复杂度为 O(n^2)，对于大数据集效率低下。**示例代码：**```python def insertion_sort(arr):n = len(arr)for i in range(1, n):key = arr[i]j = i-1while j >= 0 and key < arr[j]:arr[j+1] = arr[j]j -= 1arr[j+1] = keyreturn arr ```

4. 希尔排序 (Shell Sort)**原理：**希尔排序是插入排序的一种改进版本，它通过将列表分成多个子列表进行排序，然后逐渐减小子列表的间隔，最终对整个列表进行排序。**步骤：**1. 选择一个间隔值，将列表分成多个子列表。 2. 对每个子列表进行插入排序。 3. 逐渐减小间隔值，重复步骤 1 和 2，直到间隔值为 1。**优缺点：*** **优点：** 比插入排序效率更高，时间复杂度为 O(n^(3/2))。 * **缺点：** 实现比插入排序复杂，对于大数据集仍然效率低下。**示例代码：**```python def shell_sort(arr):n = len(arr)gap = n // 2while gap > 0:for i in range(gap, n):key = arr[i]j = iwhile j >= gap and key < arr[j - gap]:arr[j] = arr[j - gap]j -= gaparr[j] = keygap //= 2return arr ```

5. 归并排序 (Merge Sort)**原理：**归并排序是一种基于分治思想的排序算法，它将待排序的列表递归地分成两个子列表，对子列表进行排序，然后将两个排序后的子列表合并成一个排序后的列表。**步骤：**1. 将列表递归地分成两个子列表，直到子列表只有一个元素。 2. 对子列表进行排序。 3. 合并两个排序后的子列表。**优缺点：*** **优点：** 时间复杂度为 O(n log n)，效率高，稳定排序算法。 * **缺点：** 需要额外的空间来存储子列表。**示例代码：**```python def merge_sort(arr):if len(arr) > 1:mid = len(arr) // 2left_arr = arr[:mid]right_arr = arr[mid:]merge_sort(left_arr)merge_sort(right_arr)i = j = k = 0while i < len(left_arr) and j < len(right_arr):if left_arr[i] < right_arr[j]:arr[k] = left_arr[i]i += 1else:arr[k] = right_arr[j]j += 1k += 1while i < len(left_arr):arr[k] = left_arr[i]i += 1k += 1while j < len(right_arr):arr[k] = right_arr[j]j += 1k += 1return arr ```

6. 快速排序 (Quick Sort)**原理：**快速排序也是一种基于分治思想的排序算法，它通过选择一个基准元素，将列表分成两个子列表，一个子列表包含所有小于基准元素的元素，另一个子列表包含所有大于基准元素的元素，然后递归地对子列表进行排序。**步骤：**1. 选择一个基准元素。 2. 将列表分成两个子列表，一个子列表包含所有小于基准元素的元素，另一个子列表包含所有大于基准元素的元素。 3. 递归地对子列表进行排序。**优缺点：*** **优点：** 平均时间复杂度为 O(n log n)，效率高，空间复杂度为 O(log n)。 * **缺点：** 最坏时间复杂度为 O(n^2)，不稳定排序算法。**示例代码：**```python def quick_sort(arr, low, high):if low < high:pi = partition(arr, low, high)quick_sort(arr, low, pi-1)quick_sort(arr, pi+1, high)return arrdef partition(arr, low, high):pivot = arr[high]i = low - 1for j in range(low, high):if arr[j] <= pivot:i += 1arr[i], arr[j] = arr[j], arr[i]arr[i+1], arr[high] = arr[high], arr[i+1]return i+1 ```

7. 堆排序 (Heap Sort)**原理：**堆排序是一种基于堆数据结构的排序算法，它利用堆的性质，将列表构建成一个堆，然后依次取出堆顶元素，直到堆为空。**步骤：**1. 将列表构建成一个堆。 2. 依次取出堆顶元素，并将其与最后一个元素交换。 3. 将堆的大小减 1，并重新调整堆。 4. 重复步骤 2 和 3，直到堆为空。**优缺点：*** **优点：** 时间复杂度为 O(n log n)，效率高，空间复杂度为 O(1)。 * **缺点：** 不稳定排序算法。**示例代码：**```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 arrdef heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[l] > arr[largest]:largest = lif r < n and arr[r] > arr[largest]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest) ```

8. 基数排序 (Radix Sort)**原理：**基数排序是一种非比较排序算法，它根据数字的每一位进行排序。它将列表分成多个桶，每个桶对应一个数字，然后将列表中的元素按照每一位的数字分配到不同的桶中，最后将桶按照顺序合并。**步骤：**1. 确定排序的关键字，例如个位、十位、百位等。 2. 根据关键字，将列表中的元素分配到不同的桶中。 3. 将桶按照顺序合并。 4. 重复步骤 2 和 3，直到所有关键字都排序完成。**优缺点：*** **优点：** 时间复杂度为 O(nk)，其中 n 是列表长度，k 是关键字的数量，对于特定数据分布效率很高。 * **缺点：** 空间复杂度为 O(n+k)，对于不规则的数据分布可能效率低下。**示例代码：**```python def radix_sort(arr):max_num = max(arr)exp = 1while max_num // exp > 0:buckets = [[] for _ in range(10)]for num in arr:index = (num // exp) % 10buckets[index].append(num)arr = [num for bucket in buckets for num in bucket]exp *= 10return arr ```

总结以上八种排序算法各有优缺点，在实际应用中应该根据具体的数据规模、数据分布和性能要求选择合适的排序算法。例如，对于小规模数据集，可以选择简单易懂的冒泡排序或选择排序；对于大规模数据集，则可以选择效率更高的归并排序、快速排序或堆排序。