经典排序算法之桶排序、冒泡排序和选择排序

男娘i 2022-05-16 03:35 254阅读 0赞

## 1.桶排序 ##

桶排序是将待排序的数据扔到按顺序排列的桶里，如下图：

![70][]

其中每个桶都有按顺序的编号（桶就是数组，编号是数组的下标），将每个数放到编号与之对应的桶里，然后再将桶里的数依次拿出来便排号了序。缺点：如果需要对100、2、0进行排序，则需要创建一个大小为101（下标从0开始，见上图）的数组，造成了严重的空间浪费。

**时间复杂度：**

对于N个待排数据，M个桶**：**

平均时间复杂度：O(N+N\*logN-N\*logM)

最好情况下的时间复杂度：O(N)，当N=M时，即极限情况下每个桶只有一个数据时。

如果相对于同样的N，桶数量M越大，其效率越高，最好是O(N)。当然桶排序的空间复杂度为O(N+M)，如果输入数据非常庞大，而桶的数量也非常多，则空间代价无疑是昂贵的。此外，桶排序是稳定的。

**示例代码：**

public class BucketSort {
    
    	public static void main(String[] args) {
    		int arr[] = {3, 1, 5, 3, 4};
    		bucketSort(arr);
    	}
    	
    	static void bucketSort(int arr[]) {
    		
    		//首先找出待排序数据的最大值
    		int max = 0;
    		for (int i = 0; i < arr.length; i++) {
    			if(max < arr[i]) {
    				max = arr[i];
    			}
    		}		
    		//创建桶
    		int bucket[] = new int[max + 1];
    		//将数据放入桶
    		for (int i = 0; i < arr.length; i++) {
    			bucket[arr[i]]++;
    		}
    		//输出桶里的数据
    		for (int i = 0; i < bucket.length; i++) {
    			for (int j = 0; j < bucket[i]; j++) {
    				System.out.print(i + " ");
    			}
    		}
    	}
    }

## 2.冒泡排序 ##

冒泡排序是比较相邻两个元素的大小，将大的（或小的），向后移动。

例如，我们需要对3，6，4，2，4进行排序（由小到大），则冒泡排序过程如下：

第一次循环：

3，6，4，2，4      第一次比较：3和6比较，3小于6，不移动，结果：3，6，4，2，4

第二次比较：6和4比较，6大于4，将6后移，结果：3，4，6，2，4

第三次比较：6和2比较，6大于2，将6后移，结果：3，4，2，6，4

第四次比较：6和4比较，6大于4，将6后移，结果：3，4，2，4，6

第二次循环：

3，4，2，4，6      第一次比较：2和4比较，3小于4，不移动，结果：3，4，2，4，6

第二次比较：4和2比较，4大于2，将4后移，结果：3，2，4，4，6

第三次比较：4和4比较，4等于4，不移动，结果：3，2，4，4，6

第三次循环：

3，2，4，4，6     第一次比较：3和2比较，3大于2，将3后移，结果：2，3，4，4，6

第二次比较：3和4比较，3小于4，不移动，结果：2，3，4，4，6

第四次循环：

2，3，4，4，6      第一次比较：2和3比较，2小于3，不移动，结果：2，3，4，4，6

排序完毕。

之所以称之为冒泡排序，是因为每次循环后都找出了最大（或最小）的元素向后移，就像水中的气泡一样，如图：

![70 1][]

看图像不像是冒泡呢？

**时间复杂度（运行起来效率最低的）：**若待排序数据的初始状态是正序的，一趟扫描即可完成排序。此时时间复杂度为![O(n)][O_n];若初始时是反序的，需要进行 ![8b82b9014a90f60364df45f83b12b31bb051ed26.jpg][] 趟排序。每趟排序要进行 ![503d269759ee3d6d1214597441166d224e4adebb.jpg][] 次关键字的比较，此时时间复杂度为![e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg][]；因此，平均时间复杂度为：![e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg][]。此外，冒泡排序是稳定的。

**示例代码：**

public class BubbleSort {
    
    	public static void main(String[] args) {
    		int arr[] = {3, 6, 4, 2, 4};
    		bubbleSort(arr);
    	}
    	
    	static void bubbleSort(int arr[]) {
    		
    		//需要循环的次数
    		for (int i = 0; i < arr.length - 1; i++) {
    			//比较次数
    			for (int j = 0; j < arr.length - i - 1; j++) {
    				//数据交换
    				if(arr[j] > arr[j + 1]) {
    					int temp = arr[j];
    					arr[j] = arr[j + 1];
    					arr[j + 1] = temp;
    				}
    			}
    		}
    		for(int a : arr) {
    			System.out.print(a + " ");
    		}
    	}
    }

## 3.选择排序 ##

选择排序是每一次从待排序的数据中选出最大（或最小）的一个元素，存放在未排序数据的后端（或前端）位置，直到全部待排序的数据元素排完。 其和冒泡排序类似，冒泡排序是两两比较交换，而此方法是先找出最大（或最小）值后再与序列的后端（或前端）进行交换，如图（别说这个图和冒泡排序的一样哈，看第一次循环后的是不一样的）：

![70 2][]

**时间复杂度（优于冒泡排序）：**最好和最坏情况都是![e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg][]，但交换次数少，优于冒泡排序。此外，选择排序是不稳定的。

**     示例代码：**

public class SelectionSort {
    
    	public static void main(String[] args) {
    		int arr[] = {3, 6, 4, 2, 4};
    		selesctionSort(arr);
    	}
    	
    	static void selesctionSort(int arr[]) {
    		
    		//最大元素下标
    		int maxIndex = 0;
    		int temp = 0;
    		//循环次数
    		for (int i = 0; i < arr.length; i++) {
    			maxIndex = 0;
    			//比较
    			for (int j = 0; j < arr.length - i; j++) {
    				if(arr[maxIndex] < arr[j]) {
    					maxIndex = j;
    				}
    			}
    			//将最大元素放到每趟未排序元素的最后
    			temp = arr[arr.length - i - 1];
    			arr[arr.length - i - 1] = arr[maxIndex];
    			arr[maxIndex] = temp;
    		}
    		for (int i = 0; i < arr.length; i++) {
    			System.out.print(arr[i] + " ");
    		}
    	}
    	
    }

[70]: /images/20220516/a6bddf3876794fb4903189f1cc74b0b6.png
[70 1]: /images/20220516/fe15582728b247b2a78a433007d37bf9.png
[O_n]: https://private.codecogs.com/gif.latex?O%28n%29
[8b82b9014a90f60364df45f83b12b31bb051ed26.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D32/sign=411c7ed7d309b3deefbfe26acdbf0492/8b82b9014a90f60364df45f83b12b31bb051ed26.jpg
[503d269759ee3d6d1214597441166d224e4adebb.jpg]: https://gss3.bdstatic.com/7Po3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D30/sign=3af139940cf41bd5de53eef450da752f/503d269759ee3d6d1214597441166d224e4adebb.jpg
[e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg]: https://gss1.bdstatic.com/-vo3dSag_xI4khGkpoWK1HF6hhy/baike/s%3D40/sign=17b28fa860d0f703e2b294dc09fa9d5c/e4dde71190ef76c63a4e22949f16fdfaae5167f5.jpg
[70 2]: /images/20220516/c820ee68ed5449d5954dfcdfdfd38967.png