数据排序

选择排序

首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。复杂度是O(n^2)

int selectsort(int arr[])
{
	/**
		Encoded as UTF-8
		Date:2014/12/23 17:36
	**/
	for (int i = n; i > 0; i--)
	{
		int j,max=0,addr;
		for (j = 0; j <= i; j++)
		{
			if (arr[j]>max)
			{
				max=arr[j];
				addr=j;
			}
		}
		arr[addr]=arr[i];
		arr[i]=max;
	}
}

冒泡排序

通过不断比对arr[i]与arr[i+1]实现排序,复杂度为O(n^2)

int bubblesort(int arr[])
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n-1; j++)
		{
			if (arr[i]>arr[i+1])
			{
				int temp=arr[i];
				arr[i]=arr[i+1];
				arr[i+1]=temp;
			}
		}
	}
}

插入排序 貌似爆数组了 有待重写

int insertsort(int arr[])
{
	for (int i = 1; i <= n; i++)
	{
		x=arr[i];
		j=i-1;
		while (x < arr[j])
		{
			arr[j+1]=arr[j];
			j--;
		}
		arr[j+1]=x;
	}
}

计数排序

根据大于元素arr[i]的元素的个数进行排序

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<sstream>
using namespace std;
int main()
{
	/**
		Encoded as UTF-8
		Date:2014/12/24 13:20
	**/
	int n,m;
	scanf("%d%d", &n, &m);
	int arr[m];
	memset(arr,0,sizeof(arr));
	for (int i = 0; i < n; i++)
	{
		int t;
		scanf("%d", &t);
		arr[t]++;
	}
	for (int i = 0; i < m; i++)
	{
		if (arr[i]>0)
		{
			for (int p = 0; p < arr[i]; p++)
			{
				printf("%d ", i);
			}
		}
	}
	return 0;
}

珠排序

这种排序在物理中进行效率更高…复杂度貌似也是O(n^2)

long m;//max
int n;//number
int pearlsort(int arr[])
{
	int t[m];
	memset(t,0,sizeof(t));
	for (int i = 0; i < n; i++)
	{
		if (arr[i]!=0)
		{
			for (int j = 0; j < arr[i]; j++)
			{
				t[j]++;
			}
		}
	}
	int p=0;
	for (int i = 0; i < m; i++)
	{
		if (t[i]!=0)
		{
			arr[p]=t[i];
			p++;
		}
	}

}

梳子排序

像把梳子一样,以k为跨度比对数据,每一轮搜索后k–

int combsort(int arr[])
{
	int t;
	for (int i = n-1; i > 0; i--)
	{
		for (int j = 0; j <= n-1-i; j++)
		{
			if (arr[j]>arr[j+i])
			{
				t=arr[j];
				arr[j]=arr[j+i];
				arr[j+i]=t;
			}
		}
	}
}

CC BY-SA 4.0 数据排序 by 小小泥娃 is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

1 Reply to “数据排序”

发表评论

This site uses Akismet to reduce spam. Learn how your comment data is processed.