算法之降序排序

First

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static void (String[] args)
{
int a[] = {1,5,10,20,32,22,2,4,3,25};
int tmp,i,j;
for( i = 0; i<a.length-1; i++)
{
for( j =0; j<a.length-i-1; j++)
{
if(a[j]<a[j+1])
{
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
for(i=0; i<a.length-1;i++)
{
System.out.println(a[i]);
}
}

算法分析:

是让两两相邻的两个数做比较
大的值放前面,小的值放后面,最小的数会移到最后面
第一次需要相邻比较9次
第二次需要相邻比较8次
···
第九次只需要相邻比较1次

Second

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void (String[] args)
{
int a[] = {1,5,10,20,32,22,2,4,3,25};
int b[] = new int[10];
int tmp,i,j,max;
b[0] = a[0];
for(i = 1;i<a.length;i++)
{
max = a[i];
for(j = i-1; j>=0; j--)
{
if(max > b[j])
{
b[j+1] = b[j];
}
else
break;
}
b[j+1] = max;
}
for(i=0;i<b.length;i++)
{
System.out.println(b[i]);
}

}

算法分析

需要增加一个数组

  • 1.现将第一个元素存在b[]数组内
  • 2.外部循环也需要9次,依次取第i个元素,假设它成为最大元素
  • 3.相邻两个元素比较,大的放前面,小的放后面,第一次只有两个相邻元素,只需要比较一次
  • 4.第二次比较是与相邻的元素比较(但这个数据中相邻的元素一定比较小),所以可以节省比较次数。
  • 5.减少算法复杂度