一、选择排序
选择出数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。进行的操作次数 n*(n-1)/2
int main() {
vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
for (int i = 0; i < arr.size() - 1; i++) {
int minn = arr[i],index=i;
for (int j = i+1; j < arr.size(); j++) {
if (arr[j] < minn) {
minn = arr[j];
index = j;
}
}
arr[index] = arr[i];
arr[i] = minn;
}
for (int i = 0; i < arr.size(); i++) cout << arr[i];
return 0;
}二、冒泡排序
从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。在一轮循环中，如果没有发生交换，就说明数组已经是有序的，此时可以直接退出。需要最多的操作次数 n*(n-1)/2
int main() {
vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
for (int i = arr.size()-1; i>0; i--) {
int flag = 0;
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
//用异或进行元素交换
arr[j] = arr[j] ^ arr[j + 1];
arr[j+1] = arr[j] ^ arr[j + 1];
arr[j] = arr[j] ^ arr[j + 1];
flag = 1;
}
}
//在一轮循环中没有进行元素交换，说明当前数组已经有序
if (flag == 0) break;
}
for (int i = 0; i < arr.size(); i++) cout << arr[i];
return 0;
}三、插入排序
每次都将当前元素插入到左侧已经排序的数组中，使得插入之后左侧数组依然有序。最坏的情况是数组是倒序的，需要进行 n(n-1)/2次比较和 n(n-1)/2次交换，最好的情况是数组已经是有序的，需要进行n-1次比较和0次交换。插入排序每次只能交换相邻元素，令逆序数量减少 1，因此插入排序需要交换的次数为逆序数量。
int main() {
vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
for (int i = 1; i < arr.size(); i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
arr[j] = arr[j] ^ arr[j + 1];
arr[j+1] = arr[j] ^ arr[j + 1];
arr[j] = arr[j] ^ arr[j + 1];
}
}
for (int i = 0; i < arr.size(); i++) cout << arr[i];
return 0;
}四、希尔排序
插入排序每次只能交换相邻的逆序元素，对于大规模的数组，排序很慢。希尔排序则是通过交换不相邻的元素，每次可以将逆序数量减少大于 1，加快了排序速度。
int main() {
vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
int h = arr.size() / 2;//需要设置希尔常量
while (h) {
for (int i = h; i < arr.size(); i++) {
for (int j = i - h; j >= 0 && arr[j] > arr[j + h]; j -= h) {
arr[j] = arr[j] ^ arr[j + h];
arr[j+h] = arr[j] ^ arr[j + h];
arr[j] = arr[j] ^ arr[j + h];
}
}
h /= 2;
}
for (int i = 0; i < arr.size(); i++) cout << arr[i];
return 0;
}五、归并排序
将待排序的数组不断地分成两部分，对不同部分的元素分别进行排序，然后归并起来。（空间复杂度为什么是n）
vector<int> merge(vector<int>&a, vector<int>&b) {
if (a.empty()) return b;
else if (b.empty()) return a;
else {
vector<int> res;
int a1 = a.size(), b1 = b.size(), i = 0, j = 0;
while (i < a1&&j < b1) {
if (a[i] < b[j]) {
res.push_back(a[i]);
i++;
}
else {
res.push_back(b[j]);
j++;
}
}
while (i < a1) {
res.push_back(a[i]); i++;
}
while (j < b1) {
res.push_back(b[j]); j++;
}
return res;
}
}
vector<int> fun(vector<int> &array, int l, int r) {
if (l > r) {
vector<int> t = {};
return t;
}
if (l == r) {
vector<int> t;
t.push_back(array[l]);
return t;
}
else {
vector<int> left = fun(array, l, (l + r) / 2);
vector<int> right = fun(array, (l + r) / 2 + 1, r);
return merge(left,right);
}
}
int main() {
vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
int l = 0, r = arr.size() - 1;
vector<int> res = fun(arr, l, r);
for (int i = 0; i < res.size(); i++) cout << res[i];
return 0;
}六、快速排序
首先从待排序的数组中选择一个元素作为比较的基准，然后遍历一遍数组，将所有比这个值小的元素放到左边，比这个值大的元素放到右边，最后分别对左边和右边的元素重复上述过程，直到所有元素都排好序
void quickSort(vector<int>&a, int low, int high)
{
if (low < high) //判断是否满足排序条件，递归的终止条件
{
int i = low, j = high; //把待排序数组元素的第一个和最后一个下标分别赋值给i,j，使用i,j进行排序；
int x = a[low]; //将待排序数组的第一个元素作为哨兵，将数组划分为大于哨兵以及小于哨兵的两部分
while (i < j)
{
while (i < j && a[j] >= x) j--; //从最右侧元素开始，如果比哨兵大，那么它的位置就正确，然后判断前一个元素，直到不满足条件
if (i < j) a[i++] = a[j]; //把不满足位次条件的那个元素值赋值给第一个元素，（也即是哨兵元素，此时哨兵已经保存在x中，不会丢失）并把i的加1
while (i < j && a[i] <= x) i++; //换成左侧下标为i的元素开始与哨兵比较大小，比其小，那么它所处的位置就正确，然后判断后一个，直到不满足条件
if (i < j) a[j--] = a[i]; //把不满足位次条件的那个元素值赋值给下标为j的元素，（下标为j的元素已经保存到前面，不会丢失）并把j的加1
}
a[i] = x; //完成一次排序，把哨兵赋值到下标为i的位置，即前面的都比它小，后面的都比它大
quickSort(a, low, i - 1); //递归进行哨兵前后两部分元素排序 ， low,high的值不发生变化，i处于中间
quickSort(a, i + 1, high);
}
}
int main() {
vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
int l = 0, r = arr.size() - 1;
quickSort(arr, l, r);
for (int i = 0; i < arr.size(); i++) cout << arr[i];
return 0;
}七、堆排序
首先将待排序序列构造成一个大根堆，将根节点与末尾元素交换，此时末尾就为最大值，然后将剩下的前n-1个元素重新构造大根堆，并将该根节点与倒数第二个数交换得到第二大的数字，如此反复循环，最终得到一个有序序列。
void adjuct(vector<int>&arr, int i,int len) {
int l = i * 2 + 1;
int r = i * 2 + 2;
//找出当前节点与它的左右孩子节点中值最大的节点
int index = i, maxval = arr[i];
if (l<len && arr[l]>maxval) { maxval = arr[l]; index = l; }
if (r<len && arr[r]>maxval) { maxval = arr[r]; index = r; }
if (index != i) {
//调整节点并递归
arr[index] = arr[i];
arr[i] = maxval;
adjuct(arr, index,len);
}
}
int main() {
vector<int> arr = { 5,7,2,4,9,8,0,1,3,6 };
//1.建堆，自下而上
int len = arr.size();
for (int i = len / 2 - 1; i >= 0; i--) adjuct(arr, i,len);
//2.排序
for (int i = len - 1; i > 0; i--) {
int tmp = arr[i];
arr[i] = arr[0];
arr[0] = tmp;
adjuct(arr, 0, i);
}八、桶排序
将待排序序列中处于同一个值域的元素存入同一个桶中，则拆分后形成的多个桶，从值域上看是处于有序状态的。对每个桶中元素进行排序，则所有桶中元素构成的集合是已排序的。
##九、性能复杂度比较
京公网安备 11010502036488号