[c++][笔记]浅谈几种排序方式---冒泡排序，选择排序，桶排序

一、algorithm里的sort函数 

#include <cstdio> // 数据小的可以用iostream
#include <algorithm> // 不能忘记算法库，否则会编译失败。
using namespace std;
int main()
{
    int n;
    scanf("%d", &n);
    int a[n+5] = {};
    for (int i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i++){
        printf("%d", a[i]);
    }
    return 0;
}

二、冒泡排序

#include<iostream> //包含输入输出头文件
#include<cmath>
using namespace std; //指定名字空间
int main() 
{ //主函数
	int a[100]; //定义数组，大小100
	int N; //元素的实际个数
	int i = 0, j = 0; //循环变量，并进行初始化
	cin >> N; //输入元素个数
			  //-------输入数据-----------
	for (i = 0; i<N; i++) //输入N个元素
		cin >> a[i]; //循环体只有一行
					 //-------排序---------------
	for (i = 0; i<N - 1; i++) { //控制n-1趟冒泡
		for (j = 0; j<N - 1 - i; j++)
		{
			if (a[j]>a[j + 1]) { //比较相邻的两个元素
				int tmp; //临时变量
				tmp = a[j]; //交换
				a[j] = a[j + 1];
				a[j + 1] = tmp;
			}
		}
	}
	//--------输出----------
	for (i = 0; i<N; i++) 
	{ //使用循环，输出N个元素
		cout << a[i] << " "; //输出a[i], 后加空格，不换行
	}
	cout << endl; //所有元素输出完之后才换行
	return 0; //函数返回
}

三、桶思想

#include <iostream>
using namespace std;
int n, x, a[1001];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> x;
        a[x]++;
    }
    for (int i = 1; i <= 100; i++){
        for (int j = 1; j <= a[i]; j++){
            cout << i << " ";
        }
    }
    return 0;

桶思想需要知道所有数据的大小范围，从而创建足够数量的桶，在数字对应编号的桶中放入元素，最后利用桶数组的下标本身的顺序性，判断是否有以及有几个元素即可倒推出排序后的数组。

四、选择排序

void select_sort(int a[], size_t len)
{
	int index = 0;
	for (int i = 0; i < len-1; i++)
	{
		index = i;
		for (int j = i+1; j < len; j++)
		{
			//找最小元素下标
			if (a[j] < a[index])
			{
				index = j;
			}
 
		}
		//将最小元素下标和排序序列的起始位置交换
		swap(a[i], a[index]);
	}
}

选择排序与冒泡排序不同的是，冒泡排序是依次相邻两个比较，最后推到一侧的一定是最值。选择排序是先定位置，比如我要先找第一位的，就只拿现在第一位的去跟其他每一个比，这样下来一圈也选出了最值