1.冒泡排序

冒泡排序就是通过对比前一个和后一个数的大小,按照规则进行顺序的调换。每一轮对比之后最大或者最小值都会浮到最上面或者沉到最低下。

如:对这一数组进行冒泡排序:int a[5]{34,12,56,4,7}; 假设为从小到大排序

一共需要比较length-1轮:

第一轮: a.34和12比较,12比34小,那么调换位置,此时为:12,34,56,4,7,然后在对该序列进行排序

     b.然后就是34和56进行对比,34比56小,不用调换顺序,此时依旧为:12,34,56,4,7,然后在对该序列进行排序

     c.然后再就是56和4鸡西宁对比,4比56小,所以将56和4调换顺序,此时序列就是:12,34,4,56,7

     d.再然后就对比56和7,7比56小,所以将二者位置进行调换,此时完成第一轮调换,序列为:12,34,4,7,56

    我们可以看到第一轮排序之后,已经将序列中的最大值沉到最底部了。

第二轮:此时的排序此时交第一轮要减1,

     a.先是12和34对比,前者比后者小,所以不用调换位置,序列时:12,34,4,7,56

     b.然后比较34和4的大小,后者比前者小,所以调换位置,此时序列为:12,4,34,7,56

     c.再然后比较34和7的大小,后者比前者小,所以调换位置,此时序列为:12,4,7,34,56

     d.此时就不用在往下比较了,因为比较次数已经减1了,也是因为第一轮中已经将最大的数选出来了。

然后就是第三轮和第四轮的比较,方法类似。

最终结果就是4,7,12,34,56

我们可以看到程序截图如下图所示:
冒泡排序过程

2.选择排序

选择排序的实现要比冒泡排序简单一些,但是在代码上相对会有些绕。原理就是先假设待排序的序列中的第一个数为最小值或者最大值,这里还是用从小到大的顺序进行排序。首先假设第一个数为最小值(假设该值的索引下标时i),然后从该值的下一个数也就是索引为i+1的数开始进行比较,如果i+1的值要比假设的最小值小,那么就将二者的值进行交换,每一轮将最小值选择出来,并将其与假设的最小值进行调换就行,不需要想冒泡排序那样整个需略都要跟着一起移动。此时还需要一个缓冲变量来存放最小值的索引值。

详细讲解:

在时间复杂度上,这两种排序方法都是一样,O(N^2),也是需要循环执行length-1轮。还是假设对数组a进行排序。

首先定义数组:int a[5]{34,12,56,4,7};

第一轮:先假设序列中的第一个数是最小值,记录下它的索引值,定一个新的变量用来存放该索引值,minIndex=0,下表为0也就是第一个数。然后在进行循环。

     a.内循环中的第一轮是34和12进行比较,后者比前者小,所以将minIndex的索引值进行更改,此时minIndex=1,

     b.内循环中的第二轮,是利用minIndex 中的数和下一个待比较的数进行比较,应该是12和56比较,后者比前者小,所以不用修改minIndex的值

     c.内循环中的第三轮,还是利用索引为1的数值和下一个待比较的数进行比较,应该是12和4进行比较,后者较之前者较小,所以记录下当前数的索引值并赋值给minIndex,此时minIndex=3

     d.内循环中的第四轮,利用minIndex索引值的数值和下一个待比较的数进行比较,应该是4和7进行比较,后者比前者大,所以不用修改minIndex的值

    然后将序列中的第i个数和序列中索引值为minIndex的数进行调换,第一轮已将最小值选择出来了。此时序列为:4,12,56,34,7

    第一轮外循环之后,minIndex=3,下一轮外循环会将这个值直接覆盖

第二轮:此时的minIndex=1,假设的最小值是12

     此时定义上一轮外循环的下一个数为最小值,也即是索引值为1的值,那么本轮循环将从索引值为2的数开始比较,

     a.内循环中的第一轮,比较12和56,后者比前者大,所以不用修改minIndex的值,

     b.内循环中的第二轮,此时比较12和34的大小,还是依旧不用修改索引值

     c.内循环中的第三轮,此时比较12和7的大小,后者比前者小,索引记录下当前数的索引值并赋值给minIndex记录下来

    内循环结束,判断minIndex的值是否被改变,如果被改变了,那么就将下标为i的数和下标为minIndex的数进行交换。此时序列为:4,7,56,34,12且minIndex=4

第三轮和第四轮外循环的规则类似。。

我们可以看程序运行的效果图如下:
选择排序过程

最后附上可供运行的c++代码:

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
#include <iostream>
#include <iomanip>

using namespace std;

int main()
{

// bubble sort
double a[5]={34,12,56,4,7};
int len = sizeof(a) / sizeof(double);

//output all numbers
cout << "before sorted by bubbleSort:" <<endl;
for (int i=0;i<len;i++)
{
cout << a[i]<<"\t";
}
cout << endl;

//start to sort the array
for (int i=0;i<len-1;i++)
{
for(int j=0;j<len -i -1;j++)
{
if(a[j]>a[j+1])
{
double t = 0;
t = a[j];
a[j] = a[j+1];
a[j+1] = t;
}
}
cout << "This is at NO." << i << "time: ";
for(int i=0;i<len;i++)
cout << a[i] << "\t";
cout << endl;

}

//output after sorted
cout << "after sorted by bubbleSort:"<<endl;
for (int i=0;i<len;i++)
{
cout << a[i]<<"\t";
}
cout << endl;


//selectsort
double b[5]={34,12,56,4,7};

cout << "before sorted by selectSort:" << endl;
for (int i=0;i<len;i++)
{
cout << b[i]<< "\t";
}
cout << endl;
//start to selectSort
for(int i=0;i<len-1;i++)
{
int minIndex = i;//pretend the first number of the array be the min number.and record the index
cout << "ending->minIndex=" << minIndex << endl;
for (int j=i+1;j<len;j++)
{
if(b[minIndex]>b[j])
{
minIndex = j;
}
}
if(minIndex != i)
{
double t = 0;
t = b[i];
b[i] = b[minIndex];
b[minIndex] = t;

}
//print the detail
cout << "This is at NO." << i << "time: ";
for(int i=0;i<len;i++)
cout << setw(4)<<b[i] ;
cout << " "<< "ending->minIndex=" << minIndex << endl;

}
cout << "after sorted by selectSort:" << endl;
for (int i=0;i<len;i++)
{
cout << b[i]<<"\t";
}
cout << endl;

return 0;
}

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
public class Bubble {
public static void main(String[] args) {
int[] b = {3, 1, 4, 2,89,76,35};
for (int i = 0; i < b.length; i++) {
System.out.print(b[i]);
}
System.out.println();
int[] c = bubble(b);
for (int i = 0; i < c.length; i++) {
System.out.print(c[i] + "\t");
}
System.out.println();
int[] d = select(b);
for (int i = 0; i < d.length; i++) {
System.out.print(d[i] + "\t");
}


}

public static int[] bubble(int[] a) {
for (int i = 0; i < a.length - 1; i++) {
for (int j = 0; j < a.length - 1 - i; j++) {
if (a[j+1] < a[j]) {
int temp = a[j+1];
a[j+1] = a[j];
a[j] = temp;
}
}
}
return a;
}

public static int[] select(int[] a){
int maxIndex = 0;
int i,j;
for (i = 0; i < a.length; i++) {
for (j=0; j< a.length -1 ;j++){
if (a[maxIndex] < a[j]){
maxIndex = j;
}
}
}
if(maxIndex != i){
return a;
}
return null;

}
}

写在最后

欢迎大家关注鄙人的公众号【麦田里的守望者zhg】,让我们一起成长,谢谢。
微信公众号