13.排序的思想和优化
目录介绍
1.基本思想
- 很好理解,从字面意思就知道类似于冒泡。在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。
- 即:每当两相邻的数比较后发现它们的排序与排序要求相反时,就将它们互换。
2.排序过程
- 比较相邻的两个数据,如果第二个数小,就交换位置。
- 从后向前两两比较,一直到比较最前两个数据。最终最小数被交换到起始的位置,这样第一个最小数的位置就排好。
- 继续重复上述过程,依次将第2.3...n-1个最小数排好位置。
image
3.代码实现
- 如下所示
public static void sort(int arr[]) { int length = arr.length; int temp; for(int i=0 ; i<length-1 ; i++) { for(int j=0 ; j<length-1 ; j++) { if(arr[j]>arr[j+1]) { //元素互换 temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } for(int i=0;i<arr.length;i++){ System.out.println("yc--1--doubi" +arr[i]); } } //下面这个在第二个for循环做了一些变动 public static void BubbleSort(int[] arr) { int temp;//临时变量 for (int i = 0; i < arr.length - 1; i++) { //表示趟数,一共arr.length-1次。 for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } } } for(int i=0;i<arr.length;i++){ System.out.println("yc1-----" +arr[i]); } }
4.如何优化
- 遇到问题
- 数据的顺序排好之后,冒泡算法仍然会继续进行下一轮的比较,直到arr.length-1次,后面的比较没有意义的。
- 解决办法
- 设置标志位flag,如果发生了交换flag设置为true;如果没有交换就设置为false。
- 这样当一轮比较结束后如果flag仍为false,即:这一轮没有发生交换,说明数据的顺序已经排好,没有必要继续进行下去。
- 优化代码
public static void BubbleSort2(int[] arr) { int temp;//临时变量 boolean flag;//是否交换的标志 for (int i = 0; i < arr.length - 1; i++) { //表示趟数,一共arr.length-1次。 flag = false; for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; flag = true; } } if (!flag) break; } for(int i=0;i<arr.length;i++){ System.out.println("yc2-----" +arr[i]); } }
- 冒泡排序进一步优化
- 进一步想象一个场景:现在有一个包含 1000 个数的数组,仅有前面 100 个数无序,后面的 900 个数都比前面的 100 个数更大并且已经排好序。
- 那么上面优化的方法又会造成一定的时间浪费,所以我们进一步增加一个变量记录最后发生交换的元素的位置,也就是排序的尾边界。
5.复杂度
- 空间效率:只占用一个辅存单元
- 时间效率:时间复杂度是O(n²)
- 待排序元素个数为n,则外层循环的比较次数为n-1次,对j个元素的子序列进行排序,则内层循环为j-1次,考虑最大情况下,则为n-1次,由此,冒泡排序总的比较次数为n(n-1)/2,所以时间复杂度为o(n的平方)。