1.
冒泡排序是一种简单的排序算法，它通过重复地遍历要排序的数列，比较相邻的两个元素，如果它们的顺序错误就交换它们的位置。冒泡排序的时间复杂度为O(n^2)。
以下是冒泡排序的详细解析和代码示例：
从第一个元素开始，依次比较相邻的两个元素，如果它们的顺序错误就交换它们的位置。这样，每一轮循环后，最大的元素就会被“冒泡”到数列的末尾。
重复步骤1，直到整个数列都被排序。
代码示例：
#include <iostream>
using namespace std;
void bubbleSort(int a[], int n) {
for(int i = n;i >= 1; -- i)
{
for(int j = 1;j < i; ++ j)
{
if(a[j] > a[j + 1]) swap(a[j], a[j + 1]);
}
}
}
int main() {
int a[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(a) / sizeof(a[0]);
bubbleSort(a, n);
cout << "Sorted array is: ";
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}
cout << endl;
return 0;
}2.
选择排序是一种简单的排序算法，它的基本思想是每次从未排序的元素中选出最小（或最大）的一个元素，将其放到已排序序列的末尾。选择排序的时间复杂度为O(n^2)。
以下是选择排序的详细解析和代码示例：
从第一个元素开始，依次遍历未排序的元素，找到其中最小的元素。
将找到的最小元素与未排序序列的第一个元素交换位置。
重复步骤1和步骤2，直到整个序列都被排序。
代码示例：
#include <iostream>
using namespace std;
void selectionSort(int arr[], int n)
{
// 选择排序
for(int i = n;i >= 1; -- i)
{
int max_id = 1;
for(int j = 1;j <= i; ++ j)
{
if(arr[j] > arr[max_id])max_id = j;
}
swap(arr[j], arr[max_id]);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
cout << "Sorted array is: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}3.
插入排序是一种简单的排序算法，它的基本思想是将一个元素插入到已经排好序的序列中，从而得到一个新的、更长的已排序序列。插入排序的时间复杂度为O(n^2)。
以下是插入排序的详细解析和代码示例：
从第二个元素开始，将其作为待插入的元素。
将待插入元素与已排序序列中的元素依次比较，找到合适的位置插入。
重复步骤1和步骤2，直到整个序列都被排序。
代码示例：
#include <iostream>
using namespace std;
void insertionSort(int arr[], int n) {
// 插入排序
for(int i = 2;i <= n; ++ i)
{
int val = arr[i], j;
for(j = i;j > 1 && val < arr[j - 1]; -- j) arr[j] = arr[j - 1];
a[j] = val;
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
cout << "Sorted array is: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}4.
快速排序是一种高效的排序算法，它的基本思想是通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
分区（partition）是快速排序算法中的一个重要操作，用于将数组分成两个部分，使得左边的元素都小于等于基准元素，右边的元素都大于等于基准元素。
选择一个基准元素，通常选择第一个元素或者最后一个元素。
将基准元素放到数组的最右边。
从左到右遍历数组，如果当前元素小于等于基准元素，则将其与左边的边界元素交换位置，并将左边界向右移动一位。
遍历完数组后，将基准元素与左边界的前一个元素交换位置。
返回基准元素的位置。
代码示例：
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准元素
int i = low - 1; // 左边界
for (int j = low; j <= high - 1; j++) {
if (arr[j] <= pivot) {
i++;
swap(arr[i], arr[j]); // 将小于等于基准元素的元素交换到左边
}
}
swap(arr[i + 1], arr[high]); // 将基准元素放到正确的位置
return i + 1; // 返回基准元素的位置
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
int pivotIndex = partition(arr, 0, n - 1);
cout << "Pivot element is at index: " << pivotIndex << endl;
cout << "Array after partition: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}快速排序的解析和代码示例：
选择一个基准元素，通常选择第一个元素或者最后一个元素。
通过一趟排序将待排序的数据分割成独立的两部分，所有比基准元素小的元素放在基准元素前面，所有比基准元素大的元素放在基准元素的后面（相同的数可以到任何一边）。在这个分割结束之后，对基准元素的排序就已经完成。
对前后两部分的数据进行递归调用快速排序。
代码示例：
#include <iostream>
using namespace std;
int partition(int arr[], int low, int high) {
int pivot = arr[low]; // 选择第一个元素作为基准元素
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high]; // 将比基准元素小的元素交换到前面
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low]; // 将比基准元素大的元素交换到后面
}
arr[low] = pivot; // 将基准元素放到正确的位置
return low;
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high); // 获取基准元素的位置
quickSort(arr, low, pivotIndex - 1); // 对前半部分进行递归排序
quickSort(arr, pivotIndex + 1, high); // 对后半部分进行递归排序
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90};
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
cout << "Sorted array is: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}5.
归并排序是一种分治算法，它将待排序的序列分成两个子序列，对每个子序列进行排序，然后将两个已排序的子序列合并成一个有序序列。
将待排序的序列分成两个子序列，分别对它们进行排序。
将两个已排序的子序列合并成一个有序序列。
重复步骤1和步骤2，直到整个序列有序。
代码示例：
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int a[N], b[N];
void mergesort(int a[], int l, int r)
{
if(l == r) return ;
int mid = (l + r) / 2;
mergesort(a, l, mid);
mergesort(a, mid + 1, r);
int pl = l, pr = mid + 1, pb = l;
while(pl <= mid || pr <= r)
{
// 左半边已经放完
if(pl > mid) b[pb ++] = a[pr ++ ];
// 右半边已经放完
else if(pr > r)b[pb ++] = a[pl ++];
//两边都没有放完
else
{
if(a[pl] < a[pr])b[pb ++] = a[pl ++];
else b[pb ++ ] = a[pr ++ ];
}
}
// 完成后复制回去
for (int i = l;i <= r; ++ i)a[i] = b[i];
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n; cin >> n;
for(int i = 1;i <= n; ++ i)cin >> a[i];
mergesort(a, 1, n);
for(int i = 1;i <= n; ++ i)cout << a[i] << " \n"[i == n];
return 0;
}6.
桶排序（Bucket sort）是一种非比较的排序算法。桶排序采用一些分类和分治的思想，把元素的值域分成若干段，每一段对应一个桶。在排序的时候，首先把每一个元素放到其对应的桶中，再对每一个桶中的元素分别排序，再按顺序把每个桶中的元素依次取出 ，合并成最终答案。
对于数据量较大但值域较小的数据，如N > 10的7次方, a[i] < 10的6次方,可以做到每一个值对应一个桶,桶排序的时间复杂度为o(n) 推荐使用桶排序 。
对于值域教大的数据，桶排序的时间复杂度与每个桶内排序方法有关，优势不明显，对于这种数据一般不使用桶排序 。
代码示例：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e5 + 7;
int n;
int bucket[MAXN];
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ ) {
int x;
cin >> x;
bucket[x] ++;
}
for (int i = 0; i < MAXN; i ++ ) {
for (int j = 1; j <= bucket[i]; j ++ )
cout << i << " ";
}
}
