IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 排序算法-C++ -> 正文阅读

[数据结构与算法]排序算法-C++

1.冒泡排序

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

void bubbleSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) {
		return;
	}
	for (int i = n - 1; i > 0; i--) {
		for (int j = 0; j < i; j++) {
			if (data[j] > data[j + 1]) {
				swap(data[j], data[j + 1]);
			}
		}
	}
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	bubbleSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

2.选择排序

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

void selectSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) return;

	for (int i = 0; i < n - 1; i++) {
		int minIndex = i;
		for (int j = i + 1; j < n; j++) {
			if (data[j] < data[minIndex]) minIndex = j;
		}
		swap(data[minIndex], data[i]);
	}
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	selectSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

3.插入排序

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

void insertSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) return;
	for (int i = 1; i < n; i++) {
		for (int j = i - 1; j >= 0 && data[j] > data[j + 1]; j--) {
			swap(data[j], data[j + 1]);
		}
	}
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	insertSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

4.快速排序

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

int partation(vector<int> &data, int left, int right) {
	int key = data[right];
	int less = left - 1;
	int more = right;
	int index = left;
	while (index < more)
	{
		if (data[index] > key) {
			swap(data[index], data[--more]);
		}
		else if (data[index] < key) {
			swap(data[index++], data[++less]);
		}
		else {
			index++;
		}
	}
	swap(data[right], data[index]);
	return index;
}

void quick(vector<int> &data, int left, int right) {
	if (left < right) {
		int s = partation(data, left, right);
		quick(data, left, s - 1);
		quick(data, s + 1, right);
	}
}

void quickSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) return;
	quick(data, 0, n - 1);
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	quickSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

5.归并排序

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

void merge(vector<int> &data, int left, int mid, int right) {
	vector<int> tool;
	int p = left;
	int q = mid + 1;
	while (p <= mid && q <= right) {
		if (data[p] <= data[q]) tool.emplace_back(data[p++]);
		else {
			tool.emplace_back(data[q++]);
		}
	}
	while (p <= mid)
	{
		tool.emplace_back(data[p++]);
	}
	while (q <= right) {
		tool.emplace_back(data[q++]);
	}
	for (auto &item : tool) {
		data[left++] = item;
	}
}

void progress(vector<int> &data, int left, int right) {
	if (left >= right) return;

	int mid = left + (right - left) / 2;
	progress(data, left, mid);
	progress(data, mid + 1, right);
	merge(data, left, mid, right);
}

void mergeSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) return;
	progress(data, 0, n - 1);
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	mergeSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

6.堆排序

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

void heapInsert(vector<int> &heap, int index) {
	while (heap[(index - 1) / 2] < heap[index]) {
		swap(heap[index], heap[(index - 1) / 2]);
		index = (index - 1) / 2;
	}
}

void heapIfy(vector<int> &heap, int index, int heapSize) {
	int left = 2 * index + 1;
	while (left < heapSize)
	{
		int largest = left + 1 < heapSize && heap[left + 1] > heap[left] ? left + 1 : left;
		largest = heap[largest] > heap[index] ? largest : index;
		if (largest == index) break;
		swap(heap[largest], heap[index]);
		index = largest;
		left = 2 * largest + 1;
	}
}

void heapSort(vector<int> &data) {
	int n = data.size();
	if (n < 2) return;
	for (int i = 0; i < n; i++) {
		heapInsert(data, i);
	}
	swap(data[0], data[--n]);
	while (n > 0) {
		heapIfy(data, 0, n);
		swap(data[0], data[--n]);
	}
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	heapSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

7.希尔排序

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

void shellSort(vector<int> &data) {
	int n = data.size();
	for (int gap = n / 2; gap > 0; gap /= 2) {
		for (int i = gap; i < n; i++) {
			int j = i;
			while (j - gap >= 0 && data[j] < data[j - gap]) {
				swap(data[j], data[j - gap]);
				j -= gap;
			}
		}
	}
}

int main() {
	vector<int> data = { 9, 4, 2, 7, 0, 1, 6, 5, 8, 3 };
	shellSort(data);

	for (auto &item : data) {
		cout << item << " ";
	}
	system("pause");
	return 0;
}

  数据结构与算法 最新文章
LeetCode 114. 二叉树展开为链表(一题三吃
数据结构-单向链表的操作(详细思路和实例)
力扣二叉树--对称二叉树从上向下打印二叉树
[C题目]力扣142. 环形链表 II
数据结构_链表OJ特别篇——环形链表
【LeetCode刷题】动态规划实战——完全背包
C语言--递归实现字符串逆序
【LeetCode】380. O(1) 时间插入、删除和获
【题解】ARC125 C - LIS to Original Seque
【Java】浅谈Java数组的定义与使用
上一篇文章      下一篇文章      查看所有文章
加:2021-08-13 12:32:05  更:2021-08-13 12:33:48 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年8日历 -2022/8/7 23:53:15-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码