排序方法有很多,最常用的有冒泡排序、快速排序和归并排序。

时间复制度对比:

排序算法 平均时间复杂度 最好情况 最坏情况 空间复杂度 稳定性
冒泡排序 O(n^2) O(n) O(n^2) O(1) 稳定
快速排序 O(n log n) O(n log n) O(n^2) O(log n) 不稳定
归并排序 O(n log n) O(n log n) O(n log n) O(n) 稳定

下面我们来说一下快速排序,快速排序我使用的是挖坑法,也就是找一个基准元素baseNum,一般是拿nums[0]作为基准元素。首先从数组的最右侧往左寻找比baseNum小的第一个数(假设下标nums[7]),将此数填入nums[0]位置,然后从数组的最左边往右找第一个比baseNum大或等于的第一个元素填入nums[7]的位置。依次类推,找到左右重合时,将baseNum填入此位置,此时进行了第一轮排序。数组的左边是比baseNum小的元素,右边的元素大于或等于baseNum。一分为二,使用递归排序左边和右边的元素即可实现。

下面示例演示数据变化

原始数据nums:

首先找数组左边的第一个数5作为基准元素,赋值给变量baseNum

int baseNum = nums[0]

第一轮

quickSort(nums,0,nums.length-1);

(1.1)从右->左找第一个小于baseNum的位置(下标为5)

将4填入左边num[0]位置,如下

此时发现数组中出现了2个4,而元素5没有了。不用担心,后面会将baseNum重新填入数组中。

(1.2)从左往右找第一个大于等于baseNum的位置下标(下标为1)

将6填入右边num[5]的位置,如下

(2.1)从右->左找第一个小于baseNum的位置(下标为4)

这里从下标为5-1的位置从右往左找

将1填入左边num[1],如下

(2.2)从左往右找第一个大于等于baseNum的位置下标(下标为3)

这里从下标1+1的位置从坐往右找

将8填入右边nun[4]的位置,如下

(3.1)从右->左找第一个小于baseNum的位置

从下标为4-1的位置从右往左找,我们发现左边和右边重合在了下标为3的位置。表示此轮循环结束,将最开始的基准元素baseNum赋值给num[3]重合的位置。如下

此时发现以下标3为界限,左边是小于5的元素,右边是大于等于5的元素。使用递归分别排序左边和右边的元素。重复上述步骤。

quickSort(nums,low,left-1);

quickSort(nums,left+1,high);

递归终止条件是left>=right,表示左右指针重合。

Java代码示例如下

public class SpeedSort {
	public static void main(String[] args){
		int[] nums = {5,6,2,8,1,4,7};
		quickSort(nums,0,nums.length-1);
		for (int num : nums) {
			System.out.print(num+" ");
		}
	}
	/**
	 * 快速排序(挖坑法实现)
	 * https://www.runoob.com/w3cnote/quick-sort.html
	 */
	public static void quickSort(int[] nums, int low, int high){
		// 终止递归条件
		if(low >= high){
			return;
		}
		int left = low,right = high,baseNum = nums[left];
		while(left < right){
			// 从右往左找第一个小于baseNum的元素 填入到baseNum的坑上面
			for(;left<right;right--){
				if(nums[right] < baseNum){
					nums[left] = nums[right];
					// 填坑后,left要往右移动以为
					left++;
					break;
				}
			}
			// 从左往右找第一个大于temp的元素
			for(;left<right;left++){
				if(nums[left] >= baseNum){
					nums[right] = nums[left];
					// 填坑后,right要往左移动以为
					right--;
					break;
				}
			}
		}
		// 递归
		System.out.println("left:"+left);
		System.out.println("right:"+right);
		// 填坑一轮后,left和right一定是相同的,也就是left左边是<baseNun,右边是>=baseNum
		// 将baseNum填入left位置
		nums[left] = baseNum;
		// 从left切分,分别排序左边和右边的元素
		quickSort(nums,low,left-1);
		quickSort(nums,left+1,high);
	}
}


发表评论

电子邮件地址不会被公开。 必填项已用*标注