一、思路：1、创建两个空栈A和B；2、A栈作为队列的入口，B栈作为队列的出口；3、入队列操作：即是入栈A；4、出队列操作：若栈B为空，则将A栈内容出栈并压人B栈，再出 B栈；不为空就直接出栈；
二、代码：
1、头文件：stack_to_queue.h：封装了:队列、栈的数据结构和各种操作的函数。
2 #define STACK_TO_QUEUE_H
3
4 #include<stdio.h>
5 #include<stdlib.h>
6
7 #define ALLOC_SIZE 512
8 #define ElemType int
9
10 typedef struct sqstack
11 {
12 ElemType *top; //栈顶指针
13 ElemType *base; //栈底指针
14 ElemType stack_size; //栈目前的元素数目
15 }SqStack; //顺序栈
16
17 typedef struct sqqueue
18 {
19 SqStack front; //队列头，出口，
20 SqStack rear; //队列尾，入口
21 }SqQueue;
22
23 /*栈的初始化函数*/
24 void InitStack(SqStack *s)
25 {
26 if((s->top=(ElemType*)malloc(ALLOC_SIZE*sizeof(ElemType)))==NULL)
27 {
28 printf("stack malloc error\n");
29 exit(1);
30 }
31 s->base=s->top;
32 s->stack_size=ALLOC_SIZE;
33 }
34
35 /*出栈函数，栈为空时返回0，成功出栈时返回1*/
36 int pop_stack(SqStack *s,ElemType *data)
37 {
38 if(s->top!=s->base)
39 {
40 s->top--;
41 *data=*s->top;
42 return 1;
43 }
44 else //返回值为0，表示栈为空
45 {
46 return 0;
47 }
48 }
49
50 /*入栈函数*/
51 void push_stack(SqStack *s,ElemType data)
52 {
53 if((s->top-s->base)>=s->stack_size)
54 {
55 if((s->base=(ElemType *)realloc(s->base,(s->stack_size+ALLOC_SIZE)*sizeof(ElemType)))==NULL)
56 {
57 printf("stack realloc error\n");
58 exit(1);
59 }
60 else
61 {
62 s->top=s->base+s->stack_size;
63 s->stack_size+=ALLOC_SIZE;
64 }
65 }
66 *(s->top)=data;
67 s->top++;
68 }
69
70 /*队列初始化函数*/
71 void InitQueue(SqQueue *q)
72 {
73 SqStack A,B;
74
75 InitStack(&A);
76 InitStack(&B);
77 q->front=B; //将栈B作为队列的出口
78 q->rear=A; //将栈A作为队列的入口
79 }
80
基础排序算法之快速排序(Quick Sort) - 热爱GIS的坏蜀黍 阅读原文»
快速排序(Quick Sort)同样是使用了分治法的思想，相比于其他的排序方法，它所用到的空间更少，因为其可以实现原地排序。同时如果随机选取中心枢(pivot)，它也是一个随机算法。最重要的是，快速排序(Quick sort)的算法分析的过程非常给力。
本文首先描述问题，再说明快速排序(Quick Sort)的基本思路并给出伪代码，之后贴出自己的Python代码。在验证完算法的正确性之后，给出如何选择好的中心枢(pivot)的方法，即随机快速排序(Randomized Quick sort)，并贴代码。最后进行算法复杂度分析。
问题描述
问题描述和其他排序算法一样，输入一组未排序的数组，如左边的数组，通过快速排序算法的计算，输出一组正确排序的数组，如右边的数组。
基本思路和伪代码
在给定的数组中选择一个元素作为中心枢(pivot)，对数组重排列并分割(Partition)，使得位于该中心枢(pivot)左边的元素都小于该元素，右边的元素都大于该元素，之后递归处理左右两组数。
这里值得注意的地方就是，每一次重排列之后，所选择的中心枢(pivot)元素所在的位置，就是最终排序结果中它应该在的位置。
2 if n = 1 return
3 p = choosePivot(A, n)
4 Partition A around p
5 recursively sort 1st part
6 recursively sort 2st part
经过第4行的操作之后，位于左边的所有元素都小于p，而右边的数都大于p。下文中所有中心枢(pivot)元素都用p表示。
基于某一个p来对数组进行分块有两种实现的方法，第一种方法在内存在开辟新的数组，遍历元素组元素，小于p的从头插入数组，大于p的从尾部插入数组，给个例子：
而第二种方法是原地排序，比第一稍微复杂一点。假设p元素总在数组的最前端（不在最前端就让它和最前端的元素交换），将整个数组分为两部分，前半部分为已经和p比较过的元素集，后半部分为没有和p比较过的元素集。其中前半部分又分为小于p和大于p两部分。如图：
那么只要需要两个标记值i和j就可以所有部分分割开。i 标记小于p部分末端元素，j标记大于p部分的末端元素。如下例：
分割(Partition)的伪代码:
p=A[l]
i=l+1
for j=l+1 to r
if A[j]<p
swap A and A[j]
i=i+1
swap A[l] and A
假设处理的数组长度为N，从伪代码中可以比较容易算出，Partition的时间复杂度为O(N)，而且也实现了原地排序。
Python代码
Pivot选取首元素的实现
2
3 def quick_sort(datalist,l,r):
4 if l<r-1:
5 q=partition_first(datalist,l,r)
6 datalist=quick_sort(datalist,l,q)
7 datalist=quick_sort(datalist,q+1,r)
8 return datalist
9 else:
10 return datalist
11
12 def partition_first(datalist,l,r):
13 p=datalist[l]
14 i=l+1
15 for j in range(l+1,r):
16 if datalist[j]<p:
17 datalist,datalist[j]=datalist[j],datalist
18 i=i+1
19 datalist[l],datalist=datalist,datalist[l]
20 return i-1
验证算法的正确性
用数学归纳法来检验算法的正确性：
P(N)=快速排序(Quick sort)正确排序长度为N的数组。
Claim：无论选择什么p，在N>=1情况下，P(N)总能正确。
证明:
- 第一步：对于N=1时，返回该值。第一步完成。
- 第二步：第二步中只需要证明对于固定的n，如果∀k<n时，P(k)成立，那么P(n)也成立。
- 快速排序基于p进行分割数组时候，p在此次partition中之后，它所在所在的位置，就是最终排序结果中它应该在的位置。如上图所示，k1为1st part的数组长度，k2为2st part的数组长度。根据前面的假设∀k<n都递归成立，所以经过递归之后，整个数组正确排序。(QED!)
选择好的p值（随机快速排序）
首先先看两个例子：
情况1：对于已经排序好的一列数组，每次p值都选择第一个元素，那么算法的运行时间是多少？(n²)
情况2：对于已经排序号的一列数组，每次p值刚刚好是该数组元素的中位数，那么算法的运行时间是多少？Θ(nlgn）
可以看出，算法的性能取决于p值的选取，直觉上，选取随机的p值可以让算法有比较好的表现（这里我自己也没有完全想明白。）。后续的证明可以得出算法的平均时间复杂度为O（nlgn）。
Python代码
随机快速排序 (Randomized Quick sort)的实现
2 def partition_random(datalist,l,r):
3 index=random.randint(l,r-1)
4 datalist[l],datalist=datalist,datalist[l]
5 p=datalist[l]
6 i=l+1
7 for j in range(l+1,r):
8 if datalist[j]<p:
9 datalist,datalist[j]=datalist[j],datalist
10 i=i+1
11 datalist[l],datalist=datalist,datalist[l]
12 return阅读更多内容
没有评论:
发表评论