数据结构--七大排序算法（更新ing）

        下面算法编写的均是按照由小到大排序版本

---

选择排序

思想：

        每次遍历待排序元素的最大下标，与待排序元素中最后一个元素交换位置（此时需要设置一个临时变量来存放下标）

        时间复杂度--O(n^2)

        空间复杂度--O(1)

        稳定性--不稳定

代码实现

#include
using namespace std;
const int N = 1e2 + 10;
int num[N];
int n;
 
void select_sort()
{
	for (int i = 1; i < n; i++)//控制找最大值的次数
	{
		int index = 1;//存待排序元素的最小元素的下标
		for (int j = 1; j <= n - i; j++)
		{
			if (num[index] < num[j])
				index = j;
		}
		swap(num[index],num[n-i]);
	}
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> num[i];
	}
	select_sort();
	for (int i = 1; i <= n; i++) cout << num[i] << " " << endl;
}

冒泡排序 

思想：

        相邻两个元素比较，前一个比后一个大则交换

（每遍历一次都会冒出最大值 每次遍历最后一个一定是最大的）

        时间复杂度--O(n^2)  （逆序时达到O(n^2)）

        空间复杂度O(--1)

        稳定性--稳定

优化：

        当整个数组遍历过程中没有发生交换，说明待排序数组已经有序，直接结束排序过程（bool类型变量做标记)

代码实现

#include 
using namespace std;
const int N = 1e2 + 10;
int num[N];
int n;
 
void bubble_sort()
{
    for (int i = 1; i < n; i++)
    {
        bool flag = false;
        for (int j = 1; j <= n - i; j++)
        {
            if (num[j] > num[j + 1])
            {
                swap(num[j], num[j + 1]);
                flag = true;
            }
        }
        if (!flag) break;
    }
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> num[i];
    }
    bubble_sort();
    for (int i = 1; i <= n; i++)
    {
        cout << num[i] << " ";
    }
    return 0;
}