做iOS前端很少用到算法, 所以很容易忘, 而熟練度這種東西, 是需要不斷去練習(xí)的.
冒泡排序算法的運(yùn)作如下：
1.比較相鄰的元素世剖。如果第一個(gè)比第二個(gè)大零远，就交換他們兩個(gè)撇叁。
2.對每一對相鄰元素作同樣的工作窖认，從開始第一對到結(jié)尾的最后一對渔工。最后的元素應(yīng)該會(huì)是最大的數(shù), 所以下次循環(huán)不比較最后一個(gè)元素.
3.針對所有的元素重復(fù)以上的步驟钞澳，除了最后一個(gè)。
4.持續(xù)每次對越來越少的元素重復(fù)上面的步驟涨缚，直到?jīng)]有任何一對數(shù)字需要比較
void bubble_sory(int array[], int count) {
for (int i = 0; i < count - 1; i++) {
for (int j = 0; j < count-1-i; j++) {
if (array[j] > array[j+1]) {
// 交換數(shù)值
array[j] = array[j]+array[j+1];
array[j+1] = array[j]-array[j+1];
array[j] = array[j]-array[j+1];
}
}
}
}
以上代碼或者說算法的時(shí)間復(fù)雜度:
最佳:O(n^2)
最差:O(n^2)
這樣我就懵逼了..網(wǎng)上明明說的最佳情況下時(shí)間復(fù)雜度為O(n)!
上面代碼最佳情況的時(shí)間復(fù)雜度確實(shí)應(yīng)該是O(n^2)轧粟，但算法可以改進(jìn)，使最佳情況時(shí)為O(n)脓魏。改進(jìn)后的代碼為：
void bubble_sory(int array[], int count) {
for (int i = 0; i < count - 1; i++) {
int didSwap = 0;
for (int j = 0; j < count-1-i; j++) {
if (array[j] > array[j+1]) {
// 交換數(shù)值
array[j] = array[j]+array[j+1];
array[j+1] = array[j]-array[j+1];
array[j] = array[j]-array[j+1];
didSwap = 1;
}
}
if (didSwap == 0) {
return;
}
}
}
即確定數(shù)組已經(jīng)是期待的結(jié)果, 就退出算法.
這樣時(shí)間復(fù)雜度就對了, 小白的感情傷不起啊.
