22十一
归类于程序人生
参与评论
突然有欲望打代码。。。于是结合了以前的一些代码，把自己会写的排序整合了一下，写了个排序类
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
public class Sortman {
/**
* 冒泡排序
* @param Comparable数组引用
* @param start 其实位置
* @param end 终止位置
*/
public void bubbleSrot(Comparable[] a,int start,int end){
for(int i=end;i>start;i--){
for(int j=start+1;j<=i;j++){
if(a[j-1].compareTo(a[j])>0){
Comparable temp=a[j-1];
a[j-1]=a[j];
a[j]=temp;
}
}
}
}
/**
* 选择排序
* @param Comparable数组引用
* @param start 其实位置
* @param end 终止位置
*/
public void selectionSort(Comparable[] a,int start,int end){
for(int i=start;i<end;i++){
int p=i;
for(int j=i+1;j<=end;j++){
if(a[j].compareTo(a[p])<0)
p=j;
}
if(p!=i){
Comparable temp=a[i];
a[i]=a[p];
a[p]=temp;
}
}
}
/**
* 插入排序
* @param Comparable数组引用
* @param start 其实位置
* @param end 终止位置
*/
public void insertionSort(Comparable[] a,int start,int end){
for(int i=start+1;i<=end;i++){
Comparable val=a[i];
int j=i;
while(j>start&&val.compareTo(a[j-1])<0){
a[j]=a[j-1];
j--;
}
a[j]=val;
}
}
private int split(int low, int high,Comparable[] a)
{
Comparable t;
t=a[low];
while(low<high)
{
while(a[high].compareTo(t)>0&&low<high)
{
high--;
}
if(low==high)
break;
else
{
a[low]=a[high];
low++;
}
while(a[low].compareTo(t)<0&&low<high)
{
low++;
}
if(low==high)
break;
else
{
a[high]=a[low];
high--;
}
}
a[low]=t;
return low;
}
/**
* 快速排序
* @param Comparable数组引用
* @param start 其实位置
* @param end 终止位置
*/
public void quickSort(Comparable[] a,int start,int end)
{
int p;
if(start<end)
{
p=split(start,end,a);
quickSort(a,start,p-1);
quickSort(a,p+1,end);
}
}
private void add(Comparable[] a,int l1,int h1,int l2,int h2)
{
Comparable[] t;
int i,j,k;
i=l1;
j=l2;
k=0;
t=new Comparable[h2-l1+1];
while(i<=h1&&j<=h2)
{
if(a[i].compareTo(a[j])<0)
{
t[k++]=a[i++];
}else
{
t[k++]=a[j++];
}
}
while(i<=h1)
{
t[k++]=a[i++];
}
while(j<=h2)
t[k++]=a[j++];
for(i=l1,j=0;i<=h2;i++,j++)
{
a[i]=t[j];
}
}
/**
* 归并排序
* @param Comparable数组引用
* @param start 其实位置
* @param end 终止位置
*/
public void mergeSort(Comparable[] a,int low,int high)
{
int mid=(low+high)/2;
if(low<high)
{
mergeSort(a,low,mid);
mergeSort(a,mid+1,high);
add(a,low,mid,mid+1,high);
}
}
} |
167 views class, java, sort, 排序
17十
归类于程序人生
参与评论
感觉还是很假的java版本的归并排序
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| import java.util.*;
/**
*
* @author yanglingfeng
*/
public class Main {
/**
* @param args the command line arguments
*/
private static void add(int[] a,int l1,int h1,int l2,int h2)
{
int[] t;
int i,j,k;
i=l1;
j=l2;
k=0;
t=new int[h2-l1+1];
while(i<=h1&&j<=h2)
{
if(a[i]<a[j])
{
t[k++]=a[i++];
}else
{
t[k++]=a[j++];
}
}
while(i<=h1)
{
t[k++]=a[i++];
}
while(j<=h2)
t[k++]=a[j++];
for(i=l1,j=0;i<=h2;i++,j++)
{
a[i]=t[j];
}
return ;
}
private static void ms(int[] a,int low,int high)
{
int mid=(low+high)/2;
if(low<high)
{
ms(a,low,mid);
ms(a,mid+1,high);
add(a,low,mid,mid+1,high);
}
return ;
}
public static void main(String[] args) {
// TODO code application logic here
int k;
Scanner read=new Scanner(System.in);
while(read.hasNextInt())
{
k=read.nextInt();
int[] w=new int[k];
for(int i=0;i<k;i++)
{
w[i]=read.nextInt();
}
ms(w,0,k-1);
for(int i=0;i<k;i++)
{
System.out.print(w[i]+"");
}
System.out.println();
}
}
} |
128 views java, sort, 归并排序, 排序, 编程
25八
归类于程序人生
参与评论
所谓的归并排序，就是递归“把数组从中间分开，分成两段，然后分别排序，最后合并”这个过程。
比较好理解，所以很快敲出了代码。
比快排好理解。。。个人感觉。。。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
| #include<stdio.h>
#include<stdlib.h>
typedef int mytype;
void add(mytype *a,int l1,int h1,int l2,int h2)
{
mytype *t;
int i,j,k;
i=l1;
j=l2;
k=0;
t=(mytype*)malloc((h2-l1+1)*sizeof(mytype));
//申请空间存放中间数据
while(i<=h1&&j<=h2)
{
if(a[i]<a[j])
{
t[k++]=a[i++];
}else
{
t[k++]=a[j++];//小的放进去。。。
}
}
while(i<=h1)
{
t[k++]=a[i++];
}
while(j<=h2)
t[k++]=a[j++];//多余的数
for(i=l1,j=0;i<=h2;i++,j++)
{
a[i]=t[j];//复制中间数据回去
}
free(t);
return ;
}
void MergeSort(mytype *a,int low,int high)
{
int mid=(low+high)/2;
if(low<high)
{
MergeSort(a,low,mid);//最难理解的部分了吧。。。
MergeSort(a,mid+1,high);//就是不断的递归
add(a,low,mid,mid+1,high);//然后从最底一层排序后回溯上来。。。
}
return ;
}
int main()
{
mytype s[100];
int i,j,k,n;
while(scanf("%d",&n)!=EOF)
{
for(i=0;i<n;i++)
{
scanf("%d",s+i);
}
MergeSort(s,0,n-1);
for(i=0;i<n;i++)
{
printf("%d ",s[i]);
}
puts("");
}
} |
145 views C#, code, MergeSort, sort, 归并排序, 排序, 算法, 递归
24八
归类于程序人生
参与评论
突然发现，自己系统的qsort调用的很溜，可是却连个qsort怎么实现的都不知道。。。实在惭愧。。。于是从新学习排序，然后用c语言写了个比较简陋的qsort
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
| #include<stdio.h>
struct man{
int len;
char name[100];
};
typedef struct man mtype;
mtype s[100];
int cmp(const void *a, const void *b)
{
return ((mtype*)a)->len-((mtype*)b)->len;
}
int split(int low, int high,mtype *a,int (*cmp)(const void *a,const void *b))
{
mtype t;
t=a[low];
while(low<high)
{
while(cmp(&a[high],&t)>0&&low<high)
high--;
if(low==high)
break;
else
{
a[low]=a[high];
low++;
} //将比t小的数都放到t的前面
while(cmp(&a[low],&t)<=0&&low<high)
low++;
if(low==high)
break;
else
{
a[high]=a[low];
high--; //比t大的放后面
}
}
a[low]=t;
return low;
}
void qsort(mtype *a,int low,int high,int (*cmp)(const void *a,const void *b))
{
int p;
if(low<high)
{
p=split(low,high,a,cmp);//取一个数进行分割
qsort(a,low,p-1,cmp);//前部分迭代
qsort(a,p+1,high,cmp);//后部分迭代
}
}
int main()
{
int a,b,i;
while(scanf("%d",&b)!=EOF)
{
for(i=0;i<b;i++)
{
scanf("%d %s",&s[i].len,s[i].name);
}
qsort(s,0,b-1,cmp);
for( i=0;i<b;i++)
{
printf("%s ",s[i].name);
}
printf("\n");
}
} |
这个qsort就是nlogn的复杂度，没有进行任何优化
每次选第一个数作为分割标准
但是已经够用了。。。
157 views C#, code, qsort, 排序, 程序人生, 编程
24八
归类于程序人生
参与评论
一个很简单的排序。。。大牛无视。。。
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Text;
using System.IO;
namespace qsort
{
class Program
{
static void Main(string[] args)
{
ArrayList a = new ArrayList();
int i;
int n;
string t=Console.ReadLine();
n = Convert.ToInt32(t);
for(i=0;i<n;i++)
{
string s = Console.ReadLine();
a.Add(s);
}
for(i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
string k, b, temp;
k = a[i].ToString();
b = a[j].ToString();
if(k.CompareTo(b)>0)
{
temp = a[i].ToString();
a[i] = a[j];
a[j] = temp;
}
}
}
Console.WriteLine("______");
for(i=0;i<n;i++)
{
Console.WriteLine(a[i]);
}
}
}
} |
179 views C#, code, sort, 排序, 编程
