快速排序解析

快速排序解析

快速排序用到的知识点，递归，分制。

思想，如果将数列要从小到大的排列，先取一个数做为比较数a（一般取要数列或者拆开数列的第一个数，也看个人习惯），先从右往左找比a小的数据，并交换数据。交换完数据后，在交互数据的位置从左往右找比a大的数据，找到后，再交换数据。这算是一轮结束。这一轮结束后，左索引会将数组分成两半，然后将0到左索引与左索引到末尾变成两组数组，然后递归分制，上面的循环。直到每个数组的左索引和右索引相同了，说明这个数组就排好了。

算法担心的问题：一个数组被索引分开后，会担心前半部分的最大数会比后半部分的最小数要大。

解疑：

不会出现这样问题的，算法设计是（比如从小到大排），先从左边第一个作为比较数a,左索引为l=0,右索引为r=数组的长度。先从右索引往左找比a小的数，找不到就r--,直到在r1位置找到了比a小的数据，就将r1位置的与l位置的数据互换（此时l位置的数据就是0，也是比较数a,）换完之后此时，r1+1位置到r的位置都比a要大，上半轮结束。下半轮开始，从左索引（l）往右找比r1（此时的r1位置就是a）位置大的数，找不到就l++,直到在l1位置找到比r1位置大的数然后交换r1与l1位置的数，此时l1位置的数就是a,下半轮结束。这一轮结束后，这个数列从0位置到l1位置的数都是比l1位置的数（即a）都小或等于（等于性质放在左右边都可以），然后从l1到末尾的数都是比l1位置（即a）都大的数。这样由l1位置将这个数组分成两组（不拆数组），每组进行单独排序（分制递归）。就可保障这个数组从小到大排列。

代码实现

package src.main.lib;

public class 快速排序 {

	public static void main(String[] args) {
		int[] arr = { 5, 9, 7, 4, 3, 5, 1, 6 };
		// int[] arr = {5,9,7};
		quick_sort(arr, 0, 7);
	}

	// 快速排序
	public static void quick_sort(int s[], int l, int r) {
		// int[] arr = {5,9,7,4};
		if (l < r) {
			// Swap(s[l], s[(l + r) / 2]); //将中间的这个数和第一个数交换 参见注1
			int i = l, j = r, x = s[l];
			while (i < j) {
				while (i < j && s[j] >= x) { // 从右向左找第一个小于x的数
					j--;
				}
				if (i < j) {
					int temp = s[i];
					s[i] = s[j];
					s[j] = temp;
					i++;
				}
				System.out.println("左索引：" + i + ",右索引：" + j);
				print(s);
				System.out.println();// 4,9,7,4

				// i = l;
				// j = r;
				while (i < j && s[i] < x) {// 从左向右找第一个大于等于x的数
					i++;
				}
				if (i < j) {
					int temp = s[j];
					s[j] = s[i];
					s[i] = temp;
					j--;
				}
				System.out.println("左索引：" + i + ",右索引：" + j);
				print(s);
				System.out.println();// 4,5,7,9
			}
			// s[i] = x;
			if (l < (i - 1)) {
				quick_sort(s, l, i - 1); // 递归调用
			}
			if ((i + 1) < r) {
				quick_sort(s, i + 1, r);
			}
		}
	}

	public static void print(int[] arr) {
		for (int i : arr) {
			System.out.print(i + " ");
		}
	}
}