目录
一 基本思想二 例子2.1 基本实现2.2 改进的实现
三 时间复杂度
一 基本思想
两两比较相邻的元素， 如果反序则交换， 直到没有反序的元素为止。
二 例子
2.1 基本实现
private int[] array
= new int[10] {4,5,6,3,2,1,7,8,9,0};
private void Sort()
{
for (int i
= 0; i
< array
.Length
; i
++)
{
for (int j
= array
.Length
- 1; j
> i
; j
--)
{
if (array
[j
] < array
[j
-1])
{
int temp
= array
[j
];
array
[j
] = array
[j
- 1];
array
[j
- 1] = temp
;
}
}
}
}
2.2 改进的实现
private void Sort()
{
bool needSort
= true;
for (int i
= 0; i
< array
.Length
&& needSort
; i
++)
{
needSort
= false;
for (int j
= array
.Length
- 1; j
> i
; j
--)
{
if (array
[j
] < array
[j
-1])
{
int temp
= array
[j
];
array
[j
] = array
[j
- 1];
array
[j
- 1] = temp
;
needSort
= true;
}
}
}
}
三 时间复杂度
最好的情况， 表内数据本来就是有序的， 比较次数为 n - 1 次，比较操作的时间复杂度为O(n)， 不需要移动，移动操作测时间复杂度是0 ， 总的时间复杂度是O(n)。最坏的情况， 表内数据是反序的，i = 0 时，需要比较 n - 1 次， 移动 n - 1 次， i= 1时， 需要比较 n - 2 次 ，移动 n - 2 次…, 也就是总的比较次数是 n(n-1) / 2 ， 总的移动次数是n(n-1) / 2，比较操作的时间复杂度是O(n²)， 移动操作的时间复杂度也是O(n²)。如果排序记录是随机的， 平均比较次数(n²/2)，移动次数约等于(n²/4)。最终的排序时间是比较和移动次数的总和， 因此， 总的时间复杂度是 O(n²)。
