冒泡排序及其优化 1.基本冒泡排序 2.优化1(对总趟数进行优化) 3.优化2(对每趟比较中的比较次数进行优化)
假设有n个数据需要由小到大排序，从最后一个数开始，进行相邻数的两两比较，若上面的数比下面的数大，则交换两个数的位置，则第一趟两两比较过后，n个数中最小的数到达最上面。重新从最后一个数开始，进行相邻数的两两比较，第二趟比较过后，次小的数也到了它应该到的最终位置。
一趟比较确定一个位置上的数，n个数需要n-1趟比较，因为最后一个数无需进行比较即可确定位置。第0趟比较，需要比较的最后一个数为num[0]，比较过后，位置0上的数据已确定，所以第1趟比较需要比较的最后一个数为num[1]，依次类推，第i趟比较需要比较的最后一个数为num[i]。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void BubbleSort_1(int num[], int n)
{ int i, j;
int temp;
for (i = 0; i < n - 1; i++)
{
for (j = n - 1; j > i; j--)
{
if (num[j - 1] > num[j])
{
temp = num[j - 1];
num[j - 1] = num[j];
num[j] = temp;
}
}
}
} |
2.优化1(对总趟数进行优化)
如果某趟比较过程中，没有数据进行交换，表明序列已有序，无需进行后续比较。因此可以对比较的趟数进行优化。
|
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
|
void BubbleSort_2(int num[], int n)
{ int i, j;
int temp;
int flag;
for (i = 0; i < n - 1; i++)
{
//第i趟比较时，先复位比较标志位。
flag = 0;
for (j = n - 1; j > i; j--)
{
if (num[j - 1] > num[j])
{
temp = num[j - 1];
num[j - 1] = num[j];
num[j] = temp;
//如果有比较过程，则置位标志位。
flag = 1;
}
}
//如果第i趟比较过程中没有交换，则序列已有序，结束循环。
if (flag == 0)
break;
}
} |
3.优化2(对每趟比较中的比较次数进行优化)
如果在第i趟比较过程中，最后一个进行交换的数为num[last]，表明num[0]~num[last]已为有序序列，因此在第i+1趟比较过程中，需要进行比较的最后一个数为num[last]。所以可以对每趟比较过程中比较的次数进行优化。
|
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
|
void BubbleSort_3(int num[], int n)
{ int i, j;
int temp;
int flag;
int head, head_t;
head_t = 0;
for (i = 0; i < n - 1; i++)
{
flag = 0;
//head指向第i趟比较过程中最后一个需要比较的元素，即第i-1趟比较过程中最后一个进行交换的元素。
head = head_t;
for (j = n - 1; j > head; j--)
{
if (num[j - 1] > num[j])
{
temp = num[j - 1];
num[j - 1] = num[j];
num[j] = temp;
head_t = j - 1;
flag = 1;
}
}
//退出该for循环时，head_t的值指向最后一个进行交换的元素。
if (flag == 0)
break;
}
} |
假设有n个数据需要由小到大排序，从最后一个数开始，进行相邻数的两两比较，若上面的数比下面的数大，则交换两个数的位置，则第一趟两两比较过后，n个数中最小的数到达最上面。重新从最后一个数开始，进行相邻数的两两比较，第二趟比较过后，次小的数也到了它应该到的最终位置。
一趟比较确定一个位置上的数，n个数需要n-1趟比较，因为最后一个数无需进行比较即可确定位置。第0趟比较，需要比较的最后一个数为num[0]，比较过后，位置0上的数据已确定，所以第1趟比较需要比较的最后一个数为num[1]，依次类推，第i趟比较需要比较的最后一个数为num[i]。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void BubbleSort_1(int num[], int n)
{ int i, j;
int temp;
for (i = 0; i < n - 1; i++)
{
for (j = n - 1; j > i; j--)
{
if (num[j - 1] > num[j])
{
temp = num[j - 1];
num[j - 1] = num[j];
num[j] = temp;
}
}
}
} |
2.优化1(对总趟数进行优化)
如果某趟比较过程中，没有数据进行交换，表明序列已有序，无需进行后续比较。因此可以对比较的趟数进行优化。
|
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
|
void BubbleSort_2(int num[], int n)
{ int i, j;
int temp;
int flag;
for (i = 0; i < n - 1; i++)
{
//第i趟比较时，先复位比较标志位。
flag = 0;
for (j = n - 1; j > i; j--)
{
if (num[j - 1] > num[j])
{
temp = num[j - 1];
num[j - 1] = num[j];
num[j] = temp;
//如果有比较过程，则置位标志位。
flag = 1;
}
}
//如果第i趟比较过程中没有交换，则序列已有序，结束循环。
if (flag == 0)
break;
}
} |
3.优化2(对每趟比较中的比较次数进行优化)
如果在第i趟比较过程中，最后一个进行交换的数为num[last]，表明num[0]~num[last]已为有序序列，因此在第i+1趟比较过程中，需要进行比较的最后一个数为num[last]。所以可以对每趟比较过程中比较的次数进行优化。
|
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
|
void BubbleSort_3(int num[], int n)
{ int i, j;
int temp;
int flag;
int head, head_t;
head_t = 0;
for (i = 0; i < n - 1; i++)
{
flag = 0;
//head指向第i趟比较过程中最后一个需要比较的元素，即第i-1趟比较过程中最后一个进行交换的元素。
head = head_t;
for (j = n - 1; j > head; j--)
{
if (num[j - 1] > num[j])
{
temp = num[j - 1];
num[j - 1] = num[j];
num[j] = temp;
head_t = j - 1;
flag = 1;
}
}
//退出该for循环时，head_t的值指向最后一个进行交换的元素。
if (flag == 0)
break;
}
} |