排序算法进阶(一)——快速排序算法

发表于

      偶然间看了一篇微信上的文章，CSDN链接，里面介绍了十大算法，分别是：

一：快速排序算法
二：堆排序算法
三：归并排序
四：二分查找算法
五：BFPRT(线性查找算法)
六：DFS(深度优先搜索)
七：BFS(广度优先搜索)
八：Dijkstra算法
九：动态规划算法
十：朴素贝叶斯分类算法

      虽然前面自己整理里几个基本排序查找算法，但看了这篇文章真有点惭愧啊！因此想抽空学习整理一下这些算法。

      首先就从快速排序算法入手，废话不多说，上图：
<img src=”https://lxzh.oss-cn-hangzhou.aliyuncs.com/Sorting_quicksort_anim.gif" width=”500”/ alt=”快速排序”>

      不过，正式写之前还是有必要做一些简单介绍，掌握一个好的算法，它的背景尝试也得了解一下嘛！

算法的概念：

      快速排序（Quicksort）是对冒泡排序的一种改进。由C. A. R. Hoare在1962年提出。

算法思想：

      用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串（sub-lists）：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

实现思路：

      ① 以第一个关键字 n1 为控制字，将 [n1 ,n2 ,…,nk ] 分成两个子区，使左区所有关键字小于等于 n1 ，右区所有关键字大于等于 n1 ，最后控制字居两个子区中间的适当位置。在子区内数据尚处于无序状态。
      ② 把左区作为一个整体，用①的步骤进行处理，右区进行相同的处理。（即递归）
      ③ 重复第①、②步，直到左区处理完毕。

算法步骤：

      *1) *从数列中挑出一个元素，称为 “基准”（pivot），
      *2) *重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
      *3) * 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
      递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

实现代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void QuickSort(int n[], int left, int right) {
	int mid;
	if (left < right) {
		mid = Partion(n, left, right);
		QuickSort(n, left, mid - 1);
		QuickSort(n, mid + 1, right);
	}
}

public static int Partion(int n[], int left, int right) {
	int pivot = n[left];// 也可以从n[right]开始
	while (left < right) {
		while (left < right && n[right] >= pivot)
			right--;
		if (left < right) {
			n[left++] = n[right];
		}
		while (left < right && n[left] <= pivot)
			left++;
		if (left < right) {
			n[right--] = n[left];
		}
	}
	n[left] = pivot;
	return left;
}

      为了更加直观的显示算法运行过程中数组数据变化情况，这里仍旧加一个打印函数：

1
2
3
4
5
6
7
public static void printList(int[] n) {
	int len = n.length;
	for (int i = 0; i < len; i++) {
		System.out.print(n[i] + ",");
	}
	System.out.println("");
}

      随便写一个数组int n[] = { 7, 8, 1, 9, 5, 10, 3, 2, 11 };
      通过打印中间结果来展示排序情况，完整代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * @author: lxzh
 * @E-mail: 1239848066@qq.com
 * @qq: 1239848066
 * @Date: 2015年8月1日上午12:01:31
 * @version: 1.0 Dscription: 快速排序
 */
public class QuickSortDemo {

	public static void main(String[] args) {
		int n[] = { 7, 8, 1, 9, 5, 10, 3, 2, 11 };
		printList(n);
		QuickSort(n, 0, n.length - 1);
		printList(n);
	}

	public static void QuickSort(int n[], int left, int right) {
		int mid;
		if (left < right) {
			mid = Partion(n, left, right);
			QuickSort(n, left, mid - 1);
			QuickSort(n, mid + 1, right);
		}
	}

	public static int Partion(int n[], int left, int right) {
		int pivot = n[left];// 也可以从n[right]开始
		while (left < right) {
			while (left < right && n[right] >= pivot)
				right--;
			if (left < right) {
				n[left++] = n[right];
				printList(n);
			}
			while (left < right && n[left] <= pivot)
				left++;
			if (left < right) {
				n[right--] = n[left];
				printList(n);
			}
			System.out.println();
		}
		n[left] = pivot;
		printList(n);
		return left;
	}

	public static void printList(int[] n) {
		int len = n.length;
		for (int i = 0; i < len; i++) {
			System.out.print(n[i] + ",");
		}
		System.out.println("");
	}
}

      编译运行后输出结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
7,8,1,9,5,10,3,2,11,
2,8,1,9,5,10,3,2,11,
2,8,1,9,5,10,3,8,11,

2,3,1,9,5,10,3,8,11,
2,3,1,9,5,10,9,8,11,

2,3,1,5,5,10,9,8,11,

2,3,1,5,7,10,9,8,11,
1,3,1,5,7,10,9,8,11,
1,3,3,5,7,10,9,8,11,

1,2,3,5,7,10,9,8,11,

1,2,3,5,7,10,9,8,11,
1,2,3,5,7,8,9,8,11,

1,2,3,5,7,8,9,10,11,

1,2,3,5,7,8,9,10,11,
1,2,3,5,7,8,9,10,11,

      仔细分析一下输出结果就能很好的理解该算法的原理啦！不多说了，读者自己去品味吧~       如果闲来没事的话，读者可以利用这个排序原理自己制作文中的那个动图，有兴趣的可以尝试一下！
      注：动态图片展示的是以数组最后一个值为基准，稍微修改一下上述代码就可以达到动图中的效果。

反馈请点击: