如果遇到相等的值不进行交换,那这种冒泡排序方式是稳定的排序方式。
原理:以升序为例,比较两个相邻的元素,将值大的元素交换到右边。
-
思路:依次比较相邻的两个数,将比较小的数放在前面,比较大的数放在后面。
(3.1)以数组的第一个数与相邻的第二个数进行比较,将小数放在前面,将大数放在后面。
(3.2)刚刚比较完的(较大)第二个数与相邻的第二个数进行比较,将小数放在前面,将大数放在后面。
......
(3.3)以此类推,第一轮比较之后,最大的那个数会排在最后,就像在水里那个最大的气泡会最先冒出水面一样,所以这种算法也叫冒泡咆哮。
(3.4)在上面一趟比较完成后,最后一个数一定是数组中最大的一个数,所以在比较第二趟的时候,最后一个数不参加比较。
(3.5)在第二趟比较完成后,倒数第二个数就是第二大数。
4.举例:
(1)要排序的数组是:[6,5,4,3,2]static void Main(string[] args) { List<int> TestList = new List<int>(); TestList.Add(6); TestList.Add(5); TestList.Add(4); TestList.Add(3); TestList.Add(2); Console.WriteLine(TestList[0].ToString() + " " + TestList[1].ToString() + " " + TestList[2].ToString() + " " + TestList[3].ToString() + " " + TestList[4].ToString()); BubbleSort(TestList); Console.ReadLine(); } /// <summary> /// 冒泡排序 /// </summary> /// <param name="arr"></param> static void BubbleSort(List<int> arr) { //控制冒泡次数 for (int i = 0; i < arr.Count - 1; i++) { //i,i+1 for (int j = 0; j < arr.Count - 1 - i; j++) { //两两比较 i i+1 if (arr[j] > arr[j + 1]) { Swap(arr, j, j + 1); } } Console.WriteLine(arr[0].ToString() + " " + arr[1].ToString() + " " + arr[2].ToString() + " " + arr[3].ToString() + " " + arr[4].ToString()); } } /// <summary> /// 两两交换 /// </summary> /// <param name="arr"></param> /// <param name="j"></param> /// <param name="v"></param> static void Swap(List<int> arr, int j, int v) { int temp = arr[j]; arr[j] = arr[v]; arr[v] = temp; }
5.输出结果
6 5 4 3 2
5 4 3 2 6
4 3 2 5 6
3 2 4 5 6
2 3 4 5 6
每一趟比较完成以后,第1,第2,第3大的数等等,也就是6,5,4...都会被依次冒泡查找出来。