数据结构之排序算法——快速排序（Java实现）

桃扇骨 2023-03-13 05:55 13阅读 0赞

➢ **基本介绍**

快速排序(Quicksort) 是对冒泡排序的一种改进。基本思想是:通过一趟排序，将要排序 的数据分割成独立的两部分，其中一部分的所有 数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

➢ **思路分析图解**  
使用一个简单特殊的测试数组作为基本。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
代码实现：

public static void fast(int[] arr, int left, int right) { 
    		int L = left; // 左下标
    		int R = right; // 右下标
    		int middle = arr[(left + right) / 2]; // 中间值
    		int temp = 0;
    		// 把数据大小放于左右俩边
    		while (L < R) { 
    			while (arr[L] < middle) { 
    				L += 1;
    			}
    			while (arr[R] > middle) { 
    				R -= 1;
    			}
    			// L >= R条件满足，表示左右两边的值都满足
    			if (L >= R) { 
    				break;
    			}
    			// 交换,
    			temp = arr[R];
    			arr[R] = arr[L];
    			arr[L] = temp;
    
    			// 交换之后，arr[L] == middle R-- 前移
    			if (arr[L] == middle) { 
    				R--;
    			}
    			// 交换之后，arr[L] == middle L++ 后移
    			if (arr[R] == middle) { 
    				L++;
    			}
    		}
    		// 递归排序，如果L==R L++ R--
    		if (L == R) { 
    			L++;
    			R--;
    		}
    		// 向左递归
    		if (left < R) { 
    			fast(arr, left, R);
    		}
    		// 向右递归
    		if (right > L) { 
    			fast(arr, L, right);
    		}
    	}

测试代码：调用函数传递数组即可：

int[] arr = {  -9, 78, 0, 23, -567, 70 };
    		fast(arr, 0, arr.length - 1);
    		System.out.println(Arrays.toString(arr));

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]  
测试快速排序的效率：使用先前的代码进行测试：

int[] arr1 = new int[100000];
    		for (int i = 0; i < 100000; i++) { 
    			arr1[i] = (int) (Math.random() * 1000000); // 生成一个[0,1000000) 的随机数
    		}
    		Date a = new Date();
    		SimpleDateFormat SimpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
    		String a1 = SimpleDateFormat.format(a);
    		System.out.println("排序前：" + a1);
    		fast(arr1, 0, arr1.length - 1);
    
    		Date b = new Date();
    		String b1 = SimpleDateFormat.format(b);
    		System.out.println("排序后：" + b1);

在测试100000个数据的时候，速度还是很快的，基本上在1秒之内就完成了，这个时候，在后面再加俩个0，测试10000000个数据。如下图：速度还是很快；  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: /images/20230312/2170bfd456da4544b4879b9be44742b5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: /images/20230312/1f66aee93e9541a78fa69001d787a8d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]: /images/20230312/06af3c1a3e1b4ebcb05ae201f54ba586.png