文档章节

常用基础排序算法

穿
 穿靴子的猫LJL
发布于 2015/10/13 14:52
字数 1592
阅读 14
收藏 0
点赞 0
评论 0

首先初始化了一个MAX大小的数组,用乱序函数将数组打乱,用于测试各个排序函数,先附上要测试的几个基础排序函数,后面附上乱序函数和主调度函数。代码就那么几行,只是注释的思乱占了比较多的行数

冒泡排序

//冒泡排序
void bubbleSort(int *array, int size)
{
	//循环1 从后向前逐个缩短比较范围,因为后面是逐个成序的
	for (int i = size - 1; i > 0; i--){
		int flag = 1;//定义标志变量,确定当一次遍历完成时候发生过交换
		//循环2 逐个遍历当前无序序列
		for (int j = 0; j < i; j++){
			//如果满足交换条件,则交换
			if (array[j]>array[j + 1]){
				swap(&array[j], &array[j + 1]);
				flag = 0;//由于发生了交换,所以标志变量置为0
			}
		}
		if (flag){//判断标志变量的值,如果此判断可以通过,则证明当遍历玩整个无序部分都没有发生一次交换,
			break;//证明整个序列都已经成序,直接跳出循环
		}
	}
}

选择排序

//选择排序
void selectSort(int *array, int size)
{
	//循环1 用于控制遍历最小值坐标,每次首先以为当前值最小,和后面所有元素开始比较
	for (int i = 0; i < size-1; i++){
		int index = i;//存储当前最小值的索引,
		//这样只在最后需要交换的时候发生一次交换,避免没有必要的交换,加快程序执行
		//循环2 用于控制遍历后面没有成序的部分和最小值比较
		for (int j = i + 1; j < size; j++){
			if (array[index]>array[j]){
				index = j;
			}
		}
		//如果最小值的索引改变了,则交换
		if (index != i){
			swap(&array[index],&array[i]);
		}
	}
}

插入排序

//插入排序
void insertSort(int *array, int size)
{
	//由于第0个元素就一个,所以是成序的,从第1个开始认为是不成序的,和前面程序部分比较
	//循环1 控制遍历后面的不成序的序列
	for (int i = 1; i < size; i++){
		int temp = array[i];//记录当前拿出来比较的值,它的位置可能被别人填充,所以记录下来
		int j = 0;
		//循环2 控制遍历从目标数前一个向前遍历成序序列,寻找目标数可插入的位置
		for (j = i - 1; j >= 0 && array[j]>temp; j--){
				array[j + 1] = array[j];
		}
		if (j!= i - 1){//当j!=i-1说明上面循环的条件进入过,执行过,所以位置需要改变
			array[j+1] = temp;//切记这里是j+1,原因是j的位置不满足条件退出,所以插入位置应该是j+1
		}
	}
}

二分插入排序

//二分插入排序,原理和插入排序相同,就是在找插入位置的时候使用了二分查找
void binaryInsertSort(int *array, int size)
{
	for (int i = 1; i < size; i++){
		int temp = array[i];
		int left = 0;
		int right = i - 1;
		//二分查找部分,这样比简单的插入排序效率更高
		while (left <= right){
			int mid = (left + right) / 2;
			if (array[mid] < temp){
				left = mid+1;
			}
			else{
				right = mid - 1;
			}
		}
		int j = 0;
		for (j = i - 1; j >= left; j--){
			array[j + 1] = array[j];
		}
		if (j != i - 1){
			array[j + 1] = temp;
		}
	}
}

二分查找循环版

//二分查找,循环版
void binarySearch(int *array, int des, int size)
{
	int left = 0;
	int right = size - 1;//这里的size是数组长度,要访问最后一个元素,就样长度减一
	int mid = 0;
	//当left和right没有错过,则证明查找范围合理,继续查找
	while (left <= right){
		//每次开始循环,都要重新确认中间位置
		mid = (left + right) / 2;
		//如果中间位置就是目标值,则找到了,跳出循环
		if (array[mid] == des){
			break;
		}
		//如果中间值大于目标,则在前半部分寻找,寻找上限编程mid-1
		if (array[mid] > des){
			right = mid - 1;
		}
		//反之,在后半部分寻找,寻找的下限变成mid+1
		else{
			left = mid + 1;
		}
	}
	//如果循环跳出的时候,还满足left<=right,则证明是因为找到了目标数,所以跳出,所以此时返回目标数索引
	if (left <= right){
		printf("\n查找成功,在数组的%d号位置\n",mid);
	}
	//反之,查找失败
	else{
		printf("\n查找失败\n");
	}
}

二分查找递归版

//递归版二分查找
int recursionBinarySearch(int *array, int left, int right, int des)
{
	//判断left和right没有错位,则查找继续
	if (left <= right){
		//确定中间位置
		int mid = (left + right) / 2;
		//判断中间位置是否是目标值,若是则返回
		if (array[mid] == des){
			return mid;
		}
		//如果中间值大于目标值,在前半部分继续寻找
		else if (array[mid] > des){
			return recursionBinarySearch(array, left, mid - 1, des);
		}
		//如果中间位置小于目标值,在后半部分寻找
		else if (array[mid] < des){
			return recursionBinarySearch(array, mid + 1, right, des);
		}
		//如果这些情况都不是,则是不合法的值,返回-1表示没找到
		else{
			return -1;
		}
	}
	//若left和right已经错过,则证明没有找到
	else{
		return -1;
	}
}

辅助的操作函数,包括 乱序函数,打印数组函数,交换元素值得函数

//交换函数
void swap(int *a, int *b)
{
	int c = *a;
	*a = *b;
	*b = c;
}
//乱序算法,从后向前遍历数组,让目前位置数和小于它的任意索引位置交换,循环完成即完成简单的乱序
void shuffle(int *array, int size)
{
	srand((unsigned int)time(NULL));
	int index = 0;
	for (int i = size-1; i >0; i--){
		index=rand()%i;
		swap(&array[i],&array[index]);
	}
}

//数组打印函数
void printArray(int *array, int size)
{
	for (int i = 0; i < size; i++){
		printf("%d\t", array[i]);
	}
}

主函数,负责测试各个排序函数

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#define MAX 100

int main()
{
	//定义并初始化数组
	int array[MAX] = { 0 };
	for (int i = 0; i < MAX; i++){
		array[i] = i;
	}
	printf("乱序数组后\n");
	shuffle(array, MAX);
	printArray(array, MAX);
	/*printf("\n冒泡排序后\n");
	bubbleSort(array, MAX);
	printArray(array, MAX);*/
	/*printf("\n选择排序后\n");
	selectSort(array, MAX);
	printArray(array, MAX);*/
	/*printf("\n插入排序后\n");
	insertSort(array, MAX);
	printArray(array, MAX);*/
	printf("\n二分插入排序后\n");
	binaryInsertSort(array, MAX);
	printArray(array, MAX);
	printf("\n二分查找 1 测试\n");
	binarySearch(array, 1, MAX);
	printf("\n递归版二分查找 1 测试\n");
	int index=recursionBinarySearch(array, 0, MAX - 1, 1);
	printf("\n查找成功,在数组的%d号位置\n", index);
	return 0;
}


© 著作权归作者所有

共有 人打赏支持
穿
粉丝 3
博文 20
码字总数 13498
作品 0
海淀
排序算法-09-冒泡排序(Bubble Sort)

Basics Sorting - 基础排序算法 算法复习——排序 算法分析 时间复杂度-执行时间(比较和交换次数) 空间复杂度-所消耗的额外内存空间 使用小堆栈或表 使用链表或指针、数组索引来代表数据 排序...

Corwien
2016/06/17
41
0
常用排序算法(Java实现)

计算机最基础的几个排序算法,在笔试面试过程中经常会被问到,解编程题时也经常会被用到。 Ⅰ.直接插入排序 Ⅱ.希尔排序: Ⅲ.冒泡排序: Ⅳ.快速排序: Ⅴ.直接选择排序: Ⅵ.堆排序 Ⅶ.二路...

waffle930
2016/09/22
6
0
8个常用算法的超常剖析

本文来自作者 jack 在 GitChat 上分享「最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析」,「阅读原文」查看交流实录 「文末高能」 「更多同类话题」 「查看全部话题」 编辑 | ...

gitchat
2017/11/30
0
0
程序员?这些面试题你能答对几个?

  三人行必有我师,人生是需要不断学习的,在这里我们相遇就是缘分,希望各位可以看完这篇文章,也欢迎大家在下面留言讨论,天冷了,也动动手指转发收藏一下,谢谢大家!   一、数据结构...

java分享
2017/12/03
0
0
Java实现几种常见排序方法(下)

插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。其具体步骤参见代码及注释。 /** 插入排序<br/> <ul> <li>从第一个元素开始,该元...

晨曦之光
2012/03/09
0
0
线程基础:多任务处理(16)——Fork/Join框架(排序算法性能补充)

1、概述 在之前的一篇文章《线程基础:多任务处理(13)——Fork/Join框架(解决排序问题)》中,我们使用了fork/join框架提高归并排序的性 能。那篇文章发布后,有的读者联系我,觉得单就归...

yinwenjie
2017/06/06
0
0
最常用的 8 个排序算法:从原理到改进,再到代码兑现透彻解析

作者:jack 1. 关于排序 很高兴与大家一起探讨计算机科学中的基础算法之排序算法。排序算法是非常基础同时又应用非常广泛的算法,无论在工作还是在生活中,比如: 数据库脚本,如MSSql, MySq...

小数点
2017/12/04
0
0
常用高级排序算法

首先初始化了一个MAX大小的数组,用乱序函数将数组打乱,用于测试各个排序函数,先附上要测试的几个基础排序函数,后面附上乱序函数和主调度函数。代码就那么几行,只是注释的思乱占了比较多...

穿靴子的猫LJL
2015/10/13
103
0
Python大牛的必学成长之路(20个经典学习资料)

想要成为Python大师,首先要从最基础知识开始学起,了解掌握Python最基础的知识点,编程意识从无都有,才能在Python 的道路上走得更远。 第一章 python基础 3课时 1小时5分钟 1、python 入门...

让往事随风
2015/12/23
26
0
Java程序员的日常—— Arrays工具类的使用

这个类在日常的开发中,还是非常常用的。今天就总结一下Arrays工具类的常用方法。最常用的就是asList,sort,toStream,equals,copyOf了。另外可以深入学习下Arrays的排序算法,这个还是非常有用...

青夜之衫
2017/12/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

nodejs安装以及环境配置(很好的node安装和配置文章,少走很多弯路)

一、安装环境 1、本机系统:Windows 10 Pro(64位) 2、Node.js:v6.9.2LTS(64位) 二、安装Node.js步骤 1、下载对应你系统的Node.js版本:https://nodejs.org/en/download/ 2、选安装目录进...

sprouting
12分钟前
0
0
Redisson

了解了Redisson,发现使用挺简单的,接下来准备深入学习一下。 Redisson介绍 Redisson是架设于Redis基础之上的一个Java驻内存数据网格(In-Memory Data Grid) Redisson在基于NIO的Netty框架上...

to_ln
13分钟前
0
0
python有哪些好玩的应用实现,用python爬虫做一个二维码生成器

python爬虫不止可以批量下载数据,还可以有很多有趣的应用,之前也发过很多,比如天气预报实时查询、cmd版的实时翻译、快速浏览论坛热门帖等等,这些都可以算是爬虫的另一个应用方向! 今天给...

python玩家
13分钟前
0
0
jq 判断复选框是否被选中,复选框后台接收

1. 效果 2. 代码 html部分: JS部分: var rememberLogin = $("#rememberLoginId").is(':checked')//获取复选框是否被选中 var rememberLoginval = $("#rememberLoginId").attr('value')//拿......

Lucky_Me
20分钟前
0
0
python爬虫日志(3)-爬去异步加载网页

在浏览器检查元素页面中,选取Network中的XHR选项即可观察每次加载页面,网页发出的请求,观察url的规律即可利用封装的函数对每一页进行爬取。

茫羽行
20分钟前
0
0
《趣谈网络协议》之为什么要学习网络协议?

一、协议 1.协议的定义 简单说协议就是一个规则,保证沟通交流双方可以互相听懂、理解或者可以双方合作可以顺利进行的一个约定和规则。 2.生活中例子 (1)有一种叫“程序猿”的物种,敲着一种...

aibinxiao
22分钟前
1
0
Python数据分析numpy基础-维度的认识

什么是多维数组? 核心对象是同型的多维数组(简单理解就是一个表格,通常内容都是些数字),具有相同的数据类型。 概念: 1. axes(轴):数组的维度统称为轴。 2. rank:轴的数量称为rank。...

十年磨一剑3344
26分钟前
0
0
Java 正则表达式相关资料

1.java正则表达式过滤html标签

IT追寻者
29分钟前
0
0
点赞出现数字变大效果

<!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <title>Title</title> <style> .container{ padding: 50px; border: 1px solid #dddddd; } .item{ position: relative; } ......

南桥北木
48分钟前
0
0
anroid中批量将px转换成dp

package com.qu;import java.io.File;import java.io.FileWriter;import java.io.IOException;public class Aaaa {public static void main(String[] args) {String fi......

android-key
49分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部