# Bubble Sort Demo

**Repository Path**: mrfu/bubble-sort-demo

## Basic Information

- **Project Name**: Bubble Sort Demo
- **Description**: 冒泡排序总结
- **Primary Language**: Java
- **License**: Apache-2.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-07-20
- **Last Updated**: 2021-07-21

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Bubble Sort Demo

#### 冒泡排序总结

冒泡排序 Bubble Sort， 是一种基础的 **[交换排序]**<br/>
#### 交换思想：<br/>
        把相邻的两个元素两两比较，当一个元素大于右侧元素时，交换它们的位置；<br/>
        当一个元素小于或等于右侧元素时，位置不变。<br/>
        冒泡排序是一种稳定的排序，值相等的元素并不会打乱原本的顺序。<br/>
        由于该排序算法的每一轮都要遍历所有元素，总遍历（元素数量 - 1）轮，所以平均时间复杂度是 O(n²)


#### 方法说明

1.  sort1(int[]) ==> 原始冒泡排序方法<br/>
    把相邻的两个元素两两比较，当一个元素大于右侧元素时，交换它们的位置；当一个元素小于或等于右侧元素时，位置不变。<br/>
    每一轮都要遍历所有元素，总遍历（元素数量 - 1）轮，所以平均时间复杂度是 O(n²)
2.  sort2(int[]) ==> 冒泡排序优化<br/>
    定义一个标记 isSorted = true，表示该轮数组已是一个有序数组<br/>
    在排序比较过程中，只要出现一次相邻的两个元素发生位置交换，则说明数组是无序的，做出标记 isSorted = false；<br/>
    反之，在该轮比较过程中，无相邻的两个元素交换位置，则说明此时数组已是有序的，<br/>
    则做出标记 isSorted = true，剩下几轮排序比较则不必继续执行（跳出循环）
3.  sort3(int[]) ==> 冒泡排序优化<br/>
    定义一个标记 isSorted = true，表示该轮数组已是一个有序数组<br/>
    在排序比较过程中，只要出现一次相邻的两个元素发生位置交换，则说明数组是无序的，做出标记 isSorted = false；<br/>
    反之，在该轮比较过程中，无相邻的两个元素交换位置，则说明此时数组已是有序的，<br/>
    记录最后一次交换元素的位置，作为无序数组的边界，每一轮比较只需要比到这个边界位置即可<br/>
    情况一：没有元素进行位置交换，证明已经有序，排序结束。<br/>
    情况二：无序数组边界为 0 时，说明数组已然有序，直接跳出大循环<br/>
    适应于已知存在一段有序元素的数组
4.  sort4(int[]) ==> 鸡尾酒排序<br/>
    双向排序，元素的比较和交换操作是双向的<br/>
    排序过程像钟摆一样，每一轮从左到右一次，再从右到左一次，没有元素进行位置交换，证明已经有序，排序结束。
5.  sort5(int[]) ==> 鸡尾酒排序优化<br/>
    双向排序，元素的比较和交换操作是双向的<br/>
    排序过程像钟摆一样，每一轮从左到右一次，记录最后一次交换元素的位置，作为无序数组的边界 sortBorderRight，每一轮比较只需要比到这个边界位置即可；<br/>
    再从右到左一次，记录最后一次交换元素的位置，作为无序数组的边界 sortBorderLeft，每一轮比较只需要比到这个边界位置即可<br/>
    情况一：没有元素进行位置交换，证明已经有序，排序结束。<br/>
    情况二：无序数组边界为 sortBorderRight == sortBorderLeft 时，说明数组已然有序，直接跳出大循环
6.  swap(int[], int, int)  ==> 交换数组中指定位置上的元素

备注: System.out.print 语句只是为了在控制台描述交换过程