算法基础之八大排序

概要

排序算法是编程中最基础也是最重要的算法之一。通过学习和理解不同的排序算法，我们可以在实际开发中选择合适的算法来解决问题。本文将介绍八大常用排序算法，并分别用 Python、C++ 和 Java 三种语言实现。

---

时间复杂度

1. 冒泡排序（Bubble Sort）

算法描述: 冒泡排序是一种简单的排序算法，通过不断交换相邻元素，使得较大的元素“浮”到数组的末尾。

时间复杂度

• 最佳情况：O(n)
• 平均情况：O(n²)
• 最坏情况：O(n²)

空间复杂度： O(1)
稳定性： 稳定

实现步骤

1. 比较相邻元素，前大则交换

2. 对每一对相邻元素重复操作

3. 每次遍历后范围缩小1

4. 重复直到无交换发生

代码实现

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

C++版本

void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {// Swap elementsint temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}
}

Java版本

public class BubbleSort {public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {for (int j = 0; j < n-i-1; j++) {if (arr[j] > arr[j+1]) {// Swap elementsint temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;}}}}
}

2. 选择排序（Selection Sort）

算法描述： 选择排序通过分为有序区和无序区，逐步从无序区中找到最小元素，放到有序区的末尾。

时间复杂度：

• 最佳情况：O(n²)
• 平均情况：O(n²)
• 最坏情况：O(n²)

空间复杂度： O(1)

稳定性： 不稳定

代码实现
python版本

# Python
def bubble_sort(arr):n = len(arr)for i in range(n-1):swapped = Falsefor j in range(n-1-i):if arr[j] > arr[j+1]:arr[j], arr[j+1] = arr[j+1], arr[j]swapped = Trueif not swapped:breakreturn arr

C++版本

// C++
void bubbleSort(int arr[], int n) {for (int i = 0; i < n-1; ++i) {bool swapped = false;for (int j = 0; j < n-1-i; ++j) {if (arr[j] > arr[j+1]) {swap(arr[j], arr[j+1]);swapped = true;}}if (!swapped) break;}
}

Java版本

// Java
public static void bubbleSort(int[] arr) {int n = arr.length;for (int i = 0; i < n-1; i++) {boolean swapped = false;for (int j = 0; j < n-1-i; j++) {if (arr[j] > arr[j+1]) {int temp = arr[j];arr[j] = arr[j+1];arr[j+1] = temp;swapped = true;}}if (!swapped) break;}
}

3. 插入排序（Insertion Sort）

算法思想： 将未排序元素逐个插入已排序序列的合适位置

时间复杂度：

• 平均：O(n²)

• 最坏：O(n²)

• 最好：O(n)

稳定性： 稳定

python版本

# Python
def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i-1while j >=0 and key < arr[j] :arr[j+1] = arr[j]j -= 1arr[j+1] = keyreturn arr

C++版本

// C++
void insertionSort(int arr[], int n) {for (int i = 1; i < n; ++i) {int key = arr[i];int j = i-1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}

Java版本

// Java
public static void insertionSort(int[] arr) {for (int i = 1; i < arr.length; ++i) {int key = arr[i];int j = i - 1;while (j >= 0 && arr[j] > key) {arr[j+1] = arr[j];j--;}arr[j+1] = key;}
}

4. 希尔排序（Shell Sort）

算法思想： 改进的插入排序，通过间隔分组进行预处理
时间复杂度： O(n log n) ~ O(n²)
稳定性： 不稳定

python版本

# Python
def shell_sort(arr):n = len(arr)gap = n//2while gap > 0:for i in range(gap, n):temp = arr[i]j = iwhile j >= gap and arr[j-gap] > temp:arr[j] = arr[j-gap]j -= gaparr[j] = tempgap //= 2return arr

C++版本

// C++
void shellSort(int arr[], int n) {for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; ++i) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)arr[j] = arr[j - gap];arr[j] = temp;}}
}

Java版本

// Java
public static void shellSort(int[] arr) {int n = arr.length;for (int gap = n/2; gap > 0; gap /= 2) {for (int i = gap; i < n; i++) {int temp = arr[i];int j;for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)arr[j] = arr[j - gap];arr[j] = temp;}}
}

5. 归并排序（Merge Sort）

算法思想： 分治法，递归拆分后合并有序子序列
时间复杂度： O(n log n)
稳定性： 稳定

python版本

# Python
def merge_sort(arr):if len(arr) > 1:mid = len(arr)//2L = arr[:mid]R = arr[mid:]merge_sort(L)merge_sort(R)i = j = k = 0while i < len(L) and j < len(R):if L[i] < R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < len(L):arr[k] = L[i]i += 1k += 1while j < len(R):arr[k] = R[j]j += 1k += 1return arr

C++版本：

// C++
void merge(int arr[], int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;int L[n1], R[n2];for (int i = 0; i < n1; i++)L[i] = arr[l + i];for (int j = 0; j < n2; j++)R[j] = arr[m + 1 + j];int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];i++;} else {arr[k] = R[j];j++;}k++;}while (i < n1) arr[k++] = L[i++];while (j < n2) arr[k++] = R[j++];
}void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l)/2;mergeSort(arr, l, m);mergeSort(arr, m+1, r);merge(arr, l, m, r);}
}

Java版本

// Java
public static void mergeSort(int[] arr, int l, int r) {if (l < r) {int m = (l + r) / 2;mergeSort(arr, l, m);mergeSort(arr, m + 1, r);int[] L = Arrays.copyOfRange(arr, l, m + 1);int[] R = Arrays.copyOfRange(arr, m + 1, r + 1);int i = 0, j = 0, k = l;while (i < L.length && j < R.length) {if (L[i] <= R[j]) arr[k++] = L[i++];else arr[k++] = R[j++];}while (i < L.length) arr[k++] = L[i++];while (j < R.length) arr[k++] = R[j++];}
}

6. 快速排序（Quick Sort）

算法思想： 分治法，选取基准元素进行分区排序
时间复杂度：

• 平均：O(n log n)

• 最坏：O(n²)

稳定性： 不稳定

python版本

在这里插入代码片# Python
def quick_sort(arr):if len(arr) <= 1:return arrpivot = 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)

C++版本：

// C++
int partition(int arr[], int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;swap(arr[i], arr[j]);}}swap(arr[i+1], arr[high]);return i+1;
}void quickSort(int arr[], int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi-1);quickSort(arr, pi+1, high);}
}

Java版本

// Java
public static void quickSort(int[] arr, int low, int high) {if (low < high) {int pi = partition(arr, low, high);quickSort(arr, low, pi-1);quickSort(arr, pi+1, high);}
}private static int partition(int[] arr, int low, int high) {int pivot = arr[high];int i = low - 1;for (int j = low; j < high; j++) {if (arr[j] < pivot) {i++;int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}int temp = arr[i+1];arr[i+1] = arr[high];arr[high] = temp;return i+1;
}

7. 堆排序（Heap Sort）

算法思想： 利用堆数据结构进行选择排序
时间复杂度： O(n log n)
稳定性： 不稳定

python版本

# Python
def 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)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

C++版本：

// C++
void heapify(int arr[], int n, int i) {int largest = i;int l = 2*i + 1;int r = 2*i + 2;if (l < n && arr[l] > arr[largest])largest = l;if (r < n && arr[r] > arr[largest])largest = r;if (largest != i) {swap(arr[i], arr[largest]);heapify(arr, n, largest);}
}void heapSort(int arr[], int n) {for (int i = n/2 - 1; i >= 0; i--)heapify(arr, n, i);for (int i = n-1; i > 0; i--) {swap(arr[0], arr[i]);heapify(arr, i, 0);}
}

Java版本

// Java
public static void heapSort(int[] arr) {int n = arr.length;for (int i = n/2 - 1; i >= 0; i--)heapify(arr, n, i);for (int i = n-1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;heapify(arr, i, 0);}
}private static void heapify(int[] arr, int n, int i) {int largest = i;int l = 2*i + 1;int r = 2*i + 2;if (l < n && arr[l] > arr[largest]) largest = l;if (r < n && arr[r] > arr[largest]) largest = r;if (largest != i) {int swap = arr[i];arr[i] = arr[largest];arr[largest] = swap;heapify(arr, n, largest);}
}

8. 计数排序（Counting Sort）

适用场景： 整数排序且值范围不大
时间复杂度： O(n + k)
稳定性： 稳定

python版本

# Python
def counting_sort(arr):max_val = max(arr)count = [0] * (max_val + 1)for num in arr:count[num] += 1idx = 0for i in range(len(count)):while count[i] > 0:arr[idx] = iidx += 1count[i] -= 1return arr

C++版本：

// C++
void countingSort(int arr[], int n) {int maxVal = *max_element(arr, arr + n);int count[maxVal + 1] = {0};for (int i = 0; i < n; i++)count[arr[i]]++;int idx = 0;for (int i = 0; i <= maxVal; i++) {while (count[i]-- > 0) {arr[idx++] = i;}}
}

Java版本

// Java
public static void countingSort(int[] arr) {int maxVal = Arrays.stream(arr).max().getAsInt();int[] count = new int[maxVal + 1];for (int num : arr) count[num]++;int idx = 0;for (int i = 0; i <= maxVal; i++) {while (count[i]-- > 0) {arr[idx++] = i;}}
}

小结

排序算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	稳定
选择排序	O(n²)	O(n²)	O(1)	不稳定
插入排序	O(n²)	O(n²)	O(1)	稳定
希尔排序	O(n log n)	O(n²)	O(1)	不稳定
归并排序	O(n log n)	O(n log n)	O(n)	稳定
快速排序	O(n log n)	O(n²)	O(log n)	不稳定
堆排序	O(n log n)	O(n log n)	O(1)	不稳定
计数排序	O(n + k)	O(n + k)	O(k)	稳定

注：k为计数排序的值域范围

应用场景建议：

• 小规模数据：插入排序

• 通用高效：快速排序

• 内存敏感：堆排序

• 稳定需求：归并排序

• 整数排序：计数排序