交换A[j]和A[j+1];
lastExchange=j;
}
i=lastExchange;//将i置为最后交换的位置
}//endwhile
}//BubbleSort
8.18改写快速排序算法,要求采用三者取中的方式选择划分的基准记录;若当前被排序的区间长度小于等于3时,无须划分而是直接采用直接插入方式对其排序。
8.19对给定的j(1≤j≤n),要求在无序的记录区R[1..n]中找到按关键字自小到大排在第j个位置上的记录(即在无序集合中找到第j个最小元),试利用快速排序的划分思想编写算法实现上述的查找操作。
8.20`以单链表为存储结构,写一个直接选择排序算法。
8.21写一个heapInsert(R,key)算法,将关键字插入到堆R中去,并保证插入R后仍是堆。
提示:
应为堆R增加一个长度属性描述(即改写本章定义的SeqList类型描述,使其含有长度域);将key先插入R中已有元素的尾部(即原堆的长度加1的位置,插入后堆的长度加1),然后从下往上调整,使插入的关键字满足性质。
请分析算法的时间。
8.22写一个建堆算法:
从空堆开始,依次读入元素调用上题中堆插入算法将其插入堆中。
8.23写一个堆删除算法:
HeapDelete(R,i),将R[i]从堆中删去,并分析算法时间,提示:
先将R[i]和堆中最后一个元素交换,并将堆长度减1,然后从位置i开始向下调整,使其满足堆性质。
8.24已知两个单链表中的元素递增有序,试写一算法将这两个有序表归并成一个递增有序的单链表。
算法应利用原有的链表结点空间。
8.25设向量A[0..n-1]中存有n个互不相同的整数,且每个元素的值均在0到n-1之间。
试写一时间为O(n)的算法将向量A排序,结果可输出到另一个向量B[0..n-1]中。
*8.26写一组英文单词按字典序排列的基数排序算法。
设单词均由大写字母构成,最长的单词有d个字母。
提示:
所有长度不足d个字母的单词都在尾处补足空格,排序时设置27个箱子,分别与空格,A,B...Z对应。
例题1、
下面的排序算法中,初始数据集的排列顺序对算法的性能无影响的是(B)
A、二分插入排序 B、堆排序 C、冒泡排序 D、快速排序
例题2、
写出下列算法的时间复杂度。
(1)冒泡排序;
(2)选择排序;(3)插入排序;(4)二分插入排序;(5)快速排序;(6)堆排序;(7)归并排序
例题1、
写出希尔排序算法程序,并说明最坏的情况下需要进行多少次的比较和交换。
程序略,需要O(n^2)次的比较
例题2、
设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列,则:
冒泡排序一趟扫描的结果是 H, C, Q, P, A, M, S, R, D, F, X ,Y ;
初始步长为4的希尔(shell)排序一趟的结果是 P, A, C, S, Q, D, F, X , R, H,M, Y ;
二路归并排序一趟扫描的结果是 H, Q, C, Y,A, P, M, S, D, R, F, X ;
快速排序一趟扫描的结果是 F, H, C, D, P, A, M, Q, R, S, Y,X ;
堆排序初始建堆的结果是 A, D, C, R, F, Q, M, S, Y,P, H, X 。
例题1、
在插入和选择排序中,若初始数据基本正序,则选用 插入排序(到尾部) ;若初始数据基本反序,则选用 选择排序 。
例题2、
下述几种排序方法中,平均查找长度(ASL)最小的是
A. 插入排序 B.快速排序 C. 归并排序 D. 选择排序
例题1、
对于整数序列100,99,98,…3,2,1,如果将它完全倒过来,分别用冒泡排序,它们的比较次数和交换次数各是多少?
答:
冒泡排序的比较和交换次数将最大,都是1+2+…+n-1=n(n-1)/2=50×99=4545次。
例题2、
把一个字符串的大写字母放到字符串的后面,各个字符的相对位置不变,不能申请额外的空间。
事实上,这道题放到冒泡排序这里不知道是不是特别合适,只是有一种解法是类似冒泡的思想,如下解法一
解法一、
每次遇到大写字母就往后冒,最后结果即为所求
[cpp] viewplaincopy
1.#include
2.#include
3.//题目以及要求:
把一个字符串的大写字母放到字符串的后面,
4.//各个字符的相对位置不变,不能申请额外的空间。
5.//判断是不是大写字母
6.int isUpperAlpha(char c){
7.if(c >= 'A' && c <= 'Z'){
8.return 1;
9.}
10.return 0;
11.}
12.//交换两个字母
13.void swap(char *a, char *b){
14.char temp = *a;
15.*a = *b;
16.*b = temp;
17.}
18.char * mySort(char *arr, int len){
19.if(arr == NULL || len <= 0){
20.return NULL;
21.}
22.int i = 0, j = 0, k = 0;
23.for(i = 0; i < len; i++){
24.for(j = len - 1 - i; j >= 0; j--){
25.if(isUpperAlpha(arr[j])){
26.for(k = j; k < len - i - 1; k++){
27.swap(&arr[k], &arr[k + 1]);
28.}
29.break;
30.}
31.//遍历完了字符数组,但是没发现大写字母,所以没必要再遍历下去
32.if(j == 0 && !
isUpperAlpha(arr[j])){
33.//结束;
34. return arr;
35.}
36.}
37.}
38.//over:
39.return arr;
40.}
41.int main(){
42.char arr[] = "aaaaaaaaaaaaaaaaaaaaaaaAbcAdeBbDc";
43.printf("%s\n", mySort(arr, strlen(arr)));
44.return 0;
45.}
解法二。
步骤如下
1、两个指针p1和p2,从后往前扫描
2、p1遇到一个小写字母时停下, p2遇到大写字母时停下,两者所指向的char交换
3、p1, p2同时往前一格
代码如下:
[cpp] viewplaincopy
1.#include
2.#include
3.//判断是不是大写字母
4.int isUpperAlpha(char c){
5.if(c >= 'A' && c <= 'Z'){
6.return 1;
7.}
8.return 0;
9.}
10.//交换两个字母
11.void swap(char *a, char *b){
12.char temp = *a;
13.*a = *b;
14.*b = temp;
15.}
16.char * Reorder(char *arr, int len){
17.if(arr == NULL || len <= 0){
18.return NULL;
19.}
20.int *p1 = arr;
21.int *p2 = arr;
22.While(p123.While( isUpperAlpha(*p1) ){
24.P1++;
25.}
26.While( !
isUpperAlpha(*p2) ){
27.P2++;
28.}
29.swap(p1, p2)
30.}
31.//结束
32.return arr;
33.}
34.int main(){
35.char arr[] = "aaaaaaaaaaaaaaaaaaaaaaaAbcAdeBbDc";
36.printf("%s\n", Reorder(arr, strlen(arr)));
37.return 0;
例题1、
最小的k个数,输入n个整数,找出其中最下的k个数,例如输入4、5、1、6、2、7、3、8、1、2,输出最下的4个数,则输出1、1、2、2。
当然,博主也知道这题可以建大小为k的大顶堆,然后用堆的方法解决。
但是这个题目可也以仿照快速排序,运用partition函数进行求解,不过我们完整的快速排序分割后要递归地对前后两段继续进行分割,而这里我们需要做的是判定分割的位置,然后再确定对前段还是后段进行分割,所以只对单侧分割即可。
代码如下:
[cpp] viewplaincopy
1.void GetLeastNumbers_by_partition(int* input, int n, int* output, int k)
2.{
3. if(input == NULL || output == NULL || k > n || n <= 0 || k <= 0)
4. return;
5. int start = 0;
6. int end = n - 1;
7. int index = Partition(input, n, start, end);
8. while(index !
= k - 1)
9. {
10. if(index > k - 1)
11. {
12. end = index - 1;
13. index = Partition(input, n, start, end);
14. }
15. else
16. {
17. start = index + 1;
18. index = Partition(input, n, start, end);
19. }
20. }
21. for(int i = 0; i < k; ++i)
22. output[i] = input[i];
23.}
例题2、
判断数组中出现超过一半的数字
当然,这道题很多人都见过,而且最通用的一种解法是数对对消的思路。
这里只是再给大家提供一种思路,快排partition的方法在很多地方都能使用,比如这题。
我们也可以选择合适的判定条件进行递归。
代码如下:
[cpp] viewplaincopy
1.bool g_bInputInvalid = false;
2.bool CheckInvalidArray(int* numbers, int length)
3.{
4. g_bInputInvalid = false;
5. if(numbers == NULL && length <= 0)
6. g_bInputInvalid = true;
7. return g_bInputInvalid;
8.}
9.bool CheckMoreThanHalf(int* numbers, int length, int number)
10.{
11. int times = 0;
12. for(int i = 0; i < length; ++i)
13. {
14. if(numbers[i] == number)
15. times++;
16. }
17. bool isMoreThanHalf = true;
18. if(times * 2 <= length)
19. {
20. g_bInputInvalid = true;
21. isMoreThanHalf = false;
22. }
23. return isMoreThanHalf;
24.}
25.int MoreThanHalfNum_Solution1(int* numbers, int length)
26.{
27. if(CheckInvalidArray(numbers, length))
28. return 0;
29. int middle = length >> 1;
30. int start = 0;
31. int end = length - 1;
32. int index = Partition(numbers, length, start, end);
33. while(index !
= middle)
34. {
35. if(index > middle)
36. {
37. end = index - 1;
38. index = Partition(numbers, length, start, end);
39. }
40. else
41. {
42. start = index + 1;
43. index = Partition(numbers, length, start, end);
44. }
45. }
46. int result = numbers[middle];
47. if(!
CheckMoreThanHalf(numbers, length, result))
48. result = 0;
49. return result;
50.}
例题3、
有一个由大小写组成的字符串,现在需要对他进行修改,将其中的所有小写字母排在大写字母的前面(不要求保持原顺序)
这题可能大家都能想到的方法是:
设置首尾两个指针,首指针向后移动寻找大写字母,尾指针向前移动需找小写字母,找到后都停下,交换。
之后继续移动,直至相遇。
这种方法在这里我就不做讨论写代码了。
但是这题也可以采用类似快排的partition。
这里使用从左往后扫描的方式。
字符串在调整的过程中可以分成两个部分:
已排好的小写字母部分、待调整的剩余部分。
用两个指针i和j,其中i指向待调整的剩余部分的第一个元素,用j指针遍历待调整的部分。
当j指向一个小写字母时,交换i和j所指的元素。
向前移动i、j,直到字符串末尾。
代码如下:
[cpp] viewplaincopy
1.#include
2.using namespace std;
3.void Proc( char *str )
4.{
5.int i = 0;
6.int j = 0;
7.//移动指针i, 使其指向第一个大写字母
8.while( str[i] !
= '\0' && str[i] >= 'a' && str[i] <= 'z' ) i++;
9.if( str[i] !
= '\0' )
10.{
11.//指针j遍历未处理的部分,找到第一个小写字母
12.for( j=i; str[j] !
= '\0'; j++ )
13.{
14.if( str[j] >= 'a' && str[j] <= 'z' )
15.{
16.char tmp = str[i];
17.str[i] = str[j];
18.str[j] = tmp;
19.i++;
20.}
21.}
22.}
23.}
24.int main()
25.{
26.char data[] = "SONGjianGoodBest";
27.Proc( data );
28.return 0;
29.}
30.例题1、
31.编写算法,从10亿个浮点数当中,选出其中最大的10000个。
32. 典型的Top K问题,用堆是最典型的思路。
建10000个数的小顶堆,然后将10亿个数依次读取,大于堆顶,则替换堆顶,做一次堆调整。
结束之后,小顶堆中存放的数即为所求。
代码如下(为了方便,这里直接使用了STL容器):
33.例题1、
34.题目输入一个数组,数组元素的大小在0->999.999.999的范围内,元素个数为0-500000范围。
题目要求通过相邻的元素的交换,使得输入的数组变为有序,要求输出交换的次数
35. 这题求解的其实就是一个逆序对。
我们回想一下归并排序的过程:
36. 归并排序是用分治思想,分治模式在每一层递归上有三个步骤:
37. 分解:
将n个元素分成个含n/2个元素的子序列。
38. 解决:
用合并排序法对两个子序列递归的排序。
39. 合并:
合并两个已排序的子序列已得到排序结果。
40. 在归并排序算法中稍作修改,就可以在n log n的时间内求逆序对。
41. 将数组A[1...size],划分为A[1...mid] 和 A[mid+1...size].那么逆序对数的个数为 f(1, size) = f(1, mid) + f(mid+1, size) + s(1, mid, size),这里s(1, mid, size)代表左值在[1---mid]中,右值在[mid+1, size]中的逆序对数。
由于两个子序列本身都已经排序,所以查找起来非常方便。
42.代码如下:
例题2、
有10个文件,每个文件1G,每个文件的每一行存放的都是用户的query,每个文件的query都可能重复。
要求你按照query的频度排序。
1、hash映射:
顺序读取10个文件,按照hash(query)%10的结果将query写入到另外10个文件(记为)中。
这样新生成的文件每个的大小大约也1G(假设hash函数是随机的)。
2、hash统计:
找一台内存在2G左右的机器,依次对用hash_map(query, query_count)来统计每个query出现的次数。
注:
hash_map(query,query_count)是用来统计每个query的出现次数,不是存储他们的值,出现一次,则count+1。
3、堆/快速/归并排序:
利用快速/堆/归并排序按照出现次数进行排序。
将排序好的query和对应的query_cout输出到文件中。
这样得到了10个排好序的文件(记为)。
对这10个文件进行归并排序(内排序与外排序相结合)。
例题3、
归并一个左右两边分别排好序的数组,空间复杂度要求O
(1)。
使用原地归并,能够让归并排序的空间复杂度降为O
(1),但是速度上会有一定程度的下降。
代码如下:
例题1、
一年的全国高考考生人数为500 万,分数使用标准分,最低100 ,最高900 ,没有小数,你把这500 万元素的数组排个序。
对500W数据排序,如果基于比较的先进排序,平均比较次数为O(5000000*log5000000)≈1.112亿。
但是我们发现,这些数据都有特殊的条件:
100=那么我们就可以考虑桶排序这样一个“投机取巧”的办法、让其在毫秒级别就完成500万排序。
创建801(900-100)个桶。
将每个考生的分数丢进f(score)=score-100的桶中。
这个过程从头到尾遍历一遍数据只需要500W次。
然后根据桶号大小依次将桶中数值输出,即可以得到一个有序的序列。
而且可以很容易的得到100分有***人,501分有***人。
实际上,桶排序对数据的条件有特殊要求,如果上面的分数不是从100-900,而是从0-2亿,那么分配2亿个桶显然是不可能的。
所以桶排序有其局限性,适合元素值集合并不大的情况。
例题2、
在一个文件中有 10G 个整数,乱序排列,要求找出中位数。
内存限制为 2G。
只写出思路即可(内存