您现在的位置是:首页 > 正文

数据结构 | 交换排序

2024-02-01 05:48:32阅读 2

交换排序包括冒泡排序、快速排序。算法复杂度以及稳定性如下:

一、冒泡排序

#include <stdio.h>

typedef int ElemType;

/* 交换函数 */
void sawp(ElemType* a, ElemType* b) {
	ElemType temp;
	temp = *a;
	*a = *b;
	*b = temp;
}

/* 冒泡排序 */
void BubbleSort(ElemType a[], int n) {
	for (int i = 0; i < n - 1; i++) {
		int flag = 0;
		for (int j = n - 1; j > i; j--) {
			if (a[j - 1] > a[j]) {
				sawp(&a[j - 1], &a[j]);
				flag = 1;
			}
		}
		if (flag == 0)
			return;
	}
}

/* 打印结果 */
void SortPrint(ElemType* a, int len) {
	printf("冒泡排序: ");
	for (int i = 0; i < len; i++)
		printf("%d ", a[i]);
}

int main() {
	ElemType a[] = { 12,3,22,1,15,32,88,7,9 };
	int len = sizeof(a) / sizeof(a[0]);

	BubbleSort(a, len);
	SortPrint(a, len);
}

二、快速排序 

#include<stdio.h>

typedef int ElemType;

/* 划分操作 */
int Partition(ElemType A[], int low, int high) {
    ElemType 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(ElemType* a, int low, int high) {
    if (low < high) {
        int pivotops = Partition(a, low, high);
        QuickSort(a, low, pivotops - 1);
        QuickSort(a, pivotops + 1, high);
    }
}

/* 打印结果 */
void SortPrint(ElemType* a, int len) {
    printf("快速排序:");
    for (int i = 0; i < len; i++)
        printf("%d ", a[i]);
}

int main() {
    ElemType a[] = { 12,3,22,4,44,44,1,5,32,88,7,9 };
    int len = sizeof(a) / sizeof(a[0]);

    QuickSort(a, 0, len - 1);
    SortPrint(a, len);
    return 0;
}

网站文章

  • stanford corenlp命名实体识别(基于python)

    stanford corenlp命名实体识别(基于python)

    很多童鞋在用stanford-core-nlp进行命名实体识别时遇到了各种问题,在此本人根据已有经验讲述如何成功利用stanford工具进行命名实体识别处理。 1. 环境安装 需要用到的有java_j...

    2024-02-01 05:48:27
  • Count and Say --leetcode

    Count and Say --leetcode题目如下The count-and-say sequence is the sequence of integers beginning as follows:1, 11, 21, 1211, 111221, ...1 is read off as "one 1" or 11.11 is rea

    2024-02-01 05:48:19
  • paddle-serving docker部署,dockerfile一键打镜像,一键启动容器

    一、服务端dockfile编写 节省镜像空间,此处在python的镜像基础上构建,最终镜像2.38G FROM python:3.7.4 COPY . /deploy WORKDIR /deploy ...

    2024-02-01 05:48:13
  • 2D空间求一点是否在多边形内

    2D空间求一点是否在多边形内

    转自:https://www.cnblogs.com/hont/p/6105997.html大致流程:1.随便选取多边形上任意一条边,以比较点和边的中心点做一条射线(这里用的伪射线)。2.用这条射线与...

    2024-02-01 05:47:43
  • docker化笔记二、镜像应用服务日志输出到宿主机器

    本章以日志为例进行说明,仅作抛砖引玉,实际项目不应该以这种方式去搜集日志(常用Syslog日志驱动类型,再用日志分析工具,比如ELK,进行获取搜集)。如果容器重新启动,使用docker logs看到的...

    2024-02-01 05:47:38
  • Java 限制前端重复请求

    Java 限制前端重复请求

    2024-02-01 05:47:33
  • Java:常用类解析5(正则表达式)

    正则表达式不仅仅是Java的技术,在任何一门编程语言中都会存在,是一种通用的IT技术。除了有一些由于语言不同而导致的一些语法不同,其理念和用法在任何编程语言中基本一致。正则表达式,主要用于匹配(查找 ...

    2024-02-01 05:47:00
  • 现在.net的web框架有哪些?

    https://www.zhihu.com/question/366937369

    2024-02-01 05:46:53
  • 【Linux】CentOS7 常用命令集合 热门推荐

    【Linux】CentOS7 常用命令集合 热门推荐

    这两天一直在对CentOS 7.2进行初体验,各种学习命令肿么用,不过其实大多和DOS是一样的,只是命令的表达上可能有点儿不一样,毕竟这些都不是一家出来的嘛~这里就分享一些近期我常用的CentOS命令给大家,方便学习~

    2024-02-01 05:46:24
  • 使用jdom获取xml中多个相同标签的值

    使用jdom获取xml中多个相同标签的值

    1.导入的maven包 <dependency> <groupId>dom4j</groupId> <artifactId>dom4j</artifactId> <version>1.6.1</version> </dependency> <dependency...

    2024-02-01 05:46:17