【算法】冒泡排序

思路

冒泡排序就是将相邻的元素进行比较，然后将元素逐渐排好序，假设我们有n个元素，那么就是要比较n-1轮，因为最后剩下一个元素不用继续比较，然后在每轮中我们要比较n-轮数-1次，因为每经过一轮比较我们就排好一个元素，那么下轮比较次数就会减少一次。在比较时，我们可以设置一个变量用来当作标志位，如果进行了比较就将标志位置为1，然后在下轮前在将其赋0，如果有哪轮比较后标志位仍为0，说明没有需要排序的元素了，那么就可以直接结束循环。

代码

void BubbleSort(int *arr,int nLen){
	int temp = 0;
	for(int i = 0;i < nLen - 1;i++){
		int nCount = 0;                         //重置标志位
		for(int j = 0;j < nLen - i - 1;j++){
			if(arr[j] > arr[j+1]){              //升序
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
				nCount = 1;  
			}
		}
		if(nCount == 0){                        //没有需要继续排序的元素，结束循环
			break;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

测试代码

#include 
using nmaespace std;

int main(){
	int arr[10] = {3,1,5,2,4,9,7,8,0,6};
	int nLen = sizeof(arr)/sizeof(arr[0]);
	BubbleSort(arr,nLen);
	for(int i = 0;i < nLen;i ++){
		cout << arr[i] << “ ”;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12