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

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

---

选择排序

思想：

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

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

        空间复杂度--O(1)

        稳定性--不稳定

代码实现

#include<iostream>
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 <iostream>
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;
}