十大排序算法

比较类排序

冒泡排序（Bubble Sort）

原理：重复地比较相邻元素，若顺序错误则交换，使较大（或较小）的元素逐步“冒泡”到序列的一端。

时间复杂度：平均和最坏情况为 O(n²)。

空间复杂度：O(1)。

稳定性：稳定。

代码实现：

void bubbleSort(std::vector<int>& array, int n) {
	for (int i = 0; i < n; ++i) {
        // 使用标志位进行优化
        // 如果本轮未发生交换
        // 说明数组已经有序, 提前结束循环
		bool flag = false;
		for (int j = 1; j < n; ++j) {
			if (array[j - 1] > array[j]) {
				std::swap(array[j - 1], array[j]);
				flag = true;
			}
		}
		if (!flag) {
			break;
		}
	}
}

插入排序（Insertion Sort）

原理：构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

时间复杂度：平均和最坏情况为 O(n²)。

空间复杂度：O(1)。

稳定性：稳定。

代码实现：

void insertionSort(std::vector<int>& array, int n) {
	for (int i = 1; i < n; ++i) {
		int key = array[i];
		int j = i - 1;
		while (j >= 0 && array[j] > key) {
			array[j + 1] = array[j];
			--j;
		}
		array[j + 1] = key;
	}
}

选择排序（Selection Sort）

原理：每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。

时间复杂度：O(n²)。

空间复杂度：O(1)。

稳定性：不稳定。

代码实现：

void selectSort(std::vector<int>& array, int n) {
	for (int i = 0; i < n - 1; ++i) {
		int minIndex = i;
		for (int j = i + 1; j < n; ++j) {
			if (array[minIndex] > array[j]) {
				minIndex = j;
			}
		}
		std::swap(array[minIndex], array[i]);
	}
}

希尔排序（Shell Sort）

增强的插入排序，通过gap将数组分为多个子序列，对每个子序列进行插入排序，缩小gap直到gap == 1，变成标准的插入排序

• 原理：将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序。
• 时间复杂度：根据增量序列的不同而不同，平均情况约为 O(n^1.3)。
• 空间复杂度：O(1)。
• 稳定性：不稳定。

void shellSort(std::vector<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 = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

归并排序（Merge Sort）

• 原理：采用分治法，将序列分为两个子序列，分别排序后合并。
• 时间复杂度：O(n log n)。
• 空间复杂度：O(n)。
• 稳定性：稳定。

// Merge Sort
// 辅助合并函数
void merge(std::vector<int>& array, int left, int mid, int right) {
	std::vector<int> temp(right - left + 1);
	int i = left, j = mid + 1, k = 0;
	while (i <= mid && j <= right) {
		if (array[i] <= array[j]) {
			temp[k++] = array[i++];
		}
		else {
			temp[k++] = array[j++];
		}
	}
	while (i <= mid) {
		temp[k++] = array[i++];
	}
	while (j <= right) {
		temp[k++] = array[j++];
	}

	// 写回原数组
	for (int i = 0; i < temp.size(); ++i) {
		array[left + i] = temp[i];
	}
}

// 执行分治逻辑的函数
// 主函数
void mergeSort(std::vector<int>& array, int left, int right) {
	if (left >= right) return;
	int mid = left + (right - left) / 2;
	mergeSort(array, left, mid);
	mergeSort(array, mid + 1, right);
	merge(array, left, mid, right);
}

堆排序

==快速排序（Quick Sort）==

通过选定基准值，使用分治思想分割数组，确保基准点左侧一定小于基准点，右侧一定大于基准点，当数组元素个数足够小时（<= 3），该数组就是有序的

原理：通过一趟排序将数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。

时间复杂度：平均为 O(n log n)，最坏为 O(n²)。

空间复杂度：O(log n)。

稳定性：不稳定。

代码实现：

int partition(std::vector<int>& array, int left, int right) {
    // 选取最右侧作为基准点
    int pivot = array[right];
    int i = left - 1;
    for (int j = left; j < right; ++j) {
        if (array[j] <= pivot) {
            ++i;
            std::swap(array[j], array[i]);
        }
    }
    std::swap(array[i + 1], array[right]);
    return i + 1;
}

void quickSort(std::vector<int>& array, int left, int right) {
    if (left >= right) return;
    int pivotIndex = partition(array, left, right);
    quickSort(array, left, pivotIndex - 1);
    quickSort(array, pivotIndex + 1, right);
}

非比较类排序

计数排序

桶排序

基数排序