算法基础02——排序之快速&归并排序

快速排序

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。

快速排序算法通过多次比较和交换来实现排序,其排序流程如下:

  1. 首先设定一个分界值,通过该分界值将数组分成左右两部分。

  2. 将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边。此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值。

  3. 然后,左边和右边的数据可以独立排序。对于左侧的数组数据,又可以取一个分界值,将该部分数据分成左右两部分,同样在左边放置较小值,右边放置较大值。右侧的数组数据也可以做类似处理。

  4. 重复上述过程,可以看出,这是一个递归定义。通过递归将左侧部分排好序后,再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后,整个数组的排序也就完成了。

随机快速排序

经典快速排序总是指定数组或者某部分的最后一个元素作为基准值,随机快速排序指定数组或者某一部分中的随机值作为基准值。

快速排序可视化过程

/**
 * 快速排序
 * @author yixunfei
 *
 */
public class QuickSort {

	public static void sort(int[] arr) {
		quickSort(0, arr.length - 1, arr);
	}

	private static void quickSort(int start, int end, int[] arr) {
		if(start > end) {
			return;
		}
		int i = start;
		int j = end;
		int flag = arr[start];
		int changeTemp;
		
		while(i != j) {
			while(arr[j] >= flag && i < j) {
				j--;
			}
			while(arr[i] <= flag && i < j) {
				i++;
			}
			if(i < j) {
				changeTemp = arr[i];
				arr[i] = arr[j];
				arr[j] = changeTemp;
			}
		}
		
		 arr[start]=arr[i]; 
		 arr[i]=flag;
		
		quickSort(start,i-1,arr);
		quickSort(i+1,end,arr);
	}

}

归并排序

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。归并排序是一种稳定的排序方法。

如果要排序一个数组,我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。

递推公式:
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))

终止条件:
p >= r 不用再继续分解

merge_sort(p…r) 表示,给下标从 p 到 r 之间的数组排序。我们将这个排序问题转化为了两个子问题,merge_sort(p…q) 和 merge_sort(q+1…r),其中下标 q 等于 p 和 r 的中间位置,也就是 (p+r)/2。当下标从 p 到 q 和从 q+1 到 r 这两个子数组都排好序之后,我们再将两个有序的子数组合并在一起,这样下标从 p 到 r 之间的数据就也排好序了。

merge(A[p…r], A[p…q], A[q+1…r]) 这个函数的作用就是,将已经有序的 A[p…q]和 A[q+1…r]合并成一个有序的数组,并且放入 A[p…r]。

如图所示,我们申请一个临时数组 tmp,大小与 A[p…r]相同。我们用两个游标 i 和 j,分别指向 A[p…q]和 A[q+1…r]的第一个元素。比较这两个元素 A[i]和 A[j],如果 A[i]<=A[j],我们就把 A[i]放入到临时数组 tmp,并且 i 后移一位,否则将 A[j]放入到数组 tmp,j 后移一位。
image.png

我们申请一个临时数组 tmp,大小与 A[p…r]相同。我们用两个游标 i 和 j,分别指向 A[p…q]和 A[q+1…r]的第一个元素。比较这两个元素 A[i]和 A[j],如果 A[i]<=A[j],我们就把 A[i]放入到临时数组 tmp,并且 i 后移一位,否则将 A[j]放入到数组 tmp,j 后移一位。继续上述比较过程,直到其中一个子数组中的所有数据都放入临时数组中,再把另一个数组中的数据依次加入到临时数组的末尾,这个时候,临时数组中存储的就是两个子数组合并之后的结果了。最后再把临时数组 tmp 中的数据拷贝到原数组 A[p…r]中。

归并排序可视化过程

public class MergeSort {
	public static void main(String[] args) {
		int[] arr = { 9, 5, 2, 7, 3, 8, 4, 0, 2, 3, 3 };
		sort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void sort(int[] arr) {
		// 在排序前,先建好一个长度等于原数组长度的临时数组,避免递归中频繁开辟空间
		int[] temp = new int[arr.length];
		mergeSort(arr, 0, arr.length - 1, temp);
	}

	private static void mergeSort(int[] arr, int left, int right, int[] temp) {
		if (left < right) {
			// 计算递归的中间值
			int mid = (left + right) / 2;
			// 左边归并排序,使得左子序列有序
			mergeSort(arr, left, mid, temp);
			// 右边归并排序,使得右子序列有序
			mergeSort(arr, mid + 1, right, temp);
			// 将两个有序子数组合并操作
			merge(arr, left, mid, right, temp);
		}
	}

	private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		// 左序列指针
		int leftIndex = left;
		// 右序列指针
		int rightIndex = mid + 1;
		// 临时数组指针
		int tempIndex = 0;

		while (leftIndex <= mid && rightIndex <= right) {
			if (arr[leftIndex] <= arr[rightIndex]) {
				temp[tempIndex] = arr[leftIndex];
				tempIndex++;
				leftIndex++;
			} else {
				temp[tempIndex] = arr[rightIndex];
				tempIndex++;
				rightIndex++;
			}
		}
		// 将左边剩余元素填充进temp中
		while (leftIndex <= mid) {
			temp[tempIndex] = arr[leftIndex];
			tempIndex++;
			leftIndex++;
		}
		// 将右序列剩余元素填充进temp中
		while (rightIndex <= right) {
			temp[tempIndex] = arr[rightIndex];
			tempIndex++;
			rightIndex++;
		}
		tempIndex = 0;
		// 将temp中的元素全部拷贝到原数组中
		while (left <= right) {
			arr[left] = temp[tempIndex];
			left++;
			tempIndex++;
		}
	}
}

更新时间:2020-02-15 11:52:20

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/算法基础02排序之快速归并排序
最后更新:2020-02-15 11:52:20

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×