首页 > 编程语言 >排序算法

排序算法

时间:2022-12-05 19:12:48浏览次数:43  
标签:10005 code int void pos ++ 算法 排序

排序

简单排序

插入排序

普 code

点击查看代码
int n, cnt = 0;		 // 数组长度 插入数组长度 
int a[10005], r[10005];	 // 原数组 插入数组 

void InsertSort(int x) { // 插入 x 
  int pos = 0;	         // 记录 x 应插入的位置 
  
  while (pos < cnt && r[pos] < x) pos++;
        		 // 直到找到大于等于 x 的数 
  for (int i = cnt; i > pos; i--)
  	r[i] = r[i-1];
                         // 后移数组 
		
  r[pos] = x;
  cnt++;		 // 插入数组长度加一 
}

空间优化 code

点击查看代码
int n;
int a[10005];

void InsertSort() {
 for (int i = 0; i < n; i++) {
 	int pos = 0, x = a[i];
	while (pos < i && a[pos] < a[i]) pos++;		
	for (int k = i; k > pos; k--)
	    a[k] = a[k-1];
	
	a[pos] = x;
   }
} 

冒泡排序

普 code

点击查看代码
void bubble_sort(int* a, int n) {
bool f = 1;
	
while (f) {
	bool f = 0;
	for (int i = 1; i < n; i++)
		if (a[i] > a[i+1]) swap(a[i], a[i+1]), f = 1;
  }
	
return ;
}

常数优化 code

点击查看代码
int n;
int a[10005];

void BubbleSort(int n, int a[]) {
for (int i = 0; i < n; i++) {
	for (int j = 0; j < n - i - 1; j++) {
		if (a[j] > a[j+1]) swap(a[j], a[j+1]);
	}
  }
}

选择排序

普 code

点击查看代码
int n;
int a[10005];

void SelectSort(int n, int a[]) {
	for (int i = 0; i < n; i++) {
		int key = i;
		
		for (int j = i + 1; j < n; j++)
			if (a[j] < a[key]) key = j;
			
		swap(a[i], a[key]);
	}
}

优化 code

点击查看代码
int n;
int a[10005];

void SelectSort(int n, int a[]) {
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++)
			if (a[j] < a[i]) swap(a[j], a[i]);
	}
}

复杂度

时间复杂度

插入排序

O (n ^ 2)

冒泡排序

O (n ^ 2)

选择排序

O (n ^ 2)

实用排序

归并排序

O (n log n)

code

点击查看代码
int n;
int a[10005], t[10005];        // a 原数组 t 排序数组 

void MergeSort(int l, int r) {
	if (l == r - 1) return ;
	
	int mid = (l + r) >> 1;
	
	MergeSort(l, mid); MergeSort(mid, r);
	
	int p = l, q = mid, k = l;
	
	while (p < mid && q < r) {
		if (a[p] < a[q]) t[k++] = a[p++];
		else t[k++] = a[q++];
	}
	
	while (p < mid) t[k++] = a[p++]; // 复制剩余数组 
	while (q < r) t[k++] = a[q++];
	
	for (int i = l; i < r; i++)
		a[i] = t[i];
}

快速排序

O (n log n)

code

点击查看代码
int n;
int a[10005], t[10005];

void QuickSort(int l, int r) {
	if (l >= r - 1) return ;
	
	int flag = a[rand() % (r - l) + l];
	int p = l, q = r;
	
	for (int i = l; i < r; i++) {
		if (a[i] < flag) t[p++] = a[i];
		else if (a[i] > flag) t[--q] = a[i];
	}
	
	for (int i = p; i < q; i++) // 复制剩下等于 flag 的数 
		t[i] = flag;
		
	for (int i = l; i < r; i++)
		a[i] = t[i];
		
	QuickSort(l, p);
	QuickSort(q, r);
}

标签:10005,code,int,void,pos,++,算法,排序
From: https://www.cnblogs.com/Gery-blog/p/16952026.html

相关文章

  • dataframe 多字段排序
    需求:importpandasaspddf=pd.DataFrame({'gene':['BC061237','Gm19965','Afdvwef','Vafsx','4930599A14Rik','am45766'],'mid':[2,......
  • JavaScript习题之算法设计题
    //1.九九乘法表for(vari=1;i<10;i++){document.write("<span>");for(varj=1;j<=i;j++){if(j%2==0){......
  • 【A*路径搜索算法】基于A星的最优避障路径搜索算法的MATLAB仿真+GUI界面
    1.软件版本MATLAB2021a2.基本原理A算法是启发式算法重要的一种,主要是用于在两点之间选择一个最优路径,而A的实现也是通过一个估值函数F=G+HG表示该点到起始点位所需要......
  • 选择排序
    选择排序选择排序是一种简单直观的排序算法,它的工作原理是每一次从待排序的数据元素中选出最小(最大)的一个元素,存放在序列的起始位置,然后,再从剩余未排序元素中继续寻找最小......
  • 美颜SDK滤镜功能有哪些常用的滤镜算法
    “美颜滤镜”,可以说是美颜SDK中大家最常用到的一个功能,几乎所有的主播和个人用户都曾经使用过此功能。但是,如果要追溯滤镜的发展史,那得把目光转向至很久之前。最开始的时候,......
  • 4、excel快速排序从1开始
    在分世界杯的文件时,要求把每一行从1开始排列,自己的做法就是先输入1和2,然后拖黑1和2,接着鼠标一直往下拖,这样就了。公式的方法:输入公式=Row()-1,如何在这个单元格的右下角双......
  • 回溯算法_N皇后
    Sub回溯算法_N皇后()n=8ReDimar(n)cnt=nqueen(n,0,ar,0)Debug.Print(cnt)EndSubPublicFunctionnqueen(n,row,res,count)If......
  • 排序实现
    十大经典排序算法 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需......
  • 拓扑排序 专题
    拓扑排序(\(Topological\)\(sorting\))拓扑排序指的是有向无环图(\(DAG\));学过计算机网络的知道计算机网络中有一个拓扑结构;下面就是一个拓扑结构;那拓扑序就是,图中任意一对顶点......
  • 验证darknet中前处理做图像缩放(双线性内插值法)scale的算法效果
    ​​DARKNET中使用的缩放算法是双线性内插值法,这里就实际验证一把DARKNET中scale的工作原理与效果:首先这是一张原图,画面中的是南京明城墙玄武门,玄武湖的正门。18年国庆带娃......