HappyLifeLife.com
HappyLifeLife.com
HappyLifeLife.com 登录 HappyLifeLife.com 注册 HappyLifeLife.com
爱新闻 爱生活
爱分享 爱学习
爱读书 爱探索
爱音乐 爱宇宙
爱电影 爱地球
爱阅读 爱世界
爱运动 爱科技
爱学习

<< < - > >>
算法
常用算法
www.HappyLiveLife.com 收藏 www.happylivelife.com
HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com
编辑
平方
static float CarmackSqrt (float x)
{
float xhalf = 0.5f * x;
int i = *(int*)&x; // get bits for floating VALUE
i = 0x5f3759df - (i>>1); // gives initial guess y0
x = *(float*)&i; // convert bits BACK to float
x = x*(1.5f - xhalf*x*x); // Newton step, repeating increases accuracy
x = x*(1.5f - xhalf*x*x); // Newton step, repeating increases accuracy
x = x*(1.5f - xhalf*x*x); // Newton step, repeating increases accuracy
return (1 / x);
}
二分查找
int binSearch(const int *Array,int start,int end,int key)
{
int left,right;
int mid;
left=start;
right=end;
while(left<=right)
{
mid=(left+right)/2;
if(key==Array[mid]) return mid;
else if(key<Array[mid]) right=mid-1;
else if(key>Array[mid]) left=mid+1;
}
return -1;
}
基数排序
LSD的基数排序适用于位数小的数列,如果位数多的话,使用MSD的效率会比较好。MSD的方式与LSD相反,是由高位数为基底开始进行分配,但在分配之后并不马上合并回一个数组中,而是在每个“桶子”中建立“子桶”,将每个桶子中的数值按照下一数位的值分配到“子桶”中。在进行完最低位数的分配后再合并回单一的数组中。
int maxbit(int data[], int n) //辅助函数,求数据的最大位数
{
int d = 1; //保存最大的位数
int p = 10;
for(int i = 0; i < n; ++i)
{
while(data[i] >= p)
{
p *= 10;
++d;
}
}
return d;
}
void radixsort(int data[], int n) //基数排序
{
int d = maxbit(data, n);
int *tmp = newint[n];
int *count = newint[10]; //计数器
int i, j, k;
int radix = 1;
for(i = 1; i <= d; i++) //进行d次排序
{
for(j = 0; j < 10; j++)
count[j] = 0; //每次分配前清空计数器
for(j = 0; j < n; j++)
{
k = (data[j] / radix) % 10; //统计每个桶中的记录数
count[k]++;
}
for(j = 1; j < 10; j++)
count[j] = count[j - 1] + count[j]; //将tmp中的位置依次分配给每个桶
for(j = n - 1; j >= 0; j--) //将所有桶中记录依次收集到tmp中
{
k = (data[j] / radix) % 10;
tmp[count[k] - 1] = data[j];
count[k]--;
}
for(j = 0; j < n; j++) //将临时数组的内容复制到data中
data[j] = tmp[j];
radix = radix * 10;
}
delete[]tmp;
delete[]count;
}
归并排序
#include <stdlib.h>
#include <stdio.h>
void Merge(int sourceArr[],int tempArr[], int startIndex, int midIndex, int endIndex)
{
int i = startIndex, j=midIndex+1, k = startIndex;
while(i!=midIndex+1 && j!=endIndex+1)
{
if(sourceArr[i] > sourceArr[j])
tempArr[k++] = sourceArr[j++];
else
tempArr[k++] = sourceArr[i++];
}
while(i != midIndex+1)
tempArr[k++] = sourceArr[i++];
while(j != endIndex+1)
tempArr[k++] = sourceArr[j++];
for(i=startIndex; i<=endIndex; i++)
sourceArr[i] = tempArr[i];
}
void MergeSort(int sourceArr[], int tempArr[], int startIndex, int endIndex)
{
int midIndex;
if(startIndex < endIndex)
{
midIndex = (startIndex + endIndex) / 2;
MergeSort(sourceArr, tempArr, startIndex, midIndex);
MergeSort(sourceArr, tempArr, midIndex+1, endIndex);
Merge(sourceArr, tempArr, startIndex, midIndex, endIndex);
}
}
int main(int argc, char * argv[])
{
int a[8] = {50, 10, 20, 30, 70, 40, 80, 60};
int i, b[8];
MergeSort(a, b, 0, 7);
for(i=0; i<8; i++)
printf("%d ", a[i]);
printf("\n");
return 0;
}
#include<stdio.h>
#include<math.h>
#define MAXNUM 10
void main()
{
void shellSort(int array[],int n,int t);//t为排序趟数
int array[MAXNUM],i;
for(i=0;i<MAXNUM;i++)
scanf("%d",&array[i]);
shellSort(array,MAXNUM,int(log(MAXNUM+1)/log(2)));//排序趟数应为log2(n+1)的整数部分
for(i=0;i<MAXNUM;i++)
printf("%d ",array[i]);
printf("\n");
}
希尔排序
void shellInsert(int array[],int n,int dk)
{
int i,j,temp;
for(i=dk;i<n;i++)//分别向每组的有序区域插入
{
temp=array[i];
for(j=i-dk;(j>=i%dk)&&array[j]>temp;j-=dk)//比较与记录后移同时进行
array[j+dk]=array[j];
if(j!=i-dk)
array[j+dk]=temp;//插入
}
}
int dkHibbard(int t,int k)
{
return int(pow(2,t-k+1)-1);
}
void shellSort(int array[],int n,int t)
{
void shellInsert(int array[],int n,int dk);
int i;
for(i=1;i<=t;i++)
shellInsert(array,n,dkHibbard(t,i));
}

选择排序

选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录,顺序存放在已排序的记录序列的后面,直到全部排完。选择排序中主要使用直接选择排序和堆排序。
1. 直接选择排序(不稳定)
直接选择排序的过程是:首先在所有记录中选出序码最小的记录,把它与第1个记录交换,然后在其余的记录内选出排序码最小的记录,与第2个记录交换......依次类推,直到所有记录排完为止。
无论文件初始状态如何,在第i趟排序中选出最小关键字的记录,需要做n-i次比较,因此,总的比较次数为n(n-1)/2=O(n^2)。当初始文件为正序时,移动次数为0;文件初态为反序时,每趟排序均要执行交换操作,总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O(n^2)。直接选择排序是不稳定的。
void Dir_Choose(int A[],int n) //直接选择排序
{
int k,t;
for(int i=0;i<n-1;i++)
{
k=i;
for(int j=i+1;j<n;j++)
{
if(A[j]<A[k]) k=j;
}
if(k!=i)
{
t=A[i];
A[i]=A[k];
A[k]=t;
}
}
}
2. 堆排序(不稳定)
堆排序是一种树形选择排序,是对直接选择排序的有效改进。n个关键字序列
K1,K2,...,Kn称为堆,当且仅当该序列满足(Ki<=K2i且Ki<=K2i+1)或(Ki>=K2i且Ki>=K2i+1),(1<=i& lt;=n/2)。根结点(堆顶)的关键字是堆里所有结点关键字中最小者,称为小根堆;根结点的关键字是堆里所有结点关键字中最大者,称为大根堆。
若将此序列所存储的向量R[1..n]看作是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。
堆排序的关键步骤有两个:一是如何建立初始堆;二是当堆的根结点与堆的最后一个结点交换后,如何对少了一个结点后的结点序列做调整,使之重新成为堆。堆排序的最坏时间复杂度为O(nlog2n),堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较 次数较多,所以堆排序不适宜于记录较少的文件。堆排序是就地排序,辅助空间为O(1),它是不稳定的排序方法。

交换排序

交换排序的基本思想是:两两比较待排序记录的排序码,并交换不满足顺序要求的那写偶对,直到满足条件为止。交换排序的主要方法有冒泡排序和快速排序.
1. 冒泡排序(稳定的)
冒泡排序将被排序的记录数组R[1..n]垂直排列,每个记录R[i]看作是重量为ki的气泡。根据轻气泡不能在重气泡之下的原则,从下往上扫描数组R;凡扫描到违反本原则的轻气泡,就使其向上"漂浮"。如此反复进行,直到最后任何两个气泡都是轻者在上,重者在下为止。
冒泡排序的具体过程如下:
第一步,先比较k1和k2,若k1>k2,则交换k1和k2所在的记录,否则不交换。继续对k2和k3重复上述过程,直到处理完kn-1和kn。这时最大的排序码记录转到了最后位置,称第1次起泡,共执行n-1次比较。
与第一步类似,从k1和k2开始比较,到kn-2和kn-1为止,共执行n-2次比较。
依次类推,共做n-1次起泡,完成整个排序过程。
若文件的初始状态是正序的,一趟扫描即可完成排序。所需关键字比较次数为n-1次,记录移动次数为0。因此,冒泡排序最好的时间复杂度为O(n)。
若初始文件是反序的,需要进行n-1趟排序。每趟排序要进行n-i次关键字的比较(1<=i<=n-1),且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下,比较次数达到最大值n(n-1)/2=O(n^2),移动次数也达到最大值3n(n-1)/2=O(n^2)。因此,冒泡排序的最坏时间复杂度为O(n^2)。
虽然冒泡排序不一定要进行n-1趟,但由于它的记录移动次数较多,故平均性能比直接插入排序要差得多。冒泡排序是就地排序,且它是稳定的。
void QP(int A[],int n) //优化的冒泡排序
{
int count=0,t,flag;
for(int i=0;i<n-1;i++)
{
flag=0;
for(int j=0;j<n-i;j++)
{
if(A[j+1]<A[j])
{
t=A[j];
A[j]=A[j+1];
A[j+1]=t;
flag=1;
count+=3;
}
}
if(flag==0) break;
}
}
2. 快速排序:(不稳定的)
快速排序采用了一种分治的策略,通常称其为分治法,其基本思想是:将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。
快速排序的具体过程如下:
第一步,在待排序的n个记录中任取一个记录,以该记录的排序码为准,将所有记录分成两组,第1组各记录的排序码都小于等于该排序码,第2组各记录的排序码都大于该排序码,并把该记录排在这两组中间。
第二步,采用同样的方法,对左边的组和右边的组进行排序,直到所有记录都排到相应的位置为止。
代码如下:
void Quick_Sort(int A[],int low,int high) //low和high是数组的下标
{
if(low<high)
{
int temp,t=A[low];
int l=low,h=high;
while(l<h)
{
while(A[l]<t) l++;
while(A[h]>=t) h--;
if(h>l)
{
temp=A[l];
A[l]=A[h];
A[h]=temp;
}
}
Quick_Sort(A,low,l-1);
Quick_Sort(A,l+1,high);
}
}

插入排序

插入排序的基本思想是每步将一个待排序的记录按其排序码值的大小,插到前面已经排好的文件中的适当位置,直到全部插入完为止。插入排序方法主要有直接插入排序和希尔排序。
1 .直接插入排序(稳定)
接插入排序的过程为:在插入第i个记录时,R1,R2,..Ri-1已经排好序,将第i个记录的排序码Ki依次和R1,R2,..,Ri-1的排序码逐个进行比较,找到适当的位置。使用直接插入排序,对于具有n个记录的文件,要进行n-1趟排序。
代码如下:
void Dir_Insert(int A[],int N) //直接插入排序
{
int j,t;
for(int i=1;i<N;i++)
{
t=A[i];
j=i-1;
while(A[j]>t)
{
A[j+1]=A[j];
j--;
}
A[j+1]=t;
}
}
2. 希尔排序(不稳定)
希尔(Shell)排序的基本思想是:先取一个小于n的整数d1作为第一个增量把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序;然后,取得第二个增量d2<d1重复上述的分组和排序,直至所取的增量 di=1,即所有记录放在同一组中进行直接插入排序为止。该方法实质上是一种分组插入方法。
一般取d1=n/2,di+1=di/2。如果结果为偶数,则加1,保证di为奇数。
希尔排序是不稳定的,希尔排序的执行时间依赖于增量序列,其平均时间复杂度为O(n^1.3).
代码如下:
void Shell(int A[],int n) //Shell排序
{
int i,j,k,t;
(n/2)%2 == 0 ? k = n/2+1 : k = n/2; //保证增量为奇数
while(k > 0)
{
for(j=k;j<n; j++)
{
t = A[j];
i = j - k;
while(i>=0 && A[i]>t)
{
A[i+k]=A[i];
i=i-k;
}
A[i+k]=t;
}
if(k == 1) break;
(k/2)%2 ==0 ? k=k/2+1 : k=k/2;
}
}

归并排序

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时,把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成,将它们依次两两归并得到长度为2的若干有序子表,再对它们两两合并。直到得到长度为n的有序表,排序结束。
归并排序是一种稳定的排序,可用顺序存储结构,也易于在链表上实现,对长度为n的文件,需进行log2n趟二路归并,每趟归并的时间为O(n),故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。归并排序需要一个辅助向量来暂存两个有序子文件归并的结果,故其辅助空间复杂度为 O(n),显然它不是就地排序。
代码

基数排序

设单关键字的每个分量的取值范围均是C0<=Kj<=Crd-1(0<=j<=rd),可能的取值个数rd称为基数.基数的选择和关键字的分解因关键字的类型而异.
  (1).若关键字是十进制整数,则按个、十等位进行分解,基数rd=10,C0=0,C9=9,d为最长整数的位数.
  (2).若关键字是小写的英文字符串,则rd=26,C0='a',C25='z',d为最长字符串的长度.
  基数排序的基本思想是:从低位到高位依次对待排序的关键码进行分配和收集,经过d趟分配和收集,就可以得到一个有序序列.
按平均时间将排序分为四类
(1) 平方阶(O(n2))排序
 一般称为简单排序,例如直接插入、直接选择和冒泡排序;
(2) 线性对数阶(O(nlgn))排序
 如快速、堆和归并排序;
(3) O(n1+£)阶排序
 £是介于0和1之间的常数,即0<£<1,如希尔排序;
(4) 线性阶(O(n))排序
 如基数排序。
各种排序方法比较
简单排序中直接插入最好,快速排序最快,当文件为正序时,直接插入和冒泡均最佳。
影响排序效果的因素
 因为不同的排序方法适应不同的应用环境和要求,所以选择合适的排序方法应综合考虑下列因素:
  ①待排序的记录数目n;
  ②记录的大小(规模);
  ③关键字的结构及其初始状态;
  ④对稳定性的要求;
  ⑤语言工具的条件;
  ⑥存储结构;
  ⑦时间和辅助空间复杂度等。
不同条件下,排序方法的选择
(1) 若n较小(如n≤50),可采用直接插入或直接选择排序。
 当记录规模较小时,直接插入排序较好;否则因为直接选择移动的记录数少于直接插人,应选直接选择排序为宜。
(2) 若文件初始状态基本有序(指正序),则应选用直接插人、冒泡或随机的快速排序为宜;
(3) 若n较大,则应采用时间复杂度为O(nlgn)的排序方法:快速排序、堆排序或
归并排序。
快速排序是目前基于比较的内部排序中被认为是最好的方法,当待排序的关键字是随机分布时,快速排序的平均时间最短;
堆排序所需的辅助空间少于快速排序,并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
若要求排序稳定,则可选用归并排序。但从单个记录起进行两两归并的 排序算法并不值得提倡,通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件,然后再两两归并之。因为直接插入排序是稳定的,所以改进后的归并排序仍是稳定的。

JAVA中运用数组的四种排序方法

JAVA中在运用数组进行排序功能时,一般有四种方法:快速排序法、冒泡法、选择排序法、插入排序法。
快速排序法主要是运用了Arrays中的一个方法Arrays.sort()实现。
冒泡法是运用遍历数组进行比较,通过不断的比较将最小值或者最大值一个一个的遍历出来。
选择排序法是将数组的第一个数据作为最大或者最小的值,然后通过比较循环,输出有序的数组。
插入排序是选择一个数组中的数据,通过不断的插入比较最后进行排序。下面我就将他们的实现方法一一详解供大家参考。

<1>利用Arrays带有的排序方法快速排序

import java.util.Arrays;
public class Test2{
public static void main(String[] args){
int[] a={5,4,2,4,9,1};
Arrays.sort(a); //进行排序
for(int i: a){
System.out.print(i);
}
}
}

<2>冒泡排序算法

public static int[] bubbleSort(int[] args){//冒泡排序算法
for(int i=0;i<args.length-1;i++){
for(int j=i+1;j<args.length;j++){
if (args[i]>args[j]){
int temp=args[i];
args[i]=args[j];
args[j]=temp;
}
}
}
return args;
}

<3>选择排序算法

public static int[] selectSort(int[] args){//选择排序算法
for (int i=0;i<args.length-1 ;i++ ){
int min=i;
for (int j=i+1;j<args.length ;j++ ){
if (args[min]>args[j]){
min=j;
}
}
if (min!=i){
int temp=args[i];
args[i]=args[min];
args[min]=temp;
}
}
return args;
}

<4>插入排序算法

public static int[] insertSort(int[] args){//插入排序算法
for(int i=1;i<args.length;i++){
for(int j=i;j>0;j--){
if (args[j]<args[j-1]){
int temp=args[j-1];
args[j-1]=args[j];
args[j]=temp;
}else break;
}
}
return args;
}
以上就是java中的四种排序方法。不同的方法效率不一样,下面是不同的算法的比较和数据交换时的大O表示。
冒泡排序:比较O(N2) 数据交换O(N2)
选择排序:比较O(N2) 数据交换O(N)
插入排序:比较O(N2) 复制数据O(N)
在实际应用中,要尽量选择效率高的算法。
 1、有1亿个浮点数,请找出其中对大的10000个。提示:假设每个浮点数占4个字节,1亿个浮点数就要站到相当大的空间,因此不能一次将全部读入内存进行排序。 
  方法1: 读出100w个数据, 找出最大的1w个, 如果这100w数据选择够理想, 那么最小的这1w个数据里面最小的为基准, 可以过滤掉1亿数据里面99%的数据, 最后就再一次在剩下的100w(1%)里面找出最大的1w个咯~~
  方法2: 分块, 比如100w一个块, 找出最大1w个, 一次下来就剩下100w数据需要找出1w个了.
  对于上面提到的找出100w个数据里面最大的1w个, 说起来比较罗嗦, 还是说说找到第1w个大的数字的方法:
  用快速排序的方法, 分2堆, 如果大的那堆个数N大于1w个, 继续对大堆快速排序一次分成2堆, 如果大堆个数N小于1w, 就在小的那堆里面快速排序一次, 找第10000-N大的数字; 递归以上过程, 就可以找到第1w大的数. 据说也是STL的search_n()的方法;
  参考上面的找出第1w大数字, 找出前1w大数字了.
2、有一篇英文文章(也就是说每个单词之间由空格分隔),请找出“csdn”着个单词出现的次数,要求效率最高,并写出算法的时间级。
  假设不区分大小写,由于英文字母有26个,因此,可以将单词映射为数字。csdn被映射成:
  ( 'c '- 'a ')*32*32*32+( 's '- 'a ')*32*32+( 'd '- 'a ')*32+( 'n '- 'a ')
  即:( 'c '- 'a ')*(1 < <15)+( 's '- 'a ')*(1 < <10)+( 'd '- 'a ')*(1 < <5)+( 'n '- 'a ')
* 声明:本文由其作者或媒体撰写,观点仅代表其本身,不代表本站立场。
编辑
HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com HappyLifeLife.com
 
<< < - > >>
[GIT][*] [HIS][*] [JS][*] [Android][*] [DB][*] [Web][*] [JAVA][*] [C][*] [0][*] [TL][*] [O][*] [3D][*] [PAS][*] [IOS][*] [算法][*] [地球][*] [学习方法][*] [探索][*] [宇宙][*] [Linux][*] [阅读秘诀][*] [考试技巧][*] [...]
天天快乐生活[HappyLifeLife.com]
欢迎来访 快乐空间 热点新闻 我的分享 读书频道 七彩生活 精彩世界 快乐搜索 
ICP备15040518 | ©1999-2018 HappyLiveLife.com 版权所有 | 服务 | 爱新闻 | 爱分享 | 在线搜索 | 招贤纳士
欢迎来访 快乐空间 热点新闻 我的分享 读书频道 七彩生活 精彩世界 快乐搜索 
ICP备15040518 | ©1999-2018 HappyLiveLife.com 版权所有 | 服务 | 爱新闻 | 爱分享 | 在线搜索 | 招贤纳士