重温冒泡排序(优化思路+鸡尾酒排序)

拼搏现实的明天。 2023-06-26 08:21 7阅读 0赞

第一版冒泡排序：

public void sort(int[] arr){ 
    		for (int i = arr.length - 1; i >= 0; i--){ 
    			for (int j = 0; j < i; j++){ 
    				if (arr[j] > arr[j + 1]){ 
    					int temp = arr[j];
    					arr[j] = arr[j + 1];
    					arr[j + 1] = temp;
    				}
    			}
    		}
    	}

第二版冒泡排序：

/** * 在序列整体已有序时，跳过最后几躺无效的排序 * 该躺排序没有发生元素交换，则认为已有序 */
    public void sortV2(int[] arr){ 
    		for (int i = arr.length - 1; i >= 0; i--){ 
    			boolean isSorted = true;
    			for (int j = 0; j < i; j++){ 
    				if (arr[j] > arr[j + 1]){ 
    					int temp = arr[j];
    					arr[j] = arr[j + 1];
    					arr[j + 1] = temp;
    					isSorted = false;
    				}
    			}
    			if (isSorted)
    				break;
    		}
    	}

第三版冒泡排序：

/** * 每躺排序，记录最后一次发生交换的位置，确定下一趟排序的终点 * 可以跳跃式的设定下趟排序的终点，而不是像原先，每趟排序后，下趟排序的终点只往前挪动一个位置 * 可减少一定次数的比较 */
    public void sortV3(int[] arr){ 
    		int sortedSize = 0;
    		while (true){ 
    			boolean isSorted = true;
    			int lastSwapPos = 0;
    			for (int j = 0; j < arr.length - 1 - sortedSize; j++){ 
    				if (arr[j] > arr[j + 1]){ 
    					int temp = arr[j];
    					arr[j] = arr[j + 1];
    					arr[j + 1] = temp;
    					isSorted = false;
    					lastSwapPos = j;
    				}
    			}
    			if (isSorted)
    				break;
    			sortedSize = arr.length - 1 - lastSwapPos;
    		}
    	}

第四版冒泡排序 - 鸡尾酒排序

/** * 冒泡排序升级版 - 鸡尾酒排序 * 用于优化像 2 3 4 5 6 7 8 1 9 这样的序列 * 采用双向冒泡，奇数轮向右冒泡，偶数轮向左冒泡 * 像钟摆一样 */
    public void cockTailSort(int[] arr){ 
    		int leftBorder = 0,rightBorder = arr.length - 1;
    		boolean toRight = true;
    		while (true){ 
    			boolean isSorted = true;
    			if (toRight){ 
    				int lastSwapPos = leftBorder;
    				for (int i = leftBorder; i < rightBorder; i++){ 
    					if (arr[i] > arr[i + 1]){ 
    						int temp = arr[i];
    						arr[i] = arr[i + 1];
    						arr[i + 1] = temp;
    						isSorted = false;
    						lastSwapPos = i;
    					}
    				}
    				rightBorder = lastSwapPos;
    				toRight = false;
    			}else { 
    				int lastSwapPos = rightBorder;
    				for (int i = rightBorder; i > leftBorder ;i--){ 
    					if (arr[i] < arr[i - 1]){ 
    						int temp = arr[i];
    						arr[i] = arr[i - 1];
    						arr[i - 1] = temp;
    						isSorted = false;
    						lastSwapPos = i;
    					}
    				}
    				leftBorder = lastSwapPos;
    				toRight = true;
    			}
    			if (isSorted)
    				break;
    		}
    	}

分析发现，3种方式，元素交换的次数都是一样的。后两种优化，优化的点在于减少了不必要的比较次数。  
一开始交换元素的方式采用的是一种奇特的**异或方式**，这样虽然可以不必开辟额外存储空间，但是会极其影响性能。我将交换改为最简单的使用一个中间变量temp来完成，排序花费时间减少了将近一倍。由原先的800ms左右变到400ms。**可见奇淫技巧并不一定是牛逼的。有时候简单的才最牛逼！**

针对随机生成的大小为1000的数组，几种排序，比较和交换次数如下：  
![在这里插入图片描述][20200105162446730.png]  
4种排序，对大小为1000的数组进行排序所花时长的结果如下：  
![在这里插入图片描述][20200105183712473.png]  
另附上2数交换的奇淫技巧，权当记录一道智力题:-)

protected void swap(int[] arr,int i ,int j){ 
    		//该方法有个前提
            //i和j不能相等，否则将出错
            if (i == j)
                return;
            int size = arr.length;
            if (i >= size || j >= size || i < 0 || j < 0)
                throw new IndexOutOfBoundsException("i = " + i + ",j = " + j + ",but size = " +size);
            //most efficient method for swap two numbers --many days before
            
            //but now I'm afraid simple is best :-)
            arr[i] = arr[i] ^ arr[j];
            arr[j] = arr[i] ^ arr[j];
            arr[i] = arr[i] ^ arr[j];
        }

一个冒泡排序又折腾了一晚上，洗洗睡咯~

[20200105162446730.png]: https://img-blog.csdnimg.cn/20200105162446730.png
[20200105183712473.png]: https://img-blog.csdnimg.cn/20200105183712473.png