DS_QuickSort

77 阅读 0 评论 51 点赞

我是靠谱客的博主矮小荷花，最近开发中收集的这篇文章主要介绍DS_QuickSort，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1-1

对N个记录进行快速排序，在最坏的情况下，其时间复杂度是O(NlogN)。

1-2

采用递归方式对顺序表进行快速排序，每次划分后，先处理较短的分区可以减少递归次数。

划分后，处理长的分区或处理短的分区可以减少递归对栈的使用内存；

递归次数与先处理长分区或短分区的顺序无关

排序算法平均时间复杂度
冒泡排序 O(n2)
选择排序 O(n2)
插入排序 O(n2)
希尔排序 O(n1.5)
快速排序 O(NlogN)
归并排序 O(NlogN)
堆排序 O(N*logN)
基数排序 O(d(n+r))

2-1

采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：

A.每次划分后，先处理较长的分区可以减少递归次数

B.每次划分后，先处理较短的分区可以减少递归次数

C.递归次数与每次划分后得到的分区处理顺序无关

D.递归次数与初始数据的排列次序无关

2-2

有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为：

A.{38,46,79,56,40,84}

B.{38,79,56,46,40,84}

C.{38,46,56,79,40,84}

D.{40,38,46,56,79,84}

2-3

在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左右指针都不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？

A.O(logN)

B.O(N)

C.O(NlogN)

D.O(N2)

指针停止就会不断交换左右指针的元素，这样虽然多余的交换次数变多，但让子序列的元素相对平均，所以一共有logN次划分，每次时间复杂度是O(N)。

2-4

在快速排序的一趟划分过程中，当遇到与基准数相等的元素时，如果左指针停止移动，而右指针在同样情况下却不停止移动，那么当所有元素都相等时，算法的时间复杂度是多少？

A.O(logN)

B.O(N)

C.O(NlogN)

D.O(N2)

指针不停止，导致所有元素都被放到一个划分中去，一共N个元素，所以一共有N次划分，每次时间复杂度是O(N)

2-5

排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是：

A.5, 2, 16, 12, 28, 60, 32, 72

B.2, 16, 5, 28, 12, 60, 32, 72

C.2, 12, 16, 5, 28, 32, 72, 60

D.5, 2, 12, 28, 16, 32, 72, 60

答案：D

原因：每经过一趟快排，轴点元素都必然就位。也就是说，一趟下来至少有1个元素在其最终位置。所以考察各个选项，看有几个元素就位即可。

最终排序位置是：2, 5, 12, 16, 28, 32, 60, 72

第一趟排序，确定一个元素位置
第二趟排序，又确定一个或两个元素位置
当第一趟元素确认的位置为最左或最右时，第二趟排序只能确认一个位置（A，B选项情况）
当第一趟元素确认位置不是最左或最右时，第二趟能确认2个位置（C选项情况）
所以，两趟排序共确认2或3个元素位置。

5-1

快速查找第K小元

分数 15

作者陈越

单位浙江大学

本函数的功能是从有N个元素的线性表A中查找第K小的元素。函数的初始调用为Qselect(A, K, 0, N-1)。请完成下列填空。

ElementType Qselect( ElementType A[], int K, int Left, int Right )
{
ElementType Pivot = A[Left];
int L = Left, R = Right+1;
while (1) {
while ( A[++L] < Pivot ) ;
________________________while ( A[--R] > Pivot )
if ( L < R ) Swap( &A[L], &A[R] );
else break;
}
Swap( &A[Left], &A[R] );
if ( K < (L-Left) )
return Qselect(A, K, Left, R-1);
else if ( K > (L-Left) )
________________________
return Qselect(A, K-(L-Left), L, Right)
else
return Pivot;
}

5-2

快速查找第K大元

本函数的功能是从有N个元素的线性表A中查找第K大的元素。函数的初始调用为Qselect(A, K, 0, N-1)。请完成下列填空。

ElementType Qselect( ElementType A[], int K, int Left, int Right )
{
ElementType Pivot = A[Left];
int L = Left, R = Right+1;
while (1) {
while ( A[--R] < Pivot ) ;
________________________
if ( L < R ) Swap( &A[L], &A[R] );
else break;
}
Swap( &A[Left], &A[R] );
if ( K < (L-Left) )
return Qselect(A, K, Left, R-1);
else if ( K > (L-Left) )
__________________________return Qselect(A, K-(L-Left), L, Right)
//return Qselect(A, K-(L-Left), L, Right)
else
return Pivot;
}

7-1 抢红包

没有人没抢过红包吧…… 这里给出N个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

输入格式：

输入第一行给出一个正整数N（≤104），即参与发红包和抢红包的总人数，则这些人从1到N编号。随后N行，第i行给出编号为i的人发红包的记录，格式如下：

KN1P1⋯NKPK

其中K（0≤K≤20）是发出去的红包个数，Ni是抢到红包的人的编号，Pi（>0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

输出格式：

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

输入样例：

10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10

输出样例：

#include <bits/stdc++.h>
using namespace std;
typedef struct Person per;
struct Person
{
int No;//编号
int cnt;//抢到红包个数
int money;//钱包余额
};
int main()
{
int n, faNum, qiangNum, rnb;//人数，发出红包个数，抢到的编号
cin >> n;
per a[n], temp; //结构体数组，临时变量
//for (int i = 0; i < n; i++)
//a[i].money = 0;
memset(a,0,sizeof(a)); //初始化
for (int i = 0; i < n; i++)
{
a[i].No = i + 1; //赋值编号
cin >> faNum; //发出的红包个数
for (int j = 0; j < faNum; j++)
{
cin >> qiangNum >> rnb;
a[qiangNum - 1].cnt++;
a[qiangNum - 1].money += rnb; //抢到进钱包
a[i].money -= rnb; //被抢走多少钱包就少多少
}
}
for (int i = 0; i < n - 1; i++)
{
for (int j = 0; j < n - 1 - i; j++)
{
if (a[j].money < a[j + 1].money ||
(a[j].money == a[j + 1].money && a[j].cnt < a[j + 1].cnt) ||
(a[j].money == a[j + 1].money && a[j].cnt == a[j + 1].cnt && a[j].No > a[j + 1].No))
{
temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for (int i = 0; i < n; i++)
{
printf("%d %.2fn", a[i].No, (float)a[i].money / 100.0);
}
return 0;
}