插入排序

#include<iostream>
#include<vector>
using namespace std;

void insertSort(vector<int> &arr) {
	//插入sort 
	int key = 0;
	int j = 0; 
	for(int i = 1; i < arr.size(); i++) {
		key = arr.at(i);
		j = i - 1;
		while (j >=0 && key < arr.at(j))
		{
			arr.at(j + 1) = arr.at(j);	//向后移动
			j--;
		}
		arr.at(j+1) =key;
	}

}

int main() {
	vector<int> arr = { 12,15,9,20,6,31,24 };
	for (auto &val : arr) {
		cout << val << " ";
	}
	cout << "输出 arr 排序后:";

	insertSort(arr);
	for (auto &val : arr) {
		cout << val << " ";
	}
	cout << endl;
	return 0;
}

希尔排序

#include<iostream>
#include<vector>
using namespace std;

void  shellSort(vector<int> &arr) {
	//希尔排序 分类间隔
	int length = arr.size();
	for (int k=length/2 ; k>0;  k/=2)
	{
		for (int i = k; i < length;i++) {
			int temp = arr.at(i);
			int j = i - k;
			for(;j>=0;j-=k)		//	>=0
			{
				if (temp < arr.at(j)) arr.at(j + k) = arr.at(j);
				else break;
			}
			arr.at(j + k) = temp;
		}
	}
}

void shellSort2(vector<int> &arr) {
	//使用交换法 进行 shell 排序
	int len = arr.size();
	for (int k = len / 2; k > 0;k/=2) {		//这里的k 最小是1 即最后每一数都进行插入排序
		for (int i = k; i < len; i++) {
			for (int j = i-k; j >= 0; j -= k) {			//脚标可以为0 
				if (arr.at(j) > arr.at(j+k)) swap(arr.at(j + k), arr.at(j));
				else break;
			}
		}
	
	}
}

int main() {
	vector<int> arr = { 12,15,9,20,6,31,24 };
	cout << "希尔排序后" << "" << endl;
	shellSort2(arr);
	for (auto &val :arr) {
		cout << val << " ";
	}

	return 0;
}

选择排序

#include<iostream>
#include<vector>
using namespace std;
void selectSort(vector<int> &arr) {
	//选择排序
	for (int i = 0; i < arr.size();i++) {
		int minIndex = i;
		int minValue = arr[i];
		for (int j = i + 1; j < arr.size(); j++) {
			if(minValue >arr[j]) {
				minIndex = j;
				minValue = arr[j];
			}
		}
		swap(arr[minIndex],arr[i]);
	}
}

int main() {
	vector<int> arr = {12,15,9,20,6,31,24};
	cout << "选择排序后的arr ："<<endl;
	selectSort(arr);
	for (auto &val : arr) {
		cout << val<<" ";
	}
	return 0;
}