排序算法合集(简单选择排序，插入排序，希尔排序，堆排序，冒泡排序，快速排序

1.插入排序

插入排序是每次将一个数插入到前面已经排好序的部分中

实现代码:

void InsertSort(vector &nums) {
	cout << "插入排序" << endl;
	int i, j, temp;
	for (i = 1; i < nums.size(); i++) {
		if (nums[i] < nums[i - 1]) {
			temp = nums[i];
			for (j = i - 1; j >= 0 && nums[j] > temp; j--) {
				nums[j + 1] = nums[j];
			}
			nums[j+1] = temp;
		}
		PrintNums(nums);
	}
}

 时间复杂度:

最好情况(原本全部有序） O(n)

最坏情况(逆序)  o(n2)

平均时间复杂度o(n2)

稳定性:稳定

优化思路:

可以将插入位置的搜索改为二分查找

2.希尔排序

将原来序列分成多个子表，不断对子表进行插入排序。缩小子表中元素的间距直到d=1时停止

实现代码

void ShellSort(vector& nums) {
	cout << "希尔排序" << endl;
	vector dNums = { 5,3,1 };
	int i,j,temp;
	for (int d : dNums) {
		for (i = d; i < nums.size(); i++) {
			if (nums[i] < nums[i - d]) {
				temp = nums[i];
				for (j = i - d; j >= 0 && temp < nums[j]; j -= d) {
					nums[j + d] = nums[j];
				}
				nums[j + d] = temp;
			}
			PrintNums(nums);
		}
	}

 时间复杂度：与增量序列d有关，最坏为o(n2)

稳定性：不稳定

3.快速排序

在待排序表中取数枢轴元素，通过一趟排序将原表划分成为左边小于枢轴右边大于枢轴的两部分。然后分别递归地对两个子表重复上述过程。

代码:

int Partition(vector& nums, int low, int high) {
	int pivot = nums[low];
	while (low < high) {
		while (low < high && nums[high] >= pivot) --high;
		nums[low] = nums[high];
		while (low < high && nums[low] <= pivot) ++low;
		nums[high] = nums[low];
	}
	nums[low] = pivot;
	return low;
}
void QuickSort(vector& nums,int low,int high) {
	PrintNums(nums);
	if (low < high) {
		int pivot = Partition(nums, low, high);
		QuickSort(nums, low, pivot - 1);
		QuickSort(nums, pivot + 1, high);
	}
}

 时间复杂度:

最好O(nlog2n)

最坏O(n2)

空间复杂度

最好o(log2n)

最坏o(n)

稳定性

不稳定

4.简单选择排序

在每一轮的排序元素中选择最小的加入有序子序列

代码

void EasySort(vector& nums) {
	cout << "简单选择排序" << endl;
	int temp;
	for (int i = 0; i < nums.size()-1; i++) {
		int min = i;
		for (int j = i+1; j < nums.size(); j++) {
			if (nums[j] < nums[min]) {
				min = j;
			}
		}
		swap(nums[i], nums[min]);
		PrintNums(nums);
	}
}

时间复杂度o(n2)

稳定性：不稳定

优化:每一轮排序中同时选择最小的和最大的元素

void EasySort2(vector& nums) {
	cout << "简单选择排序2" << endl;
	int i, j, min, max;
	for(i = 0 ; i < nums.size()-1-i;i++){
		min = max = i;
		for (j = i + 1; j < nums.size() - i; j++) {
			if (nums[j] < nums[min]) min = j;
			else if (nums[j] > nums[max]) max = j;
		}
		if (min != i) {
			Swap(nums[min], nums[i]);
		}
		if (max != nums.size() - i - 1) {
			if (max==i) Swap(nums[min],nums[nums.size()-i-1]);
			else Swap(nums[max], nums[nums.size() - i - 1]);
		}
	}
	PrintNums(nums);
}

5.堆排序

建立大根堆，每一趟选出堆顶元素加入序列

void HeapAdjust(vector& nums, int k,int len) {
	int temp = nums[k];
	for (int i = 2 * k; i < len; i *= 2) {
		if (i < len - 1 && nums[i] < nums[i + 1]) i++;
		if (temp >= nums[i]) break;
		else {
			nums[k] = nums[i];
			k = i;
		}
	}
	nums[k] = temp;
}
void BuildMaxHeap(vector& nums) {
	for (int i = nums.size()/ 2; i >= 0; i--)
		HeapAdjust(nums, i,nums.size());
}
void HeapSort(vector& nums) {
	cout << "堆排序" << endl;
	BuildMaxHeap(nums);
	for (int i = nums.size() - 1; i > 0; i--) {
		swap(nums[i], nums[0]);
		HeapAdjust(nums, 0,i);
		PrintNums(nums);
	}
}

时间复杂度 o(nlog2n),不稳定

6.冒泡排序

这个不单独写了看下面的总代码吧

总代码:

#include
#include
using namespace std;
void PrintNums(vector nums) {
	for (int i = 0; i < nums.size(); i++) {
		cout << nums[i] << " ";
	}
	cout << endl;
}
void Swap(int& a, int& b) {
	int temp;
	temp = a;
	a = b;
	b = temp;
}
void InsertSort(vector &nums) {
	cout << "插入排序" << endl;
	int i, j, temp;
	for (i = 1; i < nums.size(); i++) {
		if (nums[i] < nums[i - 1]) {
			temp = nums[i];
			for (j = i - 1; j >= 0 && nums[j] > temp; j--) {
				nums[j + 1] = nums[j];
			}
			nums[j+1] = temp;
		}
		PrintNums(nums);
	}
}
void ShellSort(vector& nums) {
	cout << "希尔排序" << endl;
	vector dNums = { 5,3,1 };
	int i,j,temp;
	for (int d : dNums) {
		for (i = d; i < nums.size(); i++) {
			if (nums[i] < nums[i - d]) {
				temp = nums[i];
				for (j = i - d; j >= 0 && temp < nums[j]; j -= d) {
					nums[j + d] = nums[j];
				}
				nums[j + d] = temp;
			}
			PrintNums(nums);
		}
	}
}
int Partition(vector& nums, int low, int high) {
	int pivot = nums[low];
	while (low < high) {
		while (low < high && nums[high] >= pivot) --high;
		nums[low] = nums[high];
		while (low < high && nums[low] <= pivot) ++low;
		nums[high] = nums[low];
	}
	nums[low] = pivot;
	return low;
}
void QuickSort(vector& nums,int low,int high) {
	PrintNums(nums);
	if (low < high) {
		int pivot = Partition(nums, low, high);
		QuickSort(nums, low, pivot - 1);
		QuickSort(nums, pivot + 1, high);
	}
}
void EasySort(vector& nums) {
	cout << "简单选择排序" << endl;
	int temp;
	for (int i = 0; i < nums.size()-1; i++) {
		int min = i;
		for (int j = i+1; j < nums.size(); j++) {
			if (nums[j] < nums[min]) {
				min = j;
			}
		}
		swap(nums[i], nums[min]);
		PrintNums(nums);
	}
}
void EasySort2(vector& nums) {
	cout << "简单选择排序2" << endl;
	int i, j, min, max;
	for(i = 0 ; i < nums.size()-1-i;i++){
		min = max = i;
		for (j = i + 1; j < nums.size() - i; j++) {
			if (nums[j] < nums[min]) min = j;
			else if (nums[j] > nums[max]) max = j;
		}
		if (min != i) {
			Swap(nums[min], nums[i]);
		}
		if (max != nums.size() - i - 1) {
			if (max==i) Swap(nums[min],nums[nums.size()-i-1]);
			else Swap(nums[max], nums[nums.size() - i - 1]);
		}
	}
	PrintNums(nums);
}
void HeapAdjust(vector& nums, int k,int len) {
	int temp = nums[k];
	for (int i = 2 * k; i < len; i *= 2) {
		if (i < len - 1 && nums[i] < nums[i + 1]) i++;
		if (temp >= nums[i]) break;
		else {
			nums[k] = nums[i];
			k = i;
		}
	}
	nums[k] = temp;
}
void BuildMaxHeap(vector& nums) {
	for (int i = nums.size()/ 2; i >= 0; i--)
		HeapAdjust(nums, i,nums.size());
}
void HeapSort(vector& nums) {
	cout << "堆排序" << endl;
	BuildMaxHeap(nums);
	for (int i = nums.size() - 1; i > 0; i--) {
		swap(nums[i], nums[0]);
		HeapAdjust(nums, 0,i);
		PrintNums(nums);
	}
}
void BubbleSort(vector& nums){
	cout << "冒泡排序" << endl;
	for (int i = 0; i < nums.size()-1; i++) {
		for (int j = 0; j < nums.size() - i -1; j++) {
			if (nums[j] > nums[j + 1]) {
				swap(nums[j], nums[j + 1]);
			}
		}
		PrintNums(nums);
	}
}
void HeapDelete(vector& nums) {
	BuildMaxHeap(nums);
	PrintNums(nums);
	cout << "输入要删除的元素位置(0> i;
	nums[i] = nums[nums.size() - 1];
	nums.pop_back();
	HeapAdjust(nums, i, nums.size() - 1);
	PrintNums(nums);
}
int main() {
	while (1) {
		vector nums = { 265,301,751,129,937,863,742,694,76,438 };
		int type;
		cout << "(1)简单选择排序(2)堆排序(3)直接插入排序(4)希尔排序（增量分别为5、3、1）(5)冒泡排序(6)快速排序(7)删除堆元素" << endl;
		cin >> type;
		switch (type)
		{
		case 1:
			EasySort2(nums);
			break;
		case 2:
			HeapSort(nums);
			break;
		case 3:
			InsertSort(nums);
			break;
		case 4:
			ShellSort(nums);
			break;
		case 5:
			BubbleSort(nums);
			break;
		case 6:
			QuickSort(nums, 0, nums.size() - 1);
			break;
		case 7:
			cout << "堆删除元素" << endl;
			HeapDelete(nums);
			break;
		default:
			break;
		}
	}
}