一头扎进《快速排序》

本文主要是介绍一头扎进《快速排序》，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一头扎进《快速排序》

今天去听了一个讲座，师姐很厉害，在她的演讲中她提到了很多东西，未能够及时消化，回来马上开始码文档。师姐今天提及快排，但是要求我们要用**非递归**来实现。以前并没有很在意这些细节，想着能理解写出来不就可以了吗，今天特来写博文认错。
大家知道快排效率为O(N*logN)，在这几种排序方法中也算是效率较为高的一种算法了，采用的是“分治法”的思想，百度上描述为“是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)”。
快速排序（分治法）的主要思想是：

1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
我们日常都是喜欢用递归实现这么一个过程，简单，我就先写一下递归的做法，然后在用非递归的方式完成该算法操作。
具体代码如下所示（java实现）：

/** **快速排序用递归实现***/
public class SortDemo {public static void quick_sort(int s[], int l, int r) {if (l < r) {int i = l, j = r, x = s[l];while (i < j) {while (i < j && s[j] >= x)// 从右向左找第一个小于x的数j--;if (i < j)s[i++] = s[j];while (i < j && s[i] < x)// 从左向右找第一个大于等于x的数i++;if (i < j)s[j--] = s[i];}s[i] = x;quick_sort(s, l, i - 1); // 递归调用quick_sort(s, i + 1, r);}}public static void main(String[] args) {int[] a={7,12,2,45,6,8,52};quick_sort(a, 0, a.length-1);for (int i=0;i<a.length;i++) {System.out.print(a[i]+" ");}}
}

——– ——————- 分割线————————————

/

快速排序之非递归实现

先分析快速排序和冒泡排序的一些共同点：
- 都要经历n趟排序
- 每趟排序要经历O(n)次比较
- 都是后半部分元素比前半部大
不同之处就在于冒泡排序的交换操作发生相邻的元素之间，即一趟排序可以要经过多次交换操作；快速排序的交换操作发生在间隔比较远的两个元素之间，一趟排序要经过交换操作次数会少一些。
下面是非递归实现：

1. // start和end为前闭后闭  
2. private static void nonRec_quickSort(int[] a, int start, int end) {  
3.     // 用栈模拟  
4.     Stack<Integer> stack = new Stack<>();  
5.     if (start < end) {  
6.         stack.push(end);  
7.         stack.push(start);  
8.         while (!stack.isEmpty()) {  
9.             int l = stack.pop();  
10.             int r = stack.pop();  
11.             int index = partition(a, l, r);  
12.             if (l < index - 1) {  
13.                 stack.push(index - 1);  
14.                 stack.push(l);  
15.             }  
16.             if (r > index + 1) {  
17.                 stack.push(r);  
18.                 stack.push(index + 1);  
19.             }  
20.         }  
21.     }  
22.     System.out.println(Arrays.toString(a));  
23. }  
24. private static int partition(int[] a, int start, int end) {  
25.     int pivot = a[start];  
26.     while (start < end) {  
27.         while (start < end && a[end] >= pivot)  
28.             end--;  
29.         a[start] = a[end];  
30.         while (start < end && a[start] <= pivot)  
31.             start++;  
32.         a[end] = a[start];  
33.     }  
34.     a[start] = pivot;  
35.     return start;  
36. }  

这篇关于一头扎进《快速排序》的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---