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 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 考研数据结构(八):八大排序算法实现(建议收藏) -> 正文阅读

[数据结构与算法]考研数据结构(八):八大排序算法实现(建议收藏)

八大排序算法

1.插入排序

(1).直接插入排序

#include <stdio.h>
#include <stdlib.h> 

// 直接插入排序

// (哨兵版本)
void insertSort1(int a[],int n) {
	// a[0] 是哨兵 
	for(int i = 2; i <= n; i ++) {
		a[0] = a[i];
		int j;
		// 找寻要插入的位置,发挥哨兵的作用 
		for(j = i - 1; a[j] > a[0]; j --) {
				a[j + 1] = a[j];
		}
		a[j + 1] = a[0];
	} 
	return ;
}

// (非哨兵版本) 
void insertSort2(int a[],int n) {
	for(int i = 2; i <= n; i ++) {
		a[0] = a[i];
		int j;
		// 寻找合适的插入位置并且移动相应的元素 
		for(j = i - 1; j >= 1; j --) {
			if(a[j] > a[0]) {
				a[j + 1] = a[j];
			} else {
				break;
			}
		} 
		a[j + 1] = a[0];
	} 
	return ;
}

int main() {
	int a[12];
	
	printf("请输入要排序的序列:\n"); 
	
	for(int i = 1; i <= 10; i ++) {
		scanf("%d",&a[i]);
	}
	
	insertSort1(a,10);
	
	printf("直接插入排序 排序后的序列:\n");
	for(int i = 1; i <= 10; i ++) {
		printf("%d ",a[i]);
	}
	
	return 0;
}

(2).折半插入排序

#include <stdio.h>
#include <stdlib.h> 

// 折半插入排序

void middleInsertSort(int a[],int n) {
	// a[0] 是哨兵 
	for(int i = 2; i <= n; i ++) {
		a[0] = a[i];
		// 折半查找合适的插入位置 
		int low = 1,high = i - 1;
		while(low <= high) {
			int mid = low + high >> 1;
			if(a[mid] > a[0]) high = mid - 1;
			else low = mid + 1;
		}
		// 后移 
		for(int j = i - 1; j >= low; j --) {
			a[j + 1] = a[j];
		}
		// 赋值 
		a[low] = a[0];
	}
	return ;
}

int main() {
	int a[12];
	
	printf("请输入要排序的序列:\n"); 
	
	for(int i = 1; i <= 10; i ++) {
		scanf("%d",&a[i]);
	}
	
	middleInsertSort(a,10);
	
	printf("折半插入排序 排序后的序列:\n");
	for(int i = 1; i <= 10; i ++) {
		printf("%d ",a[i]);
	}
	
	return 0;
}

(3).希尔排序

#include <stdio.h>
#include <stdlib.h> 

// 希尔排序

void shellSort(int a[],int n) {
	// a[0] 是哨兵 
	
	// 确定增量 
	for(int d = n / 2; d >= 1; d /= 2) {
		// 分子表
		for(int i = 1; i < d + 1; i ++) {
			// 对每个子表进行排序
			for(int j = i + d; j <= n; j ++) {
				a[0] = a[j];
				int k;
				for(k = j - d; k > 0 && a[k] < a[0]; k -= d) {
					a[k + d] = a[k];
				} 
				a[k + d] = a[0];
			} 
		} 
	} 
	
	return ;
}

int main() {
	int a[12];
	
	printf("请输入要排序的序列:\n"); 
	
	for(int i = 1; i <= 10; i ++) {
		scanf("%d",&a[i]);
	}
	
	shellSort(a,10);
	
	printf("希尔排序 排序后的序列:\n");
	for(int i = 1; i <= 10; i ++) {
		printf("%d ",a[i]);
	}
	
	return 0;
}

2.交换排序

(1).冒泡排序

#include <stdio.h>
#include <stdlib.h> 

// 冒泡排序One:元素下标从 1 开始,从后往前冒泡 
void bubbleSortOne(int a[],int n) {
	for(int i = 1; i < n; i ++) {
		for(int j = n; j > i; j --) {
			if(a[j] > a[j - 1]) {
				int temp = a[j];
				a[j] = a[j - 1];
				a[j - 1] = temp;
			}
		}
	}
	return ;
}

// 冒泡排序Two:元素下标从 1 开始,从前往后冒泡 
void bubbleSortTwo(int a[],int n) {
	for(int i = n; i > 1; i --) {
		for(int j = 1; j < i; j ++) {
			if(a[j] > a[j + 1]) {
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
	return ;
}

int main() {
	int a[12];
	
	printf("请输入要排序的序列:\n"); 
	
	for(int i = 1; i <= 10; i ++) {
		scanf("%d",&a[i]);
	}
	
	bubbleSortTwo(a,10);
	
	printf("冒泡排序(元素下标从 1 开始,从前往后冒泡) 排序后的序列:\n");
	for(int i = 1; i <= 10; i ++) {
		printf("%d ",a[i]);
	}
	
	return 0;
}

(2).快速排序

#include <stdio.h>
#include <stdlib.h> 

int partition(int a[],int low,int high) {
	// 每次选取第一个位置作为中间枢纽 
	int pivot = a[low];
	while(low < high) {
		// 从末尾开始寻找 
		while(low < high && a[high] >= pivot) high --;
		a[low] = a[high];
		// 从头部开始寻找 
		while(low < high && a[low] <= pivot) low ++;
		a[high] = a[low];
	}
	a[low] = pivot;
	return low;
}



void quickSort(int a[],int low,int high) {
	if(low < high) {
		int pos = partition(a,low,high);
		quickSort(a,low,pos - 1);
		quickSort(a,pos + 1,high);
	}
	return ;
}

int main() {
	int a[12];
	
	printf("请输入要排序的序列:\n"); 
	
	for(int i = 1; i <= 10; i ++) {
		scanf("%d",&a[i]);
	}
	
	quickSort(a,1,10);
	
	printf("快速排序 排序后的序列:\n");
	for(int i = 1; i <= 10; i ++) {
		printf("%d ",a[i]);
	}
	
	return 0;
}

3.选择排序

(1).简单选择排序

#include <stdio.h>
#include <stdlib.h> 

// 简单选择排序 
void selectSort(int a[],int n) { 
	for(int i = 1; i <= n; i ++) {
		int pos = i,value = a[i];
		for(int j = i + 1; j <= n; j ++) {
			if(a[j] < value) {
				value = a[j];
				pos = j;
			}
		}
		// 每次从未排序的序列中选取一个最小的量与当前位置进行交换 
		int temp = a[pos];
		a[pos] = a[i];
		a[i] = temp;
	}
	
	return ;
}

int main() {
	int a[12];
	
	printf("请输入要排序的序列:\n"); 
	
	for(int i = 1; i <= 10; i ++) {
		scanf("%d",&a[i]);
	}
	
	selectSort(a,10);
	
	printf("简单选择排序 排序后的序列:\n");
	for(int i = 1; i <= 10; i ++) {
		printf("%d ",a[i]);
	}
	
	return 0;
}

(2).堆排序

#include <stdio.h>
#include <stdlib.h>

/*
	堆 : 一颗完全二叉树
	大根堆 : 所有 父节点的内容 > 子节点的内容
	小根堆 : 所有 父节点的内容 < 子节点的内容  

*/

/*
	heapify : 找到 父节点, 左子节点,右子节点 三者的最大值
			  与父节点进行交换 
	不断 heapify ,就可构造一个 堆 
*/ 

/*
	堆编号的特点 : 假设 顶根堆的编号是 0,可以用一个一维数组表示这个堆
		parent = (i - 1) / 2;(向下取整)
		c1 = 2i + 1;
		c2 = 2i + 2; 
*/ 

void swap(int arr[],int i,int j) {
	int temp = arr[i];
	arr[i] = arr[j];
	arr[j] = temp;
	return ;
}

// 从某个父节点开始做 heapify 操作 
void heapify(int tree[],int n,int i) {
	// 递归出口函数 
	if(i >= n) return ; 
	// i 表示 父节点编号 
	int c1 = 2 * i + 1;
	int c2 = 2 * i + 2;
	int max = i;
	
	// 除了要保证保证最大值外还要保证 c1 和 c2 不会出界 
	if(c1 < n && tree[c1] > tree[max]) {
		max = c1;
	} 
	if(c2 < n && tree[c2] > tree[max]) {
		max = c2;
	}
	
	if(max != i) {
		swap(tree,i,max);
		// 继续做一次 heapify 
		heapify(tree,n,max);
	} 
	
	return ;
} 

void build_heap(int tree[],int n) {
	int last_node = n - 1;
	// 从最后一个节点的根节点编号开始进行heapify操作 
	int parent = (last_node - 1) / 2;
	int i;
	for(int i = parent;i >= 0; i --) {
		heapify(tree,n,i);
	}
	return ;
} 


// 每次将当前根节点与最后一个节点进行交换,之后再对根节点进行 heapify 操作 
void heap_sort(int tree[],int n) {
	build_heap(tree,n);
	int i;
	// 从最后一个节点出发 
	for(int i = n - 1; i >= 0; i --) {
		swap(tree,i,0);
		// 根节点与最后一个节点交换后再进行 heapify 操作 
		heapify(tree,i,0);
	}
	return ;
} 

int main() {
	
	int tree[] = {2,5,90,1,10,4};
	int n = 6;
	// 给与任意一个序列,构建一个堆 
//	build_heap(tree,n);
	heap_sort(tree,n); 
	
	for(int i = 0; i < n; i ++) {
		printf("%d ",tree[i]);
	}
	
	return 0;
}

4.归并排序

#include <stdio.h>
#include <stdlib.h> 

void merge(int a[],int low,int mid,int high) {
	// 开辟一个临时辅助数组 
	int b[12]; 
	for(int i = low; i <= high; i ++) {
		b[i] = a[i];
	}
	
	int i = low,j = mid + 1,k = low;
	while(i <= mid && j <= high) {
		if(b[i] > b[j]) {
			a[k ++] = b[j ++];
		} else {
			a[k ++] = b[i ++];
		}
	}
	
	while(i <= mid) a[k ++] = b[i ++];
	while(j <= high) a[k ++] = b[j ++];
	
	
	return ; 
}

// 归并排序 
void mergeSort(int a[],int low,int high) { 
	if(low < high) {
		int mid = low + high >> 1;
		// 递归操作 
		mergeSort(a,low,mid);
		mergeSort(a,mid + 1,high);
		merge(a,low,mid,high);
	}
	return ;
}

int main() {
	int a[12];
	
	printf("请输入要排序的序列:\n"); 
	
	for(int i = 1; i <= 10; i ++) {
		scanf("%d",&a[i]);
	}
	
	mergeSort(a,1,10);
	
	printf("归并排序 排序后的序列:\n");
	for(int i = 1; i <= 10; i ++) {
		printf("%d ",a[i]);
	}
	
	return 0;
}
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2021-10-20 12:44:30  更:2021-10-20 12:46:24 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 8:32:57-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码