蓝桥杯 快速排序

Posted on | In |

排序在各种场合经常被用到。
快速排序是十分常用的高效率的算法。

其思想是：先选一个“标尺”，
用它把整个队列过一遍筛子，
以保证：其左边的元素都不大于它，其右边的元素都不小于它。

这样，排序问题就被分割为两个子区间。
再分别对子区间排序就可以了。

下面的代码是一种实现，请分析并填写划线部分缺少的代码。

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
#include <stdio.h>
#include<iostream>
using namespace std;

void swap(int a[], int i, int j)
{
int t = a[i];
a[i] = a[j]; 
a[j] = t;
}

int partition(int a[], int p, int r)
{
int i = p;
int j = r + 1;
int x = a[p];
while(1){
while(i<r && a[++i]<x);
while(a[--j]>x);
cout<<"i"<<i<<" "<<"j:"<<j<<endl;
if(i>=j) break;
swap(a,i,j);
}
______________________;
//swap(a,p,j)
return j;
}

void quicksort(int a[], int p, int r)
{
if(p<r){
int q = partition(a,p,r);  		
cout<<"q:"<<q<<endl;				
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}

int main()
{
int i;
int a[] = {2,5,3,-1,4};
int N = 5;

quicksort(a, 0, N-1);

for(i=0; i<N; i++) printf("%d ", a[i]);
printf("\n");

return 0;
}

快排单步(就是将一堆数按照某个数作为基准数分成左右两堆)这个实现方式有几种代码表现。在这里答案是swap(a,p,j).
不能填swap(a,p,i).