1
2
3
4
5
数据：[1,1,3,3,2,2,6,6,6,5,5,7]
要求：利用快速排序算法进行列表数据排序
    1.文字说明快速排序算法原理
    2.代码需有充足注释

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def quicksort(data,start,end):   #定义函数，参数分别为数据（list），算法起始位以及结束位，往往分别为0与len(data)-1,即第一个数据与最后一个数据
    if start >= end:         #当起始位置在结束位置之前时
        return              #退出递归
    key = data[start]           #以列表第一个数据作为标志位
    i = start               #将起始位置作为i。从i位置开始向右遍历
    j = end                 #将结束位置作为j。从j位置开始向左遍历
    #将所有比key值大的置于key值右边，所有比key值小的置于左边；
    while i != j :          #当i与j未重合时，即分别在key值的左右两半时
        while i < j and data[j] >= key: #当i值小于j值，且此时j位置大于key值时
            j = j - 1                   #则此j位置值置于key值右边为正确的，遍历下一个
        data[i] = data[j]           	#当找到data[j]比key值小时，退出上述while循环，将找到的比key值小的j位置值赋值给i位置
        while i < j and data[i] < key:  #同样道理，当i值小于j值，且此时j位置小于key值时
            i = i + 1                   #则此i位置值置于key值左边为正确的，遍历下一个值
        data[j] = data[i]          	 	#当找到data[i]比key值大时，退出上述while循环，将找到的比key值大的i位置值赋值给j位置
    #上述遍历后，i与j重合，重合位置即为key值正确位置，比其小的都在左边，比其大的元素都在右边
    data[i] = key
    quicksort(data,start,i-1) 	#同样的办法，遍历key值左半部分的
    quicksort(data,i+1,end) 	#遍历key值右半部分

data =[1,1,3,3,2,2,6,6,6,5,5,7] #等待排序的数据
quicksort(data,0,len(data)-1)   #执行快速排序算法
print(data)				        #打印排序后的data数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function data =QuickSort(data,start,endadd) //定义函数名，与函数返回值
if start >= endadd	//退出递归的条件
    return
end
if start < endadd  //当递归条件符合时
    key = data(start); //第一个数据作为键值
    i = start;		//将起始位置作为i。从i位置开始向右遍历
    j = endadd;		//将结束位置作为j。从j位置开始向左遍历
    while i ~= j	//当i与j未重合时，即分别在key值的左右两半时
        while (i<j) && (data(j) >= key)  //当i值小于j值，且此时j位置大于key值时
            j = j-1;					//则此j位置值置于key值右边为正确的，遍历下一个
        end
        data(i) = data(j);				//当找到data[j]比key值小时，退出上述while循环，将找到的比key值小的j位置值赋值给i位置
        while (i<j) && (data(i) <= key)	//同样道理，当i值小于j值，且此时j位置小于key值时
            i = i+1;					//则此i位置值置于key值左边为正确的，遍历下一个值
        end
        data(j) = data(i); 				//当找到data[i]比key值大时，退出上述while循环，将找到的比key值大的i位置值赋值给j位置
    end
    //上述遍历后，i与j重合，重合位置即为key值正确位置，比其小的都在左边，比其大的元素都在右边
    data(i) = key;
    data =QuickSort(data,start,j-1);//同样的办法，遍历key值左半部分的
    data =QuickSort(data,i+1,endadd);//遍历key值右半部分
end

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
clc
clear
close all

data=[1,1,3,3,2,2,6,6,6,5,5,7]; //数据内容
start=1;	//起始位置，在matlab中，数组元素位置从1开始
endadd=size(data,2); //

disp('未排序的序列为：'); //打印文字
disp(data);				//打印未排序的序列

data=QuickSort(data,start,endadd); //将数据进行快速排序

disp('快速排序之后的序列为：');//打印文字
disp(data);					//打印快速排序后的序列

1
2
3
4
5
6
7
8
9
# 将 10不断除以2，直至商为0，输出这个过程中每次得到的商的值。
def recursion(n):
    v = n//2 # 保留整数
    print(v) # 每次求商，输出商的值
    if v==0:
        return 'Done'#当商为0时，停止递归：在函数中，return后，则不会继续执行下面的语句，则停止了递归
    v = recursion(v) # 递归调用，函数内自己调用自己
recursion(10)

1
2
3
4
5
数据：[1, 2, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 10, 11, 11, 11,11, 12, 13, 13, 15, 16, 16, 20, 21, 21, 23, 24, 26,26, 27, 28, 28, 31, 33, 33, 34, 35, 38, 38, 39, 40,42, 43, 45, 45, 46, 46, 47, 47, 51, 52, 52, 53, 53,55, 55, 56, 56, 57, 57, 57, 58, 59, 61, 62, 64, 66,66, 67, 68, 69, 69, 71, 72, 72, 74, 74, 75, 76, 78,78, 79, 79, 79, 79, 80, 82, 85, 88, 89, 90, 90, 91,91, 91, 94, 99, 99]
要求：给定一个有序数组 arr 和一个目标元素 target ，返回该 target 在 arr 中的索引，若不存在，返回-1。本题arr如上所示，target为66
    1.文字说明快速排序算法原理
    2.代码需有充足注释

1
2
3
4
5
数据：1.“abcbefgf”    2.“abcdef”   3."abbcddefh"
要求：给定一个字符串，找出没有重复字符的最长的子串。例如输入“abcbefgf”，答案是 “cbefg”。
    1.文字说明快速排序算法原理（动态规划+哈希查找）
    2.代码需有充足注释

1
2
3
4
5
数据：arr = [-3,-1,-2,1,2,3]
要求：给定一个数组和目标数target，找出数组中a,b,c满足 a+b+c = target 的所有组合。例如：arr = [-3,-1,-2,1,2,3]，target = 0。输出为 [(-3,1,2),(-2,-1,3)]
    1.代码需有充足注释
    2.时间复杂度要求为O(n**2) ，空间复杂度要求O(1)